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.

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