Pure Nash Equilibria in Restricted Budget Games

Maximilian Werner Drees, Matthias Feldotto, Sören Riechers, Alexander Skopalik

Research output: Contribution to conferencePaperpeer-review

2 Downloads (Pure)

Abstract

In budget games, players compete over resources with finite budgets. For every resource, a player has a specific demand and as a strategy, he chooses a subset of resources. If the total demand on a resource does not exceed its budget, the utility of each player who chose that resource equals his demand. Otherwise, the budget is shared proportionally. In the general case, pure Nash equilibria (NE) do not exist for such games. In this paper, we consider the natural classes of singleton and matroid budget games with additional constraints and show that for each, pure NE can be guaranteed. In addition, we introduce a lexicographical potential function to prove that every matroid budget game has an approximate pure NE which depends on the largest ratio between the different demands of each individual player.
Original languageEnglish
Pages175
Number of pages187
DOIs
Publication statusPublished - 1 Jul 2017
Event24th International Conference on Computing and Combinatorics, COCOON 2018 - Qingdao, China
Duration: 2 Jul 20184 Jul 2018
Conference number: 24

Conference

Conference24th International Conference on Computing and Combinatorics, COCOON 2018
Abbreviated titleCOCOON 2018
Country/TerritoryChina
CityQingdao
Period2/07/184/07/18

Fingerprint

Dive into the research topics of 'Pure Nash Equilibria in Restricted Budget Games'. Together they form a unique fingerprint.

Cite this