# Computing Welfare-Maximizing Fair Allocations of Indivisible Goods

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Dec 2020.

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

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [EFX Allocations Exist for Binary Valuations](https://mlsanity.com/paper/2308.05503/) (2023)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [EF1-Constrained Nash Social Welfare with Identical Additive Valuations: Complexity, Guarantees, and Experiments](https://mlsanity.com/paper/2609.03846/) (2026)

## Abstract (arXiv)

We analyze the run-time complexity of computing allocations that are both fair and maximize the utilitarian social welfare, defined as the sum of agents' utilities. We focus on two tractable fairness concepts: envy-freeness up to one item (EF1) and proportionality up to one item (PROP1). We consider two computational problems: (1) Among the utilitarian-maximal allocations, decide whether there exists one that is also fair; (2) among the fair allocations, compute one that maximizes the utilitarian welfare. We show that both problems are strongly NP-hard when the number of agents is variable, and remain NP-hard for a fixed number of agents greater than two. For the special case of two agents, we find that problem (1) is polynomial-time solvable, while problem (2) remains NP-hard. Finally, with a fixed number of agents, we design pseudopolynomial-time algorithms for both problems. We extend our results to the stronger fairness notions envy-freeness up to any item (EFx) and proportionality up to any item (PROPx).