Computing Nash Equilibria: Approximation and Smoothed Complexity
| dc.creator | Chen, Xi | |
| dc.creator | Deng, Xiaotie | |
| dc.creator | Teng, Shang-Hua | |
| dc.date | 2006-02-11 | |
| dc.date | 2006-02-22 | |
| dc.date.accessioned | 2026-07-07T07:02:30Z | |
| dc.date.available | 2026-07-07T07:02:30Z | |
| dc.description | We show that the BIMATRIX game does not have a fully polynomial-time approximation scheme, unless PPAD is in P. In other words, no algorithm with time polynomial in n and 1/εcan compute an ε-approximate Nash equilibrium of an n by nbimatrix game, unless PPAD is in 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 PPAD-complete. Furthermore, we prove, unless PPAD is in 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/σunder perturbations with magnitude σ. Our result answers a major open question in the smoothed analysis of algorithms and the approximation of Nash equilibria. | |
| dc.identifier | https://arxiv.org/abs/cs/0602043 | |
| dc.identifier | http://arxiv.org/abs/cs/0602043 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/108621 | |
| dc.subject | Computational Complexity | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | F.1.2; F.1.3; F.2; F.2.3 | |
| dc.title | Computing Nash Equilibria: Approximation and Smoothed Complexity | |
| dc.type | text |