Game Transformations That Preserve Nash Equilibria or Best-Response Sets
Pages 2513 - 2515
Abstract
In the full version of this paper, we investigate under which conditions normal-form games are (guaranteed) to be strategically equivalent. First, we show for N-player games (N ≥ 3) that (a) it is NP-hard to decide whether a given strategy is a best response to some strategy profile of the opponents, and that (b) it is co-NP-hard to decide whether two games have the same best-response sets.
We then turn our attention to equivalence-preserving game transformations. It is a widely used fact that a positive affine (linear) transformation of the utility payoffs neither changes the best-response sets nor the Nash equilibrium set. We investigate which other game transformations also possess either of the following two properties when being applied to an arbitrary N-player game (N ≥ 2): (i) The Nash equilibrium set stays the same; (ii) The best-response sets stay the same.
For game transformations that operate player-wise and strategy-wise, we prove that (i) implies (ii) and that transformations with property (ii) must be positive affine. The resulting equivalence chain highlights the special status of positive affine transformations among all the transformation procedures that preserve key game-theoretic characteristics.
References
[1]
Timothy G. Abbott, Daniel M. Kane, and Paul Valiant. 2005. On the Complexity of Two-PlayerWin-Lose Games. In 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23--25 October 2005, Pittsburgh, PA, USA, Proceedings. IEEE Computer Society, 113--122. https://doi.org/10.1109/SFCS.2005.59
[2]
Ilan Adler. 2013. The equivalence of linear programs and zero-sum games. Int. J. Game Theory 42, 1 (2013), 165--177. https://doi.org/10.1007/s00182-012-0328-8
[3]
Ilan Adler, Constantinos Daskalakis, and Christos H. Papadimitriou. 2009. A Note on Strictly Competitive Games. In Internet and Network Economics, 5th International Workshop, WINE 2009, Rome, Italy, December 14-18, 2009. Proceedings, Stefano Leonardi (Ed.). Springer, 471--474. https://doi.org/10.1007/978-3-642-10841-9_44
[4]
Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni, and Bernhard von Stengel. 2021. Fast Algorithms for Rank-1 Bimatrix Games. Oper. Res. 69, 2 (2021), 613--631. https://doi.org/10.1287/opre.2020.1981
[5]
Robert J. Aumann. 1961. Almost Strictly Competitive Games. Journal of The Society for Industrial and Applied Mathematics 9 (1961), 544--550.
[6]
Tamer Başar and Geert Jan Olsder. 1998. Dynamic Noncooperative Game Theory (2nd. ed.). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611971132
[7]
B. Douglas Bernheim. 1984. Rationalizable Strategic Behavior. Econometrica 52, 4 (1984), 1007--1028. http://www.jstor.org/stable/1911196
[8]
Felix Brandt, Felix A. Fischer, and Yoav Shoham. 2006. On Strictly Competitive Multi-Player Games. In Proceedings, The Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Applications of Artificial Intelligence Conference, July 16-20, 2006, Boston, Massachusetts, USA. AAAI Press, 605--612. http://www.aaai.org/Library/AAAI/2006/aaai06-097.php
[9]
André Casajus. 2003. Weak isomorphism of extensive games. Math. Soc. Sci. 46, 3 (2003), 267--290. https://doi.org/10.1016/S0165-4896(03)00064-7
[10]
Chih Chang and Stef Tijs. 2006. A note on isomorphism and strategic equivalence of cooperative games. TOP 14 (2006), 333--342. https://doi.org/10.1007/BF02837566
[11]
George B Dantzig. 1951. A proof of the equivalence of the programming problem and the game problem. In Activity analysis of production and allocation, Tjalling C. Koopmans (Ed.). Cowles Commission Monograph No.13, 330--335.
[12]
Gaston Darboux. 1875. Sur la composition des forces en statique. Bulletin des Sciences Mathématiques et Astronomiques 9 (1875), 281--288.
[13]
Ye Du. 2008. On the complexity of deciding bimatrix games similarity. Theor. Comput. Sci. 407, 1--3 (2008), 583--586. https://doi.org/10.1016/j.tcs.2008.07.021
[14]
Susan Elmes and Philip J. Reny. 1994. On the Strategic Equivalence of Extensive Form Games. Journal of Economic Theory 62, 1 (1994), 1--23. https://doi.org/10. 1006/jeth.1994.1001
[15]
Joaquim Gabarró, Alina García, and Maria J. Serna. 2011. The complexity of game isomorphism. Theor. Comput. Sci. 412, 48 (2011), 6675--6695. https://doi.org/10.1016/j.tcs.2011.07.022
[16]
Joaquim Gabarró, Alina García, and Maria J. Serna. 2013. On the hardness of game equivalence under local isomorphism. RAIRO Theor. Informatics Appl. 47, 2 (2013), 147--169. https://doi.org/10.1051/ita/2012024
[17]
Michael R. Garey and David S. Johnson. 1990. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA.
[18]
Peter J. Hammond. 2005. Utility Invariance in Non-Cooperative Games. In Advances in Public Economics: Utility, Choice and Welfare, Ulrich Schmidt and Stefan Traub (Eds.). Springer, Boston, MA, 31--50. https://doi.org/10.1007/0-387-25706-3_3
[19]
J.C. Harsanyi and R. Selten. 1988. A General Theory of Equilibrium Selection in Games. MIT Press.
[20]
Joseph L. Heyman and Abhishek Gupta. 2023. Rank Reduction in Bimatrix Games. IGTR 25, 1 (2023). https://doi.org/10.1142/S0219198922500177
[21]
Elon Kohlberg and Jean-Francois Mertens. 1986. On the Strategic Stability of Equilibria. Econometrica 54, 5 (1986), 1003--1037. http://www.jstor.org/stable/1912320
[22]
Spyros C. Kontogiannis and Paul G. Spirakis. 2012. On mutual concavity and strategically-zero-sum bimatrix games. Theor. Comput. Sci. 432 (2012), 64--76. https://doi.org/10.1016/j.tcs.2012.01.016
[23]
Luchuan A. Liu. 1996. The Invariance of Best Reply Correspondences in Two-Player Games. (1996). 93, City University of Hong Kong, Faculty of Business, Department of Economics.
[24]
Luke Marris, Ian Gemp, and Georgios Piliouras. 2023. Equilibrium-Invariant Embedding, Metric Space, and Fundamental Set of 2 × 2 Normal-Form Games. arXiv:2304.09978 [cs.GT]
[25]
Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. 1995. Microeconomic Theory. Oxford University Press.
[26]
Michael Maschler, Eilon Solan, and Shmuel Zamir. 2013. Game Theory. Cambridge University Press. https://doi.org/10.1017/CBO9780511794216
[27]
Stephen Morris and Takashi Ui. 2004. Best response equivalence. Games Econ. Behav. 49, 2 (2004), 260--287. https://doi.org/10.1016/j.geb.2003.12.004
[28]
H. Moulin and J.P. Vial. 1978. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International Journal of Game Theory 7 (1978), 201--221. https://doi.org/10.1007/BF01769190
[29]
John F. Nash. 1950. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences 36, 1 (1950), 48--49. https://doi.org/10.1073/pnas.36.1.48 arXiv:https://www.pnas.org/doi/pdf/10.1073/pnas.36.1.48
[30]
David G. Pearce. 1984. Rationalizable Strategic Behavior and the Problem of Perfection. Econometrica 52, 4 (1984), 1029--1050. http://www.jstor.org/stable/1911197
[31]
Antonin Pottier and Rabia Nessah. 2014. Berge-Vaisman and Nash Equilibria: Transformation of Games. IGTR 16, 4 (2014). https://doi.org/10.1142/S0219198914500091
[32]
ProofWiki. 2020. Additive Function is Linear for Rational Factors. https://proofwiki.org/wiki/Additive_Function_is_Linear_for_Rational_Factors
[33]
ProofWiki. 2021. Monotone Additive Function is Linear. https://proofwiki.org/ wiki/Monotone_Additive_Function_is_Linear
[34]
Daniel Reem. 2017. Remarks on the Cauchy functional equation and variations of it. Aequationes mathematicae 91 (2017), 237--264.
[35]
Emanuel Tewolde and Vincent Conitzer. 2023. Game Transformations that Preserve Nash Equilibria or Best Response Sets. CoRR abs/2111.00076 (2023). arXiv:2111.00076 https://arxiv.org/abs/2111.00076
[36]
F. B. Thompson. 1952. Equivalence of Games in Extensive Form. RAND Corporation, Santa Monica, CA.
[37]
John von Neumann. 1928. Zur Theorie der Gesellschaftsspiele. Math. Ann. 100 (1928), 295--320.
[38]
John von Neumann and Oskar Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton University Press.
[39]
Bernhard von Stengel. 2022. Game Theory Basics. Cambridge University Press.
[40]
Yuhu Wu, Shuting Le, Kuize Zhang, and Xi-Ming Sun. 2022. Agent Transformation of Bayesian Games. IEEE Trans. Automat. Control 67, 11 (2022), 5793--5808. https://doi.org/10.1109/TAC.2021.3122372
Index Terms
- Game Transformations That Preserve Nash Equilibria or Best-Response Sets
Recommendations
Computing Nash equilibria gets harder: new results show hardness even for parameterized complexity
CATS '09: Proceedings of the Fifteenth Australasian Symposium on Computing: The Australasian Theory - Volume 94In this paper we show that some decision problems regarding the computation of Nash equilibria are to be considered particularly hard. Most decision problems regarding Nash equilibria have been shown to be NP-complete. While some NP-complete problems ...
A note on approximate Nash equilibria
In view of the intractability of finding a Nash equilibrium, it is important to understand the limits of approximation in this context. A subexponential approximation scheme is known [Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Playing large ...
The structure and complexity of Nash equilibria for a selfish routing game
In this work, we study the combinatorial structure and the computational complexity of Nash equilibria for a certain game that models selfish routing over a network consisting of m parallel links. We assume a collection of n users, each employing a ...
Comments
Information & Contributors
Information
Published In
May 2024
2898 pages
ISBN:9798400704864
- General Chairs:
- Mehdi Dastani,
- Jaime Simão Sichman,
- Program Chairs:
- Natasha Alechina,
- Virginia Dignum
Sponsors
Publisher
International Foundation for Autonomous Agents and Multiagent Systems
Richland, SC
Publication History
Published: 06 May 2024
Check for updates
Author Tags
Qualifiers
- Extended-abstract
Funding Sources
- Cooperative AI Foundation Polaris Ventures and Jaan Tallinn's donor-advised fund at Founders Pledge
Conference
AAMAS '23
Sponsor:
AAMAS '23: International Conference on Autonomous Agents and Multiagent Systems
May 6 - 10, 2024
Auckland, New Zealand
Acceptance Rates
Overall Acceptance Rate 1,155 of 5,036 submissions, 23%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 5Total Downloads
- Downloads (Last 12 months)5
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in