Metraipolis › archive › dc_707da3312e04

Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria — arXiv:2611.06076

Source: arXiv (en)
Original: https://arxiv.org/abs/2611.06076
License (as archived): CC0-1.0
Archived: 2026-11-05T18:20:21.654Z
SHA-256 of the archived text: 4021fb8d51fae531e2cba7eec245dd9c3ffd425d84c167fca87abb35c852cf2d
Stable URL of this page: https://metraipolis.com/documento/dc_707da3312e04

How to cite

Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria — arXiv:2611.06076 — arXiv (en), https://arxiv.org/abs/2611.06076 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_707da3312e04 (Metraipolis archive dc_707da3312e04, sha256 4021fb8d51fae531e2cba7eec245dd9c3ffd425d84c167fca87abb35c852cf2d)

BibTeX

@misc{dc707da3312e04,
  title = {Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash Equilibria — arXiv:2611.06076},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.06076},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_707da3312e04; sha256 4021fb8d51fae531e2cba7eec245dd9c3ffd425d84c167fca87abb35c852cf2d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.06076. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Computation of Nash equilibria is a central problem in algorithmic game theory, yet exact equilibrium computation is $\mathsf{PPAD}$-complete even for two-player games. This hardness motivates the study of polynomial-time algorithms for approximate Nash equilibria. While substantial progress has been made for two-player and three-player games, existing algorithms for general $m$-player games have largely relied on repeatedly applying one-player extension starting from improved fixed-player algorithms. Such improvements can at best strengthen the classical $1-1/m$ guarantee to $1-1/(m-c)$, for some constant $c$ independent of $m$. We break this long-standing barrier by developing an iterative algorithm that directly tackles general $m$-player games and achieves a $(1-(\sigma_{\star}-\epsilon)/m)$-approximation for fixed $\epsilon > 0$ and sufficiently large $m$, where $\sigma_\star\approx1.5867$ is the unique root in $(1,2)$ of $\sigma_\star^3-19\sigma_\star^2+27\sigma_\star+1=0$. Our approach rests on a novel iterative descent-and-repair framework that allows multiple rounds of repair. At the heart of our analysis is a new potential function inspired by continuous-time dynamics, which certifies progress across iterations and ensures polynomial-time termination. Our results highlight the power of history-aware, iterative repair in breaking approximation barriers for multiplayer games.

Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno).
Categorie arXiv: Computer Science and Game Theory (cs.GT).
Pagina del lavoro: https://arxiv.org/abs/2611.06076 — 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-11-05T18:14:18.992Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).