Iterated round robin methods may not always settle but some strategies guarantee fairness

On the Convergence of Iterated Round Robin

Computer Science and Game Theory

Summary

When sharing items among people, Round Robin is a common fair method where everyone takes turns picking items. The paper studies what happens when people change their stated preferences repeatedly to get better outcomes. The authors find that this process can sometimes get stuck in cycles and never settle on a stable sharing plan. But if people’s preference changes follow certain restrictions, the sharing method will eventually settle into a stable and fair outcome. They also examine situations where people don’t see all preferences and find some cautious strategies ensure fairness.

What this means in practice

  • For market designers: Design allocation systems where agents revise preferences and guarantee stable, fair outcomes under certain rules.
  • For online platform designers: Build iterative allocation mechanisms that remain strategyproof in settings with limited information about others’ preferences.

A theory result. No direct application yet.

Authors

Maxime Lucet, Henri Surugue, Nawal Benabbou, Aurélie Beynier, Nicolas Maudet, Arianna Novaro

Abstract

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.