Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games
Overview & Synopsis
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].
Indexed from repository: arXiv
(
arxiv.org)
Keyboard Shortcuts:
← / → for pages • + / - for zoom • 0 to fit width
Powered by Mozilla PDF.js v3.11
Document Information
| Document Title | Breaking the 1/3 Barrier for Approximate Nash Equilibria in Symmetric Bimatrix Games |
|---|---|
| Author / Organization | Ashkan Soleymani, Patrick Jaillet, Gabriele Farina |
| Subject & Discipline | cs.GT |
| Categories | Science & Mathematics |
| Publication Year | 2026 |
| License / Rights | arXiv Open Access / Creative Commons |
| Resource Verification | Listed PDF (Verification Pending) |
| Original Host Website |
arXiv
(arxiv.org)
|
| File Format | application/pdf (Portable Document Format) |
| Language | EN |
| Catalog ID | DOC-274836 |
| Original Source Link | Visit Source Page on arxiv.org » |