Computer Science – Computer Science and Game Theory
Scientific paper
2007-04-12
Computer Science
Computer Science and Game Theory
53 pages 2 figures
Scientific paper
We settle a long-standing open question in algorithmic game theory. 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. This is the first of a series of results concerning the complexity of 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 demonstrate that, even in the simplest form of non-cooperative games, equilibrium computation and approximation are polynomial-time equivalent to fixed point computation. Our results also have two broad complexity implications in mathematical economics and operations research: Arrow-Debreu market equilibria are PPAD-hard to compute. The P-Matrix Linear Complementary Problem is computationally harder than convex programming unless every problem in PPAD is solvable in polynomial time.
Chen Xi
Deng Xiaotie
Teng Shang-Hua
No associations
LandOfFree
Settling the Complexity of Computing Two-Player Nash Equilibria does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Settling the Complexity of Computing Two-Player Nash Equilibria, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Settling the Complexity of Computing Two-Player Nash Equilibria will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-677575