Access Restriction

Author Chen, Xi ♦ Deng, Xiaotie ♦ Teng, Shang-Hua
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2009
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Arrow-Debreu market ♦ Brouwer's fixed point ♦ Lemke-Howson algorithm ♦ Nash equilibrium ♦ PPAD-completeness ♦ Sperner's lemma ♦ Two-player game ♦ Smoothed analysis
Abstract We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class $\textbf{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 $\textbf{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 $\textbf{PPAD}$ is solvable in randomized polynomial time. Our results also have a complexity implication in mathematical economics: —Arrow-Debreu market equilibria are $\textbf{PPAD}-hard$ to compute.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2009-05-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 56
Issue Number 3
Page Count 57
Starting Page 1
Ending Page 57

Open content in new tab

   Open content in new tab
Source: ACM Digital Library