Theory Lunch

On Nash-equilibria of approximation-stable games

Prankal Awasthi

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 \left(logn\right)$. In addition, we also show that all $(\epsilon ,\delta )$ approximation-stable games must have an $\epsilon$-approximate equilibrium of support $O\left(\frac{{\delta }^{2-o\left(1\right)}}{{\epsilon }^2}logn\right)$, 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.