Settling the complexity of computing two-player Nash equilibria

ABSTRACT

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 Daskalakis et al. [2006a] on the complexity of four-player Nash equilibria, settles a long standing open problem in algorithmic game theory. It also serves as a starting point for a series of results concerning the complexity of two-player Nash equilibria. In particular, we prove the following theorems:

—Bimatrix does not have a fully polynomial-time approximation scheme unless every problem in PPAD is solvable in polynomial time.

—The smoothed complexity of the classic Lemke-Howson algorithm and, in fact, of any algorithm for Bimatrix is not polynomial unless every problem in PPAD is solvable in randomized polynomial time.

Our results also have a complexity implication in mathematical economics:

—Arrow-Debreu market equilibria are PPAD-hard to compute.

REFERENCES

• 1: Tim Abbott , Daniel Kane , Paul Valiant, On the Complexity of Two-PlayerWin-Lose Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.113-122, October 23-25, 2005 [doi>10.1109/SFCS.2005.59]
• 2: Addario-Berry, L., Olver, N., and Vetta, A. 2007. A polynomial time algorithm for finding Nash equilibria in planar win-lose games. J. Graph Algor. Applica. 11, 1, 309--319.
• 3: Arrow, K., and Debreu, G. 1954. Existence of an equilibrium for a competitive economy. Econometrica 22, 265--290.
• 4: Imre Barany , Santosh Vempala , Adrian Vetta, Nash Equilibria in Random Games, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.123-131, October 23-25, 2005 [doi>10.1109/SFCS.2005.52]
• 5: Blum, L., Shub, M., and Smale, S. 1989. On a theory of computation over the real numbers; NP completeness, recursive functions and universal machines. Bull. AMS 21, 1 (July), 1--46.
• 6: Borgwardt, K.-H. 1982. The average number of steps required by the simplex method is polynomial. Z. Oper. Res. 26, 157--177.
• 7: Bosse, H., Byrka, J., and Markakis, E. 2007. New algorithms for approximate Nash equilibria in bimatrix games. In Proceedings of the 3rd International Workshop on Internet and Network Economics. 17--29.
• 8: Brouwer, L. 1910. Über Abbildung von Mannigfaltigkeiten. Math. Ann. 71, 97--115.
• 9: Chen, X., and Deng, X. 2005a. 3-Nash is PPAD-complete. In Electronic Colloquium in Computational Complexity. TR05--134.
• 10: Xi Chen , Xiaotie Deng, On algorithms for discrete and approximate brouwer fixed points, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060638]
• 11: Chen, X., and Deng, X. 2006. On the complexity of 2D discrete fixed point problem. In ICALP '06: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. 489--500.
• 12: Chen, X., Deng, X., and Teng, S.-H. 2006a. Sparse games are hard. In Proceedings of the 2nd Workshop on Internet and Network Economics. 262--273.
• 13: Chen, X., Huang, L.-S., and Teng, S.-H. 2006b. Market equilibria with hybrid linear-Leontief utilities. In Proceedings of the 2nd Workshop on Internet and Network Economics. 274--285.
• 14: Xi Chen , Xiaoming Sun , Shang-Hua Teng, Quantum Separation of Local Search and Fixed Point Computation, Proceedings of the 14th annual international conference on Computing and Combinatorics, June 27-29, 2008, Dalian, China [doi>10.1007/978-3-540-69733-6_18]
• 15: Xi Chen , Shang-Hua Teng, Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.124-134, October 21-23, 2007 [doi>10.1109/FOCS.2007.53]
• 16: Xi Chen , Shang-Hua Teng , Paul Valiant, The approximation complexity of win-lose games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.159-168, January 07-09, 2007, New Orleans, Louisiana
• 17: 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]
• 18: Condon, A., Edelsbrunner, H., Emerson, E., Fortnow, L., Haber, S., Karp, R., Leivant, D., Lipton, R., Lynch, N., Parberry, I., Papadimitriou, C., Rabin, M., Rosenberg, A., Royer, J., Savage, J., Selman, A., Smith, C., Tardos, E., and Vitter, J. 1999. Challenges for theory of computing: Report of an NSF-sponsored workshop on research in theoretical computer science. SIGACT News 30, 2, 62--76.
• 19: Conitzer, V., and Sandholm, T. 2003. Complexity results about Nash equilibria. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). ACM, New York, 765--771.
• 20: 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]
• 21: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Communications of the ACM, v.52 n.2, February 2009 [doi>10.1145/1461928.1461951]
• 22: Daskalakis, C., Mehta, A., and Papadimitriou, C. H. 2006b. A note on approximate Nash equilibria. In Proceedings of the 2nd Workshop on Internet and Network Economics. 297--306.
• 23: Constantinos Daskalakis , Aranyak Mehta , Christos Papadimitriou, Progress in approximate nash equilibria, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250962]
• 24: Daskalakis, C., and Papadimitriou, C. 2005. Three-player games are hard. In Electronic Colloquium in Computational Complexity. TR05--139.
• 25: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of price equilibria, Journal of Computer and System Sciences, v.67 n.2, p.311-324, September 2003 [doi>10.1016/S0022-0000(03)00011-4]
• 26: Herbert Edelsbrunner , M. J. Ablowitz , S. H. Davis , E. J. Hinch , A. Iserles , J. Ockendon , P. J. Olver, Geometry and Topology for Mesh Generation (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
• 27: 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]
• 28: Tomas Feder , Hamid Nazerzadeh , Amin Saberi, Approximating nash equilibria using small-support strategies, Proceedings of the 8th ACM conference on Electronic commerce, June 11-15, 2007, San Diego, California, USA [doi>10.1145/1250910.1250961]
• 29: Friedl, K., Ivanyos, G., Santha, M., and Verhoeven, F. 2005. On the black-box complexity of Sperner's lemma. In Proceedings of the 15th International Symposium on Fundamentals of Computation Theory. 245--257.
• 30: Friedl, K., Ivanyos, G., Santha, M., and Verhoeven, F. 2006. Locally 2-dimensional Sperner problems complete for the polynomial parity argument classes. In Proceedings of the 6th Conference on Algorithms and Complexity. 380--391.
• 31: Gilboa, I., and Zemel, E. 1989. Nash and correlated equilibria: Some complexity considerations. Games Econ. Behav. 1, 1, 80--93.
• 32: 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]
• 33: P. E. Haxell , G. T. Wilfong, A fractional model of the border gateway protocol (BGP), Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.193-199, January 20-22, 2008, San Francisco, California
• 34: 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]
• 35: Holt, C., and Roth, A. 2004. The Nash equilibrium: A perspective. Proc. Nat. Acad. Sci. USA 101, 12, 3999--4002.
• 36: Huang, L.-S., and Teng, S.-H. 2007. On the approximation and smoothed complexity of Leontief market equilibria. In Proceedings of the 1st International Frontiers of Algorithmics Workshop. 96--107.
• 37: David S. Johnson, The NP-completeness column: Finding needles in haystacks, ACM Transactions on Algorithms (TALG), v.3 n.2, p.24-es, May 2007 [doi>10.1145/1240233.1240247]
• 38: Kakutani, S. 1941. A generalization of Brouwer's fixed point theorem. Duke Math. J. 8, 457--459.
• 39: Ravi Kannan , Thorsten Theobald, Games of fixed rank: a hierarchy of bimatrix games, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.1124-1132, January 07-09, 2007, New Orleans, Louisiana
• 40: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 41: 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
• 42: Khachian, L. 1979. A polynomial algorithm in linear programming. Doklady Akademia Nauk SSSR 244, 1093--1096, (English translation in Soviet Math. Dokl. 20, 191--194).
• 43: Klee, V., and Minty, G. 1972. How good is the simplex algorithm? In Inequalities -- III, O. Shisha, Ed. Academic Press, Orlando, FL, 159--175.
• 44: Ker-I Ko, Complexity theory of real functions, Birkhauser Boston Inc., Cambridge, MA, 1991
• 45: Kontogiannis, S., Panagopoulou, P., and Spirakis, P. 2006. Polynomial algorithms for approximating Nash equilibria of bimatrix games. In Proceedings of the 2nd Workshop on Internet and Network Economics. 286--296.
• 46: Nikolaos Laoutaris , Laura J. Poplawski , Rajmohan Rajaraman , Ravi Sundaram , Shang-Hua Teng, Bounded budget connection (BBC) games or how to make friends and influence people, on a budget, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400774]
• 47: Lemke, C. 1965. Bimatrix equilibrium points and mathematical programming. Manag. Sci. 11, 681--689.
• 48: Lemke, C., and Howson, Jr., J. 1964. Equilibrium points of bimatrix games. J. Soc. Indust. Appl. Math. 12, 413--423.
• 49: Leonard, R. 1994. Reading Cournot, reading Nash: The creation and stabilisation of the Nash equilibrium. Economic Journal 104, 424, 492--511.
• 50: Lipton, R., and Markakis, E. 2004. Nash equilibria via polynomial equations. In Proceedings of the 6th Latin American Symposium on Theoretical Informatics. 413--422.
• 51: 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]
• 52: Megiddo, N. 1988. A note on the complexity of P-matrix LCP and computing an equilibrium. Res. Rep. RJ6439 IBM Almaden Research Center, San Jose.
• 53: Nimrod Megiddo , Christos H. Papadimitriou, On total functions, existence theorems and computational complexity, Theoretical Computer Science, v.81 n.2, p.317-324, April 30 1991 [doi>10.1016/0304-3975(91)90200-L]
• 54: Morgenstern, O., and von Neumann, J. 1947. Theory of Games and Economic Behavior. Princeton University Press, Princeton, NJ.
• 55: Nash, J. 1950. Equilibrium points in n-person games. Proc. Nat. Acad. USA 36, 1, 48--49.
• 56: Nash, J. 1951. Noncooperative games. Ann. Math. 54, 289--295.
• 57: Papadimitriou, C. 1991. On inefficient proofs of existence and complexity classes. In Proceedings of the 4th Czechoslovakian Symposium on Combinatorics.
• 58: 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]
• 59: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 60: Poplawski, L. J., Rajaraman, R., Sundaram, R., and Teng, S.-H. 2008. Preference games and personalized equilibria, with applications to fractional BGP. In arXiv:0812.0598.
• 61: Tuomas Sandholm, Issues in computational Vickrey auctions, International Journal of Electronic Commerce, v.4 n.3, p.107-129, March 2000
• 62: 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, p.258-267, October 17-19, 2004 [doi>10.1109/FOCS.2004.28]
• 63: Scarf, H. 1967a. The approximation of fixed points of a continuous mapping. SIAM J. Appl. Math. 15, 997--1007.
• 64: Scarf, H. 1967b. On the computation of equilibrium prices. In Ten Economic Studies in the Tradition of Irving Fisher, W. Fellner, Ed. Wiley, New York.
• 65: Sperner, E. 1928. Neuer Beweis fur die Invarianz der Dimensionszahl und des Gebietes. Abhandlungen aus dem Mathematischen Seminar Universitat Hamburg 6, 265--272.
• 66: Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004 [doi>10.1145/990308.990310]
• 67: Spielman, D., and Teng, S.-H. 2006. Smoothed analysis of algorithms and heuristics: Progress and open questions. In Foundations of Computational Mathematics, L. Pardo, A. Pinkus, E. Süli, and M. Todd, Eds. Cambridge University Press, Cambridge, MA, 274--342.
• 68: Tsaknakis, H., and Spirakis, P. 2007. An optimization approach for approximate Nash equilibria. In Proceedings of the 3rd International Workshop on Internet and Network Economics. 42--56.
• 69: von Neumann, J. 1928. Zur theorie der gesellschaftsspiele. Math. Ann. 100, 295--320.
• 70: Wilson, R. 1971. Computing equilibria of n-person games. SIAM J. Appl. Math. 21, 80--87.
• 71: Ye, Y. 2005. Exchange market equilibria with Leontief's utility: Freedom of pricing leads to rationality. In Proceedings of the 1st Workshop on Internet and Network Economics. 14--23.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Economics, Theory

Keywords:
Arrow-Debreu market, Brouwer's fixed point, Lemke-Howson algorithm, Nash equilibrium, PPAD-completeness, Sperner's lemma, Two-player game, smoothed analysis