Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games
In the authors' words
We give the first unconditional family of polynomial-time algorithms that breaks the approximation barrier for symmetric bimatrix games. For every fixed , an algorithm in this family computes a symmetric -approximate Nash equilibrium, improving on the previous best guarantee of due to Kontogiannis and Spirakis [2011].
Main resultLimitation the authors admit
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027