Pure Nash equilibria in restricted budget games. (English) Zbl 1422.91054
Summary: 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.
MSC:
| 91A10 | Noncooperative games |
| 91A43 | Games involving graphs |
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
References:
| [1] | Ackermann H, Röglin H, Vöcking B (2009) Pure Nash equilibria in player-specific and weighted congestion games. Theor Comput Sci 410(17):1552-1563 · Zbl 1159.91328 · doi:10.1016/j.tcs.2008.12.035 |
| [2] | Anshelevich E, Dasgupta A, Kleinberg J, Tardos E, Wexler T, Roughgarden T (2008) The price of stability for network design with fair cost allocation. SIAM J Comput 38(4):1602-1623 · Zbl 1173.91321 · doi:10.1137/070680096 |
| [3] | Byde A, Polukarov M, Jennings NR (2009) Games with congestion-averse utilities. In: Algorithmic game theory: second international symposium. Springer, Berlin, pp 220-232 · Zbl 1262.91013 |
| [4] | Caragiannis I, Fanelli A, Gravin N, Skopalik A (2015) Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. ACM Trans Econ Comput 3(1):2:1-2:32 · Zbl 1292.91012 · doi:10.1145/2614687 |
| [5] | Chien S, Sinclair A (2011) Convergence to approximate Nash equilibria in congestion games. Games Econ Behav 71(2):315-327 · Zbl 1209.91020 · doi:10.1016/j.geb.2009.05.004 |
| [6] | Drees M, Riechers S, Skopalik A (2014) Budget-restricted utility games with ordered strategic decisions. In: Proceedings of the 7th international symposium on algorithmic game theory. Springer, Berlin, pp 110-121 · Zbl 1403.91037 |
| [7] | Drees M, Feldotto M, Riechers S, Skopalik A (2015) On existence and properties of approximate pure Nash equilibria in bandwidth allocation games. In: Proceedings of the 8th international symposium on algorithmic game theory. Springer, Berlin, pp 178-189 · Zbl 1358.91071 |
| [8] | Gairing M, Klimm M (2013) Congestion games with player-specific costs revisited. In: Proceedings of the 6th international symposium on algorithmic game theory. Springer, Berlin, pp 98-109 · Zbl 1319.91015 |
| [9] | Hansknecht C, Klimm M, Skopalik A (2014) Approximate pure Nash equilibria in weighted congestion games. In: Proceedings of the 17th international workshop on approximation algorithms for combinatorial optimization problems. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, pp 242-257 · Zbl 1360.91013 |
| [10] | Harks T, Klimm M (2010) On the existence of pure Nash equilibria in weighted congestion games. In: Proceedings of the 38th international colloquium on automata, languages and programming. Springer, Berlin, pp 79-89 · Zbl 1287.91005 |
| [11] | Harks T, Klimm M (2015) Congestion games with variable demands. Math Oper Res 41(1):255-277 · Zbl 1347.91014 · doi:10.1287/moor.2015.0726 |
| [12] | Jain K, Mahdian M (2007) Cost sharing. Algorithmic Game Theory 15:385-410 · Zbl 1152.91332 · doi:10.1017/CBO9780511800481.017 |
| [13] | Kollias K, Roughgarden T (2015) Restoring pure equilibria to weighted congestion games. ACM Trans Econ Comput 3(4):21:1-21:24 · Zbl 1334.91024 · doi:10.1145/2781678 |
| [14] | Mavronicolas M, Milchtaich I, Monien B, Tiemann K (2007) Congestion games with player-specific constants. In: Proceedings of the 32nd international conference on mathematical foundations of computer science, pp 633-644 · Zbl 1147.91304 |
| [15] | Milchtaich I (1996) Congestion games with player-specific payoff functions. Games Econ Behav 13(1):111-124 · Zbl 0848.90131 · doi:10.1006/game.1996.0027 |
| [16] | Monderer D, Shapley LS (1996) Potential games. Games Econ Behav 14(1):124-143 · Zbl 0862.90137 · doi:10.1006/game.1996.0044 |
| [17] | Rosenthal RW (1973) A class of games possessing pure-strategy Nash equilibria. Int J Game Theory 2(1):65-67 · Zbl 0259.90059 · doi:10.1007/BF01737559 |
| [18] | Shapley LS (1952) A value for n-person games. Technical report, DTIC Document · Zbl 0050.14404 |
| [19] | Voice T, Polukarov M, Byde A, Jennings NR (2009) On the impact of strategy and utility structures on congestion-averse games. In: Proceedings of the 5th international conference on web and internet economics. Springer, Berlin, pp 600-607 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
