We advance significantly beyond the recent progress on the algorithmic complexity of Nash equilibria by solving two major open problems in the approximation of Nash equilibria and in the smoothed analysis of algorithms. • We show that no algorithm with complexity poly(n, 1 ) can compute an -approximate Nash equilibrium in a two-player game, in which each player has n pure strategies, unless PPAD ⊆ P. In other words, the problem of computing a Nash equilibrium in a twoplayer game does not have a fully polynomial-time approximation scheme unless PPAD ⊆ P. • We prove that no algorithm for computing a Nash equilibrium in a two-player game can have smoothed complexity poly(n, 1 σ ) under input perturbation of magnitude σ, unless PPAD ⊆ RP. In particular, the smoothed complexity of the classic Lemke-Howson algorithm is not polynomial unless PPAD ⊆ RP. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional hypergrid with constant side-length, and show that it can host the embedding of the proof structure of any PPAD problem. We prove a key geometric lemma for finding a discrete fixed-point, a new concept defined on n + 1 vertices of a unit hypercube. This lemma enables us to overcome the curse of dimensionality in reasoning about fixed-points in high dimensions. 1 As an -approximate Nash equilibrium (x, y) of game (A, B) becomes a c · -approximate Nash equilibrium in game (cA, cB) for c > 0. Following Lipton, Markakis, and Mehta [16], we normalize the matrices A and B so that all their entries are between 0 and 1, or between -1 and 1 when studying -approximate Nash equilibria.
Chen, Deng and Teng REF showed that approximating Nash equilibrium is also hard.
Computing Nash Equilibria: Approximation and Smoothed Complexity
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
Computer Science Mathematics