The complexity of computing a Nash equilibrium

ABSTRACT

How long does it take until economic agents converge to an equilibrium? By studying the complexity of the problem of computing a mixed Nash equilibrium in a game, we provide evidence that there are games in which convergence to such an equilibrium takes prohibitively long. Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are NP-hard. However, the concept of NP-hardness cannot be applied to the rare problems where "every instance has a solution"---for example, in the case of games Nash's theorem asserts that every game has a mixed equilibrium (now known as the Nash equilibrium, in honor of that result). We show that finding a Nash equilibrium is complete for a class of problems called PPAD, containing several other known hard problems; all problems in PPAD share the same style of proof that every instance has a solution.

REFERENCES

• 1: Bubelis, V. On equilibria in finite games. Int. J. Game Theory 8, 2 (1979), 65--79.
• 2: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 3: Xi Chen , Xiaotie Deng , Shang-Hua Teng, Computing Nash Equilibria: Approximation and Smoothed Complexity, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.603-612, October 21-24, 2006 [doi>10.1109/FOCS.2006.20]
• 4: Conitzer, V., Sandholm, T. Complexity results about Nash equilibria. Proceedings of IJCAI (2003).
• 5: Daskalakis, C., Papadimitriou, C.H. Three-player games are hard. Electronic Colloquium in Computational Complexity, TR05-139, 2005.
• 6: Constantinos Daskalakis , Christos H. Papadimitriou, Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.25-34, October 25-28, 2008 [doi>10.1109/FOCS.2008.84]
• 7: 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]
• 8: 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]
• 9: Kousha Etessami , Mihalis Yannakakis, On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract), Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.113-123, October 21-23, 2007 [doi>10.1109/FOCS.2007.48]
• 10: Friedman, E., Shenker, S. Learning and implementation on the Internet. Department of Economics, Rutgers University, 1997.
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: Gilboa, I., Zemel, E. Nash and correlated equilibria: some complexity considerations. Games Econ. Behav. (1989).
• 13: 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]
• 14: Sergiu Hart , Yishay Mansour, The communication complexity of uncoupled nash equilibrium procedures, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250843]
• 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: Knaster, B., Kuratowski, C., mazurkiewicz, S. Ein beweis des fixpunktsatzes für n-dimensionale simplexe. Fundamenta Mathematicae 14, (1929), 132--137.
• 17: Lemke, C.E., Howson, Jr.J.T., Equilibrium points of bimatrix games. SIAM J. Appl. Math, 12, (1964), 413--423.
• 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: Nash, J. Noncooperative games. Ann. Math. 54, (1951), 289--295.
• 20: 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]
• 21: Scarf, H.E. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15, (1967), 1328--1343.
• 22: Yoav Shoham, Computer science and game theory, Communications of the ACM, v.51 n.8, August 2008 [doi>10.1145/1378704.1378721]

INDEX TERMS

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