# The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 42 references that are in the map.
- First posted on arXiv 19 Jan 2026.

## Builds on (most cited first, 28 of 28)

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [Fair Division of Indivisible Goods: Recent Progress and Open Questions](https://mlsanity.com/paper/2208.08782/) (2022)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [Maximum Nash Welfare and Other Stories About EFX](https://mlsanity.com/paper/2001.09838/) (2020)
- [A Little Charity Guarantees Almost Envy-Freeness](https://mlsanity.com/paper/1907.04596/) (2019)
- [Fair Division with Binary Valuations: One Rule to Rule Them All](https://mlsanity.com/paper/2007.06073/) (2020)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [Almost Envy-Freeness in Group Resource Allocation](https://mlsanity.com/paper/1901.08463/) (2019)
- [Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination](https://mlsanity.com/paper/1909.07650/) (2019)
- [Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations](https://mlsanity.com/paper/2005.07370/) (2020)
- [On the Fairness of Normalized p-Means for Allocating Goods and Chores](https://mlsanity.com/paper/2402.14996/) (2024)
- [Uniform Welfare Guarantees Under Identical Subadditive Valuations](https://mlsanity.com/paper/2005.00504/) (2020)
- [Computing Welfare-Maximizing Fair Allocations of Indivisible Goods](https://mlsanity.com/paper/2012.03979/) (2020)
- [A tight negative example for MMS fair allocations](https://mlsanity.com/paper/2104.04977/) (2021)
- [Truthful and Fair Mechanisms for Matroid-Rank Valuations](https://mlsanity.com/paper/2109.05810/) (2021)
- [Tractable Fragments of the Maximum Nash Welfare Problem](https://mlsanity.com/paper/2112.10199/) (2021)
- [Approximability Landscape of Welfare Maximization within Fair Allocations](https://mlsanity.com/paper/2205.14296/) (2022)
- [A General Framework for Fair Allocation under Matroid Rank Valuations](https://mlsanity.com/paper/2208.07311/) (2022)
- [Existence of EFX for Two Additive Valuations](https://mlsanity.com/paper/2008.08798/) (2020)
- [Extension of Additive Valuations to General Valuations on the Existence of EFX](https://mlsanity.com/paper/2107.09901/) (2021)
- [EFX Allocations Exist for Binary Valuations](https://mlsanity.com/paper/2308.05503/) (2023)
- [A Complete Landscape for the Price of Envy-Freeness](https://mlsanity.com/paper/2401.01516/) (2024)
- [EFX Exists for Three Types of Agents](https://mlsanity.com/paper/2410.13580/) (2024)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)
- [Fair and Efficient Allocations under Subadditive Valuations](https://mlsanity.com/paper/2005.06511/) (2020)
- [The price of fairness for a small number of indivisible items](https://mlsanity.com/paper/1406.5722/) (2014)
- [Existence of MMS Allocations with Mixed Manna](https://mlsanity.com/paper/2401.07490/) (2024)
- [Egalitarian Price of Fairness for Indivisible Goods](https://mlsanity.com/paper/2402.16145/) (2024)

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

- [Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO](https://mlsanity.com/paper/2607.23367/) (2026)

## Abstract (arXiv)

Envy-freeness up to any good (EFX) is a central fairness notion for allocating indivisible goods, yet its existence is unresolved in general. In the setting with few surplus items, where the number of goods exceeds the number of agents by a small constant (at most three), EFX allocations are guaranteed to exist, shifting the focus from existence to efficiency and computation. We study how EFX interacts with generalized-mean (p-mean) welfare, which subsumes commonly-studied utilitarian (p=1), Nash (p=0), and egalitarian (p rightarrow -∞) objectives. We establish sharp complexity dichotomies at p=0: for any fixed p ∈ (0,1], both deciding whether EFX can attain the global p-mean optimum and computing an EFX allocation maximizing p-mean welfare are NP-hard, even with at most three surplus goods; in contrast, for any fixed p ≤ 0, we give polynomial-time algorithms that optimize p-mean welfare within the space of EFX allocations and efficiently certify when EFX attains the global optimum. We further quantify the welfare loss of enforcing EFX via the price of fairness framework, showing that for p > 0, the loss can grow linearly with the number of agents, whereas for p ≤ 0, it is bounded by a constant depending on the surplus (and for Nash welfare it vanishes asymptotically). Finally we show that requiring Pareto-optimality alongside EFX is NP-hard (and becomes Sigma2P-complete for a stronger variant of EFX). Overall, our results delineate when EFX is computationally costly versus structurally aligned with welfare maximization in the setting with few surplus items.