# The Price of Fairness for Indivisible Goods

arXiv: https://arxiv.org/abs/1905.04910 · HTML: https://mlsanity.com/paper/1905.04910/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2019.

## Built on by (most cited first, 8 of 8)

- [Temporal Elections: Welfare, Strategyproofness, and Proportionality](https://mlsanity.com/paper/2408.13637/) (2024)
- [Fairness Maximization among Offline Agents in Online-Matching Markets](https://mlsanity.com/paper/2109.08934/) (2021)
- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [Fair and Efficient Resource Allocation with Partial Information](https://mlsanity.com/paper/2105.10064/) (2021)
- [Proportional Fairness in Obnoxious Facility Location](https://mlsanity.com/paper/2301.04340/) (2023)
- [EFX Allocations Exist for Binary Valuations](https://mlsanity.com/paper/2308.05503/) (2023)
- [Learning Fair and Preferable Allocations through Neural Network](https://mlsanity.com/paper/2410.17500/) (2024)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)

## Abstract (arXiv)

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.