Metraipolis › archive › dc_de8ed7be6004
On the Convergence of Iterated Round Robin — arXiv:2610.23040
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.23040
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T08:44:33.616Z
- SHA-256 of the archived text
10e49f1c4d931ecd6a21eb92631dfa6f1502a53738553a332cd00330015bc6ad- Stable URL of this page
https://metraipolis.com/documento/dc_de8ed7be6004
How to cite
On the Convergence of Iterated Round Robin — arXiv:2610.23040 — arXiv (en), https://arxiv.org/abs/2610.23040 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_de8ed7be6004 (Metraipolis archive dc_de8ed7be6004, sha256 10e49f1c4d931ecd6a21eb92631dfa6f1502a53738553a332cd00330015bc6ad)
BibTeX
@misc{dcde8ed7be6004,
title = {On the Convergence of Iterated Round Robin — arXiv:2610.23040},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.23040},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_de8ed7be6004; sha256 10e49f1c4d931ecd6a21eb92631dfa6f1502a53738553a332cd00330015bc6ad},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.23040. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Round Robin (RR) is a simple and widely used picking sequence mechanism for allocating indivisible goods, known to guarantee envy-freeness up to one item (EF1) when preferences are additive. Despite being manipulable (meaning that agents may have an incentive to strategically misreport their preferences), it is known to always admit at least one pure Nash equilibrium. In this paper, we study an iterated variant of RR, in which agents observe the outcome of the mechanism at each iteration and may revise their reported preferences through a best-response dynamics. We first consider a full-information setting, where agents observe both the outcome and the reported preferences of all the agents. In this setting, we show that cycles can occur even under strong restrictions on the manipulations carried out by the agents. We nonetheless identify a natural restriction (item-preserving swaps), under which convergence to a pure Nash equilibrium is guaranteed to exist for any number of agents and items. We also show that restricting to adjacent swaps guarantees convergence for two agents and a limited number of items, leaving the question open for unbounded number of items. We then turn to a partial-information setting, in which agents only observe the resulting allocation and must then infer the preference profiles of the others assuming consistency with the RR sequence. We study three behaviours guiding the agents when deciding how to manipulate under uncertainty on the other agents' preferences. We show that two of the studied behaviours, despite being quite natural, may cycle while a more cautious rule guarantees iterated RR to be strategyproof. Tema degli esploratori: economia dei servizi IA (elenco arXiv cs.GT, nuovi lavori del giorno). Categorie arXiv: Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2610.23040 — 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-19T08:40:39.824Z dalla pagina https://arxiv.org/list/cs.GT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).