# Envy-freeness up to any item with high Nash welfare: The virtue of donating items

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2019.

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

- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [EFX Allocations Exist for Binary Valuations](https://mlsanity.com/paper/2308.05503/) (2023)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)
- [On the existence of EFX allocations in multigraphs](https://mlsanity.com/paper/2502.09777/) (2025)
- [Multilevel Fair Allocation with Matroid-Rank Preferences](https://mlsanity.com/paper/2512.24105/) (2025)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [Maximin Share Guarantees via Limited Cost-Sensitive Sharing](https://mlsanity.com/paper/2602.20541/) (2026)
- [Online Fair Division with Budget Constraints](https://mlsanity.com/paper/2607.23310/) (2026)
- [EFX Allocation In (Multi)Hypergraphs](https://mlsanity.com/paper/2608.03171/) (2026)

## Abstract (arXiv)

Several fairness concepts have been proposed recently in attempts to approximate envy-freeness in settings with indivisible goods. Among them, the concept of envy-freeness up to any item (EFX) is arguably the closest to envy-freeness. Unfortunately, EFX allocations are not known to exist except in a few special cases. We make significant progress in this direction. We show that for every instance with additive valuations, there is an EFX allocation of a subset of items with a Nash welfare that is at least half of the maximum possible Nash welfare for the original set of items. That is, after donating some items to a charity, one can distribute the remaining items in a fair way with high efficiency. This bound is proved to be best possible. Our proof is constructive and highlights the importance of maximum Nash welfare allocation. Starting with such an allocation, our algorithm decides which items to donate and redistributes the initial bundles to the agents, eventually obtaining an allocation with the claimed efficiency guarantee. The application of our algorithm to large markets, where the valuations of an agent for every item is relatively small, yields EFX with almost optimal Nash welfare. To the best of our knowledge, this is the first use of large market assumptions in the fair division literature. We also show that our algorithm can be modified to compute, in polynomial-time, EFX allocations that approximate optimal Nash welfare within a factor of at most 2ρ, using a ρ-approximate allocation on input instead of the maximum Nash welfare one.