Metraipolis › archive › dc_46ba0c46e4ee
Analyzing the Interaction of Optimal Strategies in Mean-Payoff Bidding Games — arXiv:2608.07383
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.07383
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T09:50:10.400Z
- SHA-256 of the archived text
9dc247c57690200c0f5cd697989e83a63baedff0d2068f263642f3192844c8fd- Stable URL of this page
https://metraipolis.com/documento/dc_46ba0c46e4ee
How to cite
Analyzing the Interaction of Optimal Strategies in Mean-Payoff Bidding Games — arXiv:2608.07383 — arXiv (en), https://arxiv.org/abs/2608.07383 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_46ba0c46e4ee (Metraipolis archive dc_46ba0c46e4ee, sha256 9dc247c57690200c0f5cd697989e83a63baedff0d2068f263642f3192844c8fd)
BibTeX
@misc{dc46ba0c46e4ee,
title = {Analyzing the Interaction of Optimal Strategies in Mean-Payoff Bidding Games — arXiv:2608.07383},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.07383},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_46ba0c46e4ee; sha256 9dc247c57690200c0f5cd697989e83a63baedff0d2068f263642f3192844c8fd},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.07383. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A common assumption when designing an agent in a multi-agent system is that the other agents behave adversarially. This allows a designer to obtain the strongest guarantees when they have no control over nor knowledge about the other agents' behavior. However, when all agents are designed under this adversarial assumption, their actual interaction is not adversarial (e.g., when all players play defensively, no player actually attacks). In such settings, we would like to know what behavior arises in the multi-agent system. However, analyzing the interaction among agents is notoriously challenging, both mathematically and algorithmically. In this paper, we provide such an analysis, focusing on bidding games, played by two agents on a graph as follows. A token is placed on a vertex, and in each turn an auction (bidding) determines which agent moves the token, thus generating an infinite path that determines the agents' utilities. We consider mean-payoff objectives; each vertex is associated with a reward for each player, and the utility in an infinite play is the limit average of the rewards. We analyze the play that is generated when each agent follows a strategy that optimizes against an adversary, and consider the two known explicit constructions of optimal strategies. The technical challenge stems from the infinitely-many configurations of a bidding game and their complicated dynamics. We show that, under some restrictions, the generated play is ultimately periodic, and develop algorithms to compute the players' utilities in it. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-10 in cs.GT). Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Multiagent Systems (cs.MA). Pagina del lavoro: https://arxiv.org/abs/2608.07383 — 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-19T09:49:04.944Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-10?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).