Metraipolis › archive › dc_e225af53bdc7

Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents — arXiv:2609.18309

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.18309
License (as archived)
CC0-1.0
Archived
2026-10-15T14:08:40.091Z
SHA-256 of the archived text
092877504cbb5fc0b0874c208b8e831733d2a9321d25b3c6c6997b52b8f6e0d8
Stable URL of this page
https://metraipolis.com/documento/dc_e225af53bdc7

How to cite

Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents — arXiv:2609.18309 — arXiv (en), https://arxiv.org/abs/2609.18309 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_e225af53bdc7 (Metraipolis archive dc_e225af53bdc7, sha256 092877504cbb5fc0b0874c208b8e831733d2a9321d25b3c6c6997b52b8f6e0d8)
BibTeX
@misc{dce225af53bdc7,
  title = {Equilibria of Round-Robin: Computational Hardness and Fairness for Few Subadditive Agents — arXiv:2609.18309},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18309},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_e225af53bdc7; sha256 092877504cbb5fc0b0874c208b8e831733d2a9321d25b3c6c6997b52b8f6e0d8},
  year = {2026}
}

Archived text

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

The round-robin procedure is a simple and well-studied fair division mechanism where agents pick goods in turns. Motivated by draft mechanisms in sports leagues, we investigate strategic behaviour in online round-robin for subadditive agents. This gives rise to an extensive-form game, and we study the computational problem of computing a subgame perfect Nash equilibrium (SPNE). We show that for just two submodular agents, computing an SPNE is $\mathsf{PSPACE}$-hard. Even for the class of $\mathit{OXS}$ utilities, which are a special case of submodular utilities, computing an SPNE remains $\mathsf{NP}$-hard for a small number of agents. We complement our computational results with normative results. We show that for just three additive agents, there exist instances where every equilibrium violates EF1. This separates the online and the direct revelation games. On the positive side, we show that for additive agents every equilibrium allocation is proportional up to one good (PROP1) and for two additive agents it is also EF1. Finally, by showing that round-robin is bossy at equilibrium, we prove that the number of equilibrium allocations can be exponential even if agents have lexicographic preferences.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-17 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.18309 — 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-15T13:50:52.121Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).