The Price of Fairness for Indivisible Goods

Abstract

We investigate the efficiency of fair allocations of indivisible goods using the well-studied price of fairness concept. Previous work has focused on classical fairness notions such as envy-freeness, proportionality, and equitability. However, these notions cannot always be satisfied for indivisible goods, leading to certain instances being ignored in the analysis. In this paper, we focus instead on notions with guaranteed existence, including envy-freeness up to one good (EF1), balancedness, maximum Nash welfare (MNW), and leximin. We also introduce the concept of strong price of fairness, which captures the efficiency loss in the worst fair allocation as opposed to that in the best fair allocation as in the price of fairness. We mostly provide tight or asymptotically tight bounds on the worst-case efficiency loss for allocations satisfying these notions, for both the price of fairness and the strong price of fairness.

A preliminary version appears in the 28th International Joint Conference on Artificial Intelligence (IJCAI), 2019

References in corpus (7)

• Multiple Birds with One Stone: Beating $1/2$ for EFX and GMMS via Envy Cycle Elimination
• Almost Envy-Freeness in Group Resource Allocation
• Finding Fair and Efficient Allocations When Valuations Don't Add Up
• Closing Gaps in Asymptotic Fair Division
• Envy-free Relaxations for Goods, Chores, and Mixed Items
• When Do Envy-Free Allocations Exist?
• On the Number of Almost Envy-Free Allocations

Cited by in corpus (7)

• Fair Division of Indivisible Goods: Recent Progress and Open Questions
• Mixed Fair Division: A Survey
• On the Number of Almost Envy-Free Allocations
• Truthful Cake Sharing
• Welfare Loss in Connected Resource Allocation
• The Price of EF1 for Few Agents with Additive Ternary Valuations
• On the Fairness of Additive Welfarist Rules