Metraipolis › archive › dc_beeaf19070e7
ABRA: An algorithm which cannot converge to low-quality Nash equilibria — arXiv:2609.11889
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.11889
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T05:45:10.945Z
- SHA-256 of the archived text
891de7aed91d6913a910effae9438d21175f31b138dd36dc4bd24f223a3194f8- Stable URL of this page
https://metraipolis.com/documento/dc_beeaf19070e7
How to cite
ABRA: An algorithm which cannot converge to low-quality Nash equilibria — arXiv:2609.11889 — arXiv (en), https://arxiv.org/abs/2609.11889 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_beeaf19070e7 (Metraipolis archive dc_beeaf19070e7, sha256 891de7aed91d6913a910effae9438d21175f31b138dd36dc4bd24f223a3194f8)
BibTeX
@misc{dcbeeaf19070e7,
title = {ABRA: An algorithm which cannot converge to low-quality Nash equilibria — arXiv:2609.11889},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.11889},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_beeaf19070e7; sha256 891de7aed91d6913a910effae9438d21175f31b138dd36dc4bd24f223a3194f8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11889. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider a game theoretic approach to solve multi-agent coordination problems with submodular objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal. A recent work further shows that the equilibria which achieve this worst-case bound are not stable. Leveraging this, we design an Approximate Best Response Algorithm (ABRA) governed by a noise parameter and a rationality parameter. The noise allows ABRA to escape the bad equilibria and the rationality parameter balances any degradation in the objective function caused by the noise. We show for any two-player game that if ABRA converges to a Nash equilibrium, its system objective value is strictly more than 50% of optimal plus a term controlled by the noise parameter. Otherwise, ABRA converges to some recurrent class: if a recurrent class contains any action profile yielding system objective less than 50% of the optimal, the class must also contain either the optimal action profile or an action profile yielding system objective strictly more than 50\% of the optimal by the same amount in addition to a factor controlled by noise parameter. The time that ABRA spends in such action profiles can be controlled using the rationality parameter. Using numerical simulations, we show that the minimum expected objective function is typically well above half of the optimal. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-11 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2609.11889 — 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-16T05:29:38.358Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).