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

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