Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness

Georgios Amanatidis (), Georgios Birmpas (), Federico Fusco (), Philip Lazos (), Stefano Leonardi () and Rebecca Reiffenhäuser ()
Additional contact information
Georgios Amanatidis: School of Mathematics, Statistics and Actuarial Science, University of Essex, Colchester CO4 3SQ, United Kingdom; Archimedes/Athena Research Center, 15125 Marousi, Greece
Georgios Birmpas: Department of Computer Science, University of Liverpool, Liverpool L69 3BX, United Kingdom
Federico Fusco: Department of Computer, Control, and Management Engineering, Sapienza University of Rome, 00185 Roma, Italy
Philip Lazos: Input Output Global, London W1W 6DW, United Kingdom
Stefano Leonardi: Department of Computer, Control, and Management Engineering, Sapienza University of Rome, 00185 Roma, Italy
Rebecca Reiffenhäuser: Institute for Logic, Language and Computation, University of Amsterdam, 1012 WP Amsterdam, Netherlands

Mathematics of Operations Research, 2024, vol. 49, issue 4, 2425-2445

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.

Keywords: Primary: 91A68; 91B03; secondary: 68W25; 91B14; discrete fair division; mechanism design without money; fairness in equilibrium; envy-freeness up to one good; envy-freeness up to any good (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/moor.2022.0058 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:49:y:2024:i:4:p:2425-2445

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().