Settling the complexity of computing two-player Nash equilibria
Top Cited Papers
- 19 May 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 56 (3), 1-57
- https://doi.org/10.1145/1516512.1516516
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.Keywords
Funding Information
- National Natural Science Foundation of China (60553001)
- Division of Computing and Communication Foundations (DMS-0635607CCF-0832797)
- National Science Foundation (CCR-0311430CCR-0635102ITR CCR-0325630)
- Ministry of Science and Technology of the People's Republic of China (2003CB3178072004CB318108, 2007CB8079002007CB807901)
- Division of Mathematical Sciences (DMS-0635607CCF-0832797)
This publication has 49 references indexed in Scilit:
- A Polynomial Time Algorithm for Finding Nash Equilibria in Planar Win-Lose GamesJournal of Graph Algorithms and Applications, 2007
- On the Complexity of 2D Discrete Fixed Point ProblemLecture Notes in Computer Science, 2006
- Market Equilibria with Hybrid Linear-Leontief UtilitiesLecture Notes in Computer Science, 2006
- Sparse Games Are HardLecture Notes in Computer Science, 2006
- Nash Equilibria in Random GamesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- On the Complexity of Two-PlayerWin-Lose GamesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- On algorithms for discrete and approximate brouwer fixed pointsPublished by Association for Computing Machinery (ACM) ,2005
- On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machinesBulletin of the American Mathematical Society, 1989
- Existence of an Equilibrium for a Competitive EconomyEconometrica, 1954
- Über Abbildung von MannigfaltigkeitenMathematische Annalen, 1911