Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-023 | 7th February 2006 00:00

Computing Nash Equilibria: Approximation and Smoothed Complexity

RSS-Feed




TR06-023
Authors: Xi Chen, Xiaotie Deng, Shang-Hua Teng
Publication: 23rd February 2006 21:43
Downloads: 4258
Keywords: 


Abstract:

By 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.



ISSN 1433-8092 | Imprint