Abstract
A recent sequence of results established that computing Nash equilibria in normal form games is a PPAD-complete problem even in the case of two players [11,6,4]. By extending these techniques we prove a general theorem, showing that, for a far more general class of families of succinctly representable multiplayer games, the Nash equilibrium problem can also be reduced to the two-player case. In view of empirically successful algorithms available for this problem, this is in essence a positive result — even though, due to the complexity of the reductions, it is of no immediate practical significance. We further extend this conclusion to extensive form games and network congestion games, two classes which do not fall into the same succinct representation framework, and for which no positive algorithmic result had been known.
This is a preview of subscription content, log in via an institution.
Buying options
Tax calculation will be finalised at checkout
Purchases are for personal use only
Learn about institutional subscriptionsPreview
Unable to display preview. Download preview PDF.
References
Aumann, R.J.: Subjectivity and Correlation in Randomized Strategies. Journal of Mathematical Economics 1, 67–95 (1974)
Bürgisser, P.: On the structure of Valiant’s complexity classes. Discr. Math. Theoret. Comp. Sci. 3, 73–94 (1999)
Chen, X., Deng, X.: 3-NASH is PPAD-Complete. ECCC, TR05-134 (2005)
Chen, X., Deng, X.: Settling the Complexity of 2-Player Nash-Equilibrium. ECCC, TR05-140 (2005)
Daskalakis, C., Papadimitriou, C.H.: Three-Player Games Are Hard. ECCC, TR05-139 (2005)
Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The Complexity of Computing a Nash Equilibrium. In: Proceedings of 38th STOC (2006)
Fabrikant, A., Papadimitriou, C.H., Talwar, K.: The Complexity of Pure Nash Equilibria. In: Proceedings of 36th STOC (2004)
Feigenbaum, J., Koller, D., Shor, P.: A game-theoretic classification of interactive complexity classes. In: IEEE Conference on Structure in Complexity Theory (1995)
Fortnow, L., Impagliazzo, R., Kabanets, V., Umans, C.: On the Complexity of Succinct Zero-Sum Games. In: IEEE Conference on Computational Complexity (2005)
Geanakoplos, J.: Nash and Walras Equilibrium via Brouwer. Economic Theory, 21 (2003)
Goldberg, P.W., Papadimitriou, C.H.: Reducibility Among Equilibrium Problems. In: Proceedings of 38th STOC (2006)
Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How Easy is Local Search? J. Comput. Syst. Sci. 37(1), 79–100 (1988)
Kearns, M., Littman, M., Singh, S.: Graphical Models for Game Theory. In: UAI (2001)
Lemke, C.E., Howson Jr., J.T.: Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics 12, 413–423 (1964)
Nash, J.: Noncooperative Games. Annals of Mathematics 54, 289–295 (1951)
Osborne, M.J., Rubinstein, A.: A Course in Game Theory. MIT Press, Cambridge (1994)
Papadimitriou, C.H.: Computing Correlated Equilibria in Multiplayer Games. In: STOC (2005)
Papadimitriou, C.H.: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 3, 498–532 (1994)
Savani, R., von Stengel, B.: Exponentially many steps for finding a Nash equilibrium in a Bimatrix Game. In: Proceedings of 45th FOCS (2004)
von Stengel, B.: Computing equilibria for two-person games. In: Aumann, R.J., Hart, S. (eds.) Handbook of Game Theory, vol. 3, pp. 1723–1759. North-Holland, Amsterdam (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Daskalakis, C., Fabrikant, A., Papadimitriou, C.H. (2006). The Game World Is Flat: The Complexity of Nash Equilibria in Succinct Games. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds) Automata, Languages and Programming. ICALP 2006. Lecture Notes in Computer Science, vol 4051. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11786986_45
Download citation
DOI: https://doi.org/10.1007/11786986_45
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-35904-3
Online ISBN: 978-3-540-35905-0
eBook Packages: Computer ScienceComputer Science (R0)