Metraipolis › archive › dc_059e2013aa5a
The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games — arXiv:2609.07136
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.07136
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:30:07.481Z
- SHA-256 of the archived text
92f81d7d5a4e09feffe7e96b1f432e10898fad114ff2d0e0e90f7687173c9d68- Stable URL of this page
https://metraipolis.com/documento/dc_059e2013aa5a
How to cite
The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games — arXiv:2609.07136 — arXiv (en), https://arxiv.org/abs/2609.07136 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_059e2013aa5a (Metraipolis archive dc_059e2013aa5a, sha256 92f81d7d5a4e09feffe7e96b1f432e10898fad114ff2d0e0e90f7687173c9d68)
BibTeX
@misc{dc059e2013aa5a,
title = {The Fine-Grained Complexity of Approximate Nash Equilibrium and Free Games — arXiv:2609.07136},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.07136},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_059e2013aa5a; sha256 92f81d7d5a4e09feffe7e96b1f432e10898fad114ff2d0e0e90f7687173c9d68},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.07136. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the fine-grained complexity of computing approximate Nash equilibria and approximating the value of free games in the regime where the approximation error vanishes. Under the PCP for PPAD and ETH for PPAD conjectures, we show that computing $\varepsilon$-approximate Nash equilibria in 2-player $N$-action normal-form games requires time $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$, thus showing that the classical Lipton-Markakis-Mehta algorithm (2003) is optimal through all regimes of $\varepsilon = \omega(1/\sqrt{N})$. While such optimality was known in the constant-$\varepsilon$ regime (Rubinstein, 2016), previous work could only rule out significantly smaller running times of $N^{O(\log(N)/\varepsilon)}$ in the regime $\varepsilon = o(1)$. Using similar techniques, we then establish an analogous tight lower bound of $N^{(\log(N)/\varepsilon^2)^{1-o(1)}}$ under ETH for $\varepsilon$-additive value estimation in free games, when $\varepsilon \geq 2^{-o(\sqrt{\log N})}$, answering a question of Aaronson, Impagliazzo, and Moshkovitz (2014).
Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-09 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.07136 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:06:09.171Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).