pipette
ENEnglish

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

Ashkan Soleymani, Patrick Jaillet, Gabriele Farina

PreprintDice ser un gran avance

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