Metraipolis › archive › dc_e730e988bc03

Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees — arXiv:2609.11863

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.11863
License (as archived)
CC0-1.0
Archived
2026-10-16T05:20:31.619Z
SHA-256 of the archived text
320ee0779acbdadf5ee1053f0cd35765784610936192eb93edc67889fafe8e75
Stable URL of this page
https://metraipolis.com/documento/dc_e730e988bc03

How to cite

Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees — arXiv:2609.11863 — arXiv (en), https://arxiv.org/abs/2609.11863 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e730e988bc03 (Metraipolis archive dc_e730e988bc03, sha256 320ee0779acbdadf5ee1053f0cd35765784610936192eb93edc67889fafe8e75)
BibTeX
@misc{dce730e988bc03,
  title = {Truncated Noisy Best-Response Algorithms: Toward Game Theoretic Learning with Safety Guarantees — arXiv:2609.11863},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.11863},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e730e988bc03; sha256 320ee0779acbdadf5ee1053f0cd35765784610936192eb93edc67889fafe8e75},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.11863. 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 maximization objectives. It is known for such problems that the Nash equilibria for the corresponding game are always within 50% of the optimal, but that the equilibria which achieve this worst-case bound are not stable. To exploit this instability, we propose a family of algorithms which we call Truncated Noisy Best-Response (TNBR) Algorithms. These algorithms are flexibly characterized by agents asynchronously and stochastically selecting actions from a neighbourhood of their best response payoffs. We compute bounds on the recurrent classes of TNBR algorithms' associated Markov chains. Our bounds fall into two categories: first, "Performance" bounds ensure that TNBR algorithms always have a high-value recurrent state; second, "Safety" bounds ensure that TNBR algorithms never have arbitrarily-bad recurrent states. Furthermore, these two types of bounds are linked by a waterbed-like effect: every game with a poor Safety guarantee necessarily has a favorable Performance guarantee.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-11 in cs.MA).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Multiagent Systems (cs.MA); Systems and Control (eess.SY).
Pagina del lavoro: https://arxiv.org/abs/2609.11863 — 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:15:07.146Z dalla pagina https://arxiv.org/catchup/cs.MA/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).