ECCC-Report TR06-023https://eccc.weizmann.ac.il/report/2006/023Comments and Revisions published for TR06-023en-usThu, 23 Feb 2006 21:43:30 +0200
Paper TR06-023
| Computing Nash Equilibria: Approximation and Smoothed Complexity |
Xi Chen,
Xiaotie Deng,
Shang-Hua Teng
https://eccc.weizmann.ac.il/report/2006/023By proving that the problem of computing a $1/n^{\Theta(1)}$-approximate Nash equilibrium remains \textbf{PPAD}-complete, we show that the BIMATRIX game is not likely to have a fully polynomial-time approximation scheme. In other words, no algorithm with time polynomial in $n$ and $1/\epsilon$ can compute an $\epsilon$-approximate Nash equilibrium of an $n\times n$ bimatrix game, unless $\textbf{PPAD}\subseteq\textbf{P}$. Instrumental to our proof, we introduce a new discrete fixed-point problem on a high-dimensional cube with a constant side-length, such as on an $n$-dimensional cube with side-length $7$, and show that they are \textbf{PPAD}-complete.
Furthermore, we prove that it is unlikely, unless $\textbf{PPAD}\subseteq\textbf{RP}$, that the smoothed complexity of the Lemke-Howson algorithm or any algorithm for computing a Nash equilibrium of a bimatrix game is polynomial in $n$ and $1/\sigma$ under perturbations with magnitude $\sigma$. Our result answers a major open question in the smoothed analysis of algorithms and the approximation of Nash equilibria.
Thu, 23 Feb 2006 21:43:30 +0200https://eccc.weizmann.ac.il/report/2006/023