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).