Constantinos Daskalakis
Paul W. Goldberg
Christos H. Papadimitriou
ABSTRACT
We resolve the question of the complexity of Nash equilibrium by showing that the problem of computing a Nash equilibrium in a game with 4 or more players is complete for the complexity class PPAD. Our proof uses ideas from the recently-established equivalence between polynomial time solvability of normal form games and graphical games, establishing that these kinds of games can simulate a PPAD-complete class of Brouwer functions.
- P. Beame, S. Cook, J. Edmonds, R. Impagliazzo, T. Pitassi. "The Relative Complexity of NP Search Problems," J. Comput. Syst. Sci. 57, 1, pp. 13--19, 1998. Google Scholar
Digital Library
- X. Chen and X. Deng. "3-NASH is PPAD-Complete," Electronic Colloquium in Computational Complexity TR05-134, 2005.Google Scholar
- X. Chen and X. Deng. "Settling the Complexity of 2-Player Nash-Equilibrium," Electronic Colloquium in Computational Complexity TR05-140, 2005.Google Scholar
- X. Chen, X. Deng and S. Teng. "Computing Nash Equilibria: Approximation and Smoothed Complexity," arXiv report, 2006.Google Scholar
- B. Codenotti, A. Saberi, K. Varadarajan and Y. Ye. "Leontief Economies Encode Nonzero Sum Two-Player Games," Proceedings of SODA, 2006. Google ScholarDigital Library
- V. Conitzer and T. Sandholm. "Complexity Results about Nash Equilibria," Proceedings of IJCAI, 2003. Google ScholarDigital Library
- C. Daskalakis, A. Fabrikant and C. H. Papadimitriou. "The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games," To appear, 2006.Google Scholar
- C. Daskalakis and C. H. Papadimitriou. "Three-Player Games Are Hard," Electronic Colloquium in Computational Complexity TR05-139, 2005.Google Scholar
- A. Fabrikant, C.H. Papadimitriou and K. Talwar. "The Complexity of Pure Nash Equilibria," Proceedings of STOC, 2004. Google ScholarDigital Library
- J. Geanakoplos. "Nash and Walras Equilibrium via Brouwer," Economic Theory, 21, 2003.Google Scholar
- I. Gilboa and E. Zemel. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, 1989.Google Scholar
- P. W. Goldberg and C. H. Papadimitriou. "Reducibility Among Equilibrium Problems," Proceedings of STOC, 2006. Google ScholarDigital Library
- M. Hirsch, C. H. Papadimitriou and S. Vavasis. "Exponential Lower Bounds for Finding Brouwer Fixpoints," J. Complexity 5, pp. 379--416, 1989. Google ScholarDigital Library
- D. S. Johnson, C. H. Papadimitriou and M. Yannakakis, "How Easy is Local Search?," J. Comput. Syst. Sci. 37, 1, pp. 79--100,1988. Google ScholarDigital Library
- M. Kearns, M. Littman and S. Singh. "Graphical Models for Game Theory," Proceedings of UAI, 2001. Google ScholarDigital Library
- C. E. Lemke and J. T. Howson, Jr. "Equilibrium points of bimatrix games", SIAM J. Appl. Math. 12, pp. 413--423, 1964.Google ScholarCross Ref
- R. Lipton and E. Markakis. "Nash Equilibria via Polynomial Equations," Proceedings of LATIN, 2004.Google Scholar
- R. Lipton, E. Markakis and A. Mehta. "Playing large games using simple strategies," Proceedings of the ACM Conference on Electronic Commerce, 2003. Google ScholarDigital Library
- M. Littman, M. Kearns and S. Singh. "An Efficient Exact Algorithm for Single Connected Graphical Games," Proceedings of NIPS, 2002.Google Scholar
- J. Nash. "Noncooperative Games," Annals of Mathematics, 54, 289--295, 1951.Google ScholarCross Ref
- J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior, Princeton University Press, 1944.Google Scholar
- M.J. Osborne and A. Rubinstein. A Course in Game Theory, MIT Press (1994).Google Scholar
- C. H. Papadimitriou. "On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence," J. Comput. Syst. Sci. 48, 3, pp. 498--532, 1994. Google ScholarDigital Library
- C. H. Papadimitriou and T. Roughgarden. "Computing equilibria in multi-player games," Proceedings of SODA, 2005. Google ScholarDigital Library
- C. H. Papadimitriou. "Computing Correlated Equilibria in Multiplayer Games," Proceedings of STOC, 2005. Google ScholarDigital Library
- R. Savani and B. von Stengel. "Exponentially many steps for finding a Nash equilibrium in a Bimatrix Game," Proceedings of FOCS, 2004. Google ScholarDigital Library
- G. Schoenebeck and S. Vadhan. "The Computational Complexity of Nash Equilibria in Concisely Represented Games," To appear in ACM EC, 2006. Google ScholarDigital Library
Index Terms
- The complexity of computing a Nash equilibrium
Recommendations
Settling the complexity of computing two-player Nash equilibria
We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991.
Our result, building upon the work of ...
The Complexity of Computing a Nash Equilibrium
In 1951, John F. Nash proved that every game has a Nash equilibrium [Ann. of Math. (2), 54 (1951), pp. 286-295]. His proof is nonconstructive, relying on Brouwer's fixed point theorem, thus leaving open the questions, Is there a polynomial-time ...
On the Complexity of Approximating a Nash Equilibrium
Special Issue on SODA'11We show that computing a relatively (i.e., multiplicatively as opposed to additively) approximate Nash equilibrium in two-player games is PPAD-complete, even for constant values of the approximation. Our result is the first constant inapproximability ...
Comments