Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games
En palabras de los autores
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].
Resultado principalLimitación que admiten los autores
Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: ACM-SIAM Symposium on Discrete Algorithms (SODA), 2027