Volume 13 (2017) Article 13 pp. 1-31
Nash Equilibria in Perturbation-Stable Games
Revised: August 30, 2017
Published: November 13, 2017
$\newcommand{\poly}{\mathrm{poly}}$
For uniformly stable games, where the equilibria fluctuate at most quasi-linearly in the extent of the perturbation, we get a particularly dramatic improvement. Here, we achieve a fully quasi-polynomial-time approximation scheme, that is, we can find $1/\poly(n)$-approximate equilibria in quasi-polynomial time. This is in marked contrast to the general class of bimatrix games for which finding such approximate equilibria is PPAD-hard. In particular, under the (widely believed) assumption that PPAD is not contained in quasi-polynomial time, our results imply that such uniformly stable games are inherently easier for computation of approximate equilibria than general bimatrix games.