Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games

Ashkan Soleymani, Patrick Jaillet, Gabriele Farina

We give the first unconditional family of polynomial-time algorithms that breaks the $1/3$ approximation barrier for symmetric bimatrix games. For every fixed $δ>0$, an algorithm in this family computes a symmetric $(1-1/\sqrt{2}+δ)$-approximate Nash equilibrium, improving on the previous best guarantee of $(1/3+δ)$ due to Kontogiannis and Spirakis [2011].