On Nash-equilibria of approximation-stable games
Oct 13, 2010
In this work, we define the notion of games that are approximation-stable, meaning that all $\epsilon$-approximate equilibria are contained inside a small ball of radius $\delta$ around a true equilibrium, and investigate a number of their properties. Many natural small games such as matching pennies and rock-paper-scissors are indeed approximation stable. We show furthermore that there exist 2-player n-by-n approximation-stable games in which the Nash equilibrium and all approximate equilibria have support $\Omega(log n)$. In addition, we also show that all $(\epsilon,\delta)$ approximation-stable games must have an $\epsilon$-approximate equilibrium of support $O(\frac{\delta^{2-o(1)}}{\epsilon^2}log n)$, yielding a faster algorithm for computing approximate Nash-equilibria, for games which are approximation-stable.

This is joint work with Avrim Blum, Nina Balcan, Or Sheffet and Santosh Vempala.