Round-robin picking sequences do not always ensure fairness guarantees
Revisiting the Fairness of Pure Nash Equilibria of Round-Robin
Computer Science and Game Theory
Summary
The paper looks at how fairly items get shared when people pick them in turn, called Round-Robin. It shows that not all ways people might pick in this setup lead to fair shares if fairness means no one envies another too much. However, they also prove that every pure Nash equilibrium of certain balanced picking methods guarantees some approximate fairness and proportionality. They identify limitations on how fair these outcomes can be at best. This corrects earlier incorrect assumptions about fairness in these picking games.
What this means in practice
- •For resource allocation teams: Design allocation protocols knowing that exact envy-freeness may fail in round-robin picking but approximate guarantees hold for balanced sequences.
- •For multi-agent system designers: Develop fair division mechanisms with guaranteed approximate fairness and proportionality based on recursive picking sequences in strategic settings.
A theory result. No direct application yet.
Authors
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Federico Fusco, Stefano Leonardi, Rebecca Reiffenhäuser
Abstract
We prove that for additive valuations, not every pure Nash equilibrium of the Round-Robin mechanism induces an allocation that is envy-free up to one good (EF1) with respect to the agents' true valuations. This corrects an earlier claim of Amanatidis et al. (WINE 2021; Math. Oper. Res. 2024). On the positive side, every pure Nash equilibrium of every fixed recursively balanced picking sequence mechanism induces an allocation that is $1/2$-EF1 and proportional up to one good (PROP1). We prove the approximate EF1 guarantee through a potential function comparing two executions, and the proportionality guarantee via a deviation that preserves the agent's most valuable goods. We also give a family of Round Robin equilibria showing that it is not possible to have a strictly better guarantee than $2/3$-EF1 for all equilibria.