pipette
ESEspañol

Revisiting the Fairness of Pure Nash Equilibria of Round-Robin

Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Federico Fusco, Stefano Leonardi, Rebecca Reiffenh\"auser

Preprint

In the authors' words

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 -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 -EF1 for all equilibria.

Main resultLimitation the authors admit

Appeared: Monday, October 19. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: Corrects the claim in arXiv:2109.08644 (WINE 2021; Math. Oper. Res. 49(4), 2024) that every pure Nash equilibrium of Round-Robin is EF1. We give a counterexample, identify the step of the original proof that fails, and show that every pure