Algorithms improve approximate nash equilibria for symmetric games
Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games
Computer Science and Game TheoryMachine Learning
Summary
Finding approximate Nash equilibria is important in understanding how players might behave in strategic games where exact solutions are hard to find. Before, the best known algorithms could only guarantee an approximate equilibrium with an accuracy threshold of about 1/3. The authors present new polynomial-time algorithms that improve this threshold to roughly 0.29 for symmetric bimatrix games. This advancement means the solution is closer to a true equilibrium, improving our understanding of strategic interactions in these games.
What this means in practice
- •For game developers: Use improved algorithms to model player interactions with better approximations of stable strategies in symmetric competitive settings.
- •For economic modelers: Incorporate more accurate approximate equilibria in symmetric market simulations to predict strategic decision-making.
A theory result. No direct application yet.
Authors
Ashkan Soleymani, Patrick Jaillet, Gabriele Farina
Abstract
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].