Reducibility among equilibrium problems

ABSTRACT

We address the fundamental question of whether the Nash equilibria of a game can be computed in polynomial time. We describe certain efficient reductions between this problem for normal form games with a fixed number of players and graphical games with fixed degree. Our main result is that the problem of solving a game for any constant number of players, is reducible to solving a 4-player game.

REFERENCES

• 1: X. Chen and X. Deng. "3-NASH is PPAD-Complete", Electronic Colloquium in Computational Complexity TR-05-134, 2005.
• 2: X. Chen and X. Deng. "Settling the Complexity of 2-Player Nash-Equilibrium", Electronic Colloquium in Computational Complexity TR-05-140, 2005.
• 3: B. Codenotti, A. Saberi, K. Varadarajan, Y. Ye. "Leontief Economies Encode Nonzero Sum Two-Player Games" , Electronic Colloquium in Computational Complexity TR-05-055, 2005.
• 4: V. Conitzer and T. Sandholm. "Complexity Results about Nash Equilibria", Proceedings of 18th IJCAI, pp. 765--771, Acapulco, Mexico, 2003.
• 5: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 6: K. Daskalakis and C.H. Papadimitriou. "The Complexity of Games on Highly Regular Graphs", 13th Annual Symposium on Algorithms (ESA) 2005.
• 7: K. Daskalakis and C.H. Papadimitriou. "Three-Player Games are Hard", Electronic Colloquium in Computational Complexity TR-05-139, 2005.
• 8: R.S. Datta. Algebraic Methods in Game Theory, PhD Dissertation, Department of Mathematics, U.C. Berkeley, 2003.
• 9: Edith Elkind , Leslie Ann Goldberg , Paul Goldberg, Nash equilibria in graphical games on trees revisited, Proceedings of the 7th ACM conference on Electronic commerce, p.100-109, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134719]
• 10: 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]
• 11: Georg Gottlob , Gianluigi Greco , Francesco Scarcello, Pure Nash equilibria: hard and easy games, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846269]
• 12: I. Gilboa and E. Zemel. "Nash and correlated equilibria: Some complexity considerations", Games and Economic Behavior, 1989.
• 13: 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
• 14: R. Lipton and E. Markakis. "Nash Equilibria via Polynomial Equations", Proceedings of the 6th Latin American Symposium on Theoretical Informatics (LATIN'04), pp. 413--422, Buenos Aires, Argentina, 2004.
• 15: M. Littman, M. Kearns and S. Singh. "An Efficient Exact Algorithm for Single Connected Graphical Games", Proceedings of 14th NIPS (Advances in Neural Information Processing Systems), pp. 817--823, 2002.
• 16: J. Nash. "Noncooperative Games", Annals of Mathematics, 54, 289--295, 1951.
• 17: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior, Princeton University Press, 1944.
• 18: 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]
• 19: 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]
• 20: G.R. Schoenebeck and S.P. Vadhan. "The Computational Complexity of Nash Equilibria in Concisely Represented Games", Electronic Colloquiium on Computational Complexity TR-05-052, 2005.

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