The complexity of computing a Nash equilibrium

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.

REFERENCES

• 1: Paul Beame , Stephen Cook , Jeff Edmonds , Russell Impagliazzo , Toniann Pitassi, The relative complexity of NP search problems, Journal of Computer and System Sciences, v.57 n.1, p.3-19, Aug. 1998 [doi>10.1006/jcss.1998.1575]
• 2: X. Chen and X. Deng. "3-NASH is PPAD-Complete," Electronic Colloquium in Computational Complexity TR05-134, 2005.
• 3: X. Chen and X. Deng. "Settling the Complexity of 2-Player Nash-Equilibrium," Electronic Colloquium in Computational Complexity TR05-140, 2005.
• 4: X. Chen, X. Deng and S. Teng. "Computing Nash Equilibria: Approximation and Smoothed Complexity," arXiv report, 2006.
• 5: Bruno Codenotti , Amin Saberi , Kasturi Varadarajan , Yinyu Ye, Leontief economies encode nonzero sum two-player games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.659-667, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109629]
• 6: V. Conitzer and T. Sandholm. "Complexity Results about Nash Equilibria," Proceedings of IJCAI, 2003.
• 7: C. Daskalakis, A. Fabrikant and C. H. Papadimitriou. "The Game World is Flat: The Complexity of Nash Equilibria in Succinct Games," To appear, 2006.
• 8: C. Daskalakis and C. H. Papadimitriou. "Three-Player Games Are Hard," Electronic Colloquium in Computational Complexity TR05-139, 2005.
• 9: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 10: J. Geanakoplos. "Nash and Walras Equilibrium via Brouwer," Economic Theory, 21, 2003.
• 11: I. Gilboa and E. Zemel. "Nash and correlated equilibria: Some complexity considerations," Games and Economic Behavior, 1989.
• 12: Paul W. Goldberg , Christos H. Papadimitriou, Reducibility among equilibrium problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132526]
• 13: M. D. Hirsch , C. H. Papadimitriou, Exponential lower bounds for finding Brouwer fixed points, Journal of Complexity, v.5 n.4, p.379-416, Dec. 1989 [doi>10.1016/0885-064X(89)90017-4]
• 14: David S. Johnson , Christos H. Papadimtriou , Mihalis Yannakakis, How easy is local search?, Journal of Computer and System Sciences, v.37 n.1, p.79-100, August 1988 [doi>10.1016/0022-0000(88)90046-3]
• 15: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 16: C. E. Lemke and J. T. Howson, Jr. "Equilibrium points of bimatrix games", SIAM J. Appl. Math. 12, pp. 413--423, 1964.
• 17: R. Lipton and E. Markakis. "Nash Equilibria via Polynomial Equations," Proceedings of LATIN, 2004.
• 18: Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
• 19: M. Littman, M. Kearns and S. Singh. "An Efficient Exact Algorithm for Single Connected Graphical Games," Proceedings of NIPS, 2002.
• 20: J. Nash. "Noncooperative Games," Annals of Mathematics, 54, 289--295, 1951.
• 21: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior, Princeton University Press, 1944.
• 22: M.J. Osborne and A. Rubinstein. A Course in Game Theory, MIT Press (1994).
• 23: Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
• 24: Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 25: Christos H. Papadimitriou, Computing correlated equilibria in multi-player games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060598]
• 26: Rahul Savani , Bernhard von Stengel, Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.258-267, October 17-19, 2004 [doi>10.1109/FOCS.2004.28]
• 27: Grant Schoenebeck , Salil Vadhan, The computational complexity of nash equilibria in concisely represented games, Proceedings of the 7th ACM conference on Electronic commerce, p.270-279, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134737]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Economics, Theory

Keywords:
Nash equilibrium, PPAD-completeness, complexity, game theory