Amanatidis, Georgios and Birmpas, Georgios and Fusco, Federico and Lazos, Philip and Leonardi, Stefano and Reiffenhäuser, Rebecca (2023) Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness. Mathematics of Operations Research. DOI https://doi.org/10.1287/moor.2022.0058
Amanatidis, Georgios and Birmpas, Georgios and Fusco, Federico and Lazos, Philip and Leonardi, Stefano and Reiffenhäuser, Rebecca (2023) Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness. Mathematics of Operations Research. DOI https://doi.org/10.1287/moor.2022.0058
Amanatidis, Georgios and Birmpas, Georgios and Fusco, Federico and Lazos, Philip and Leonardi, Stefano and Reiffenhäuser, Rebecca (2023) Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness. Mathematics of Operations Research. DOI https://doi.org/10.1287/moor.2022.0058
Abstract
We consider the problem of fairly allocating a set of indivisible goods to a set of strategic agents with additive valuation functions. We assume no monetary transfers, and therefore, a mechanism in our setting is an algorithm that takes as input the reported—rather than the true—values of the agents. Our main goal is to explore whether there exist mechanisms that have pure Nash equilibria for every instance and, at the same time, provide fairness guarantees for the allocations that correspond to these equilibria. We focus on two relaxations of envy-freeness, namely, envy-freeness up to one good (EF1) and envy-freeness up to any good (EFX), and we positively answer the preceding question. In particular, we study two algorithms that are known to produce such allocations in the nonstrategic setting: round-robin (EF1 allocations for any number of agents) and a cut-and-choose algorithm of Plaut and Roughgarden (EFX allocations for two agents). For round-robin, we show that all of its pure Nash equilibria induce allocations that are EF1 with respect to the underlying true values, whereas for the algorithm of Plaut and Roughgarden, we show that the corresponding allocations not only are EFX, but also satisfy maximin share fairness, something that is not true for this algorithm in the nonstrategic setting! Further, we show that a weaker version of the latter result holds for any mechanism for two agents that always has pure Nash equilibria, which all induce EFX allocations.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | discrete fair division; mechanism design without money; fairness in equilibrium; envy-freeness up to one good; envy-freeness up to any good |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Mathematics, Statistics and Actuarial Science, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 24 Jan 2024 16:40 |
Last Modified: | 07 Aug 2024 15:27 |
URI: | http://repository.essex.ac.uk/id/eprint/37030 |
Available files
Filename: Fair_Division_under_Incentives-1.pdf