# Almost Envy-Freeness with General Valuations

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2017.

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

- [Fairness in Federated Learning via Core-Stability](https://mlsanity.com/paper/2211.02091/) (2022)
- [Temporal Fair Division of Indivisible Items](https://mlsanity.com/paper/2410.14593/) (2024)
- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Pushing the Frontier on Approximate EFX Allocations](https://mlsanity.com/paper/2406.12413/) (2024)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairness](https://mlsanity.com/paper/2109.08644/) (2021)
- [Yankee Swap: a Fast and Simple Fair Allocation Mechanism for Matroid Rank Valuations](https://mlsanity.com/paper/2206.08495/) (2022)
- [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)
- [Fairness in Repeated Matching: A Maximin Perspective](https://mlsanity.com/paper/2510.04624/) (2025)
- [PROPm Allocations of Indivisible Goods to Multiple Agents](https://mlsanity.com/paper/2105.11348/) (2021)
- [Resource Allocation under the Latin Square Constraint](https://mlsanity.com/paper/2501.06506/) (2025)
- [On the existence of EFX allocations in multigraphs](https://mlsanity.com/paper/2502.09777/) (2025)
- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna](https://mlsanity.com/paper/2202.02672/) (2022)
- [Dividing Good and Better Items Among Agents with Bivalued Submodular Valuations](https://mlsanity.com/paper/2302.03087/) (2023)
- [Polynomial-Time Algorithms for Fair Orientations of Chores](https://mlsanity.com/paper/2501.13481/) (2025)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [Envy-Free Allocation of Indivisible Goods via Noisy Queries](https://mlsanity.com/paper/2602.06361/) (2026)
- [Fair Division with Strictly Increasing Valuations: A Tight Threshold for Two-Agent EF1 and PO](https://mlsanity.com/paper/2607.23367/) (2026)
- [EFX Allocation In (Multi)Hypergraphs](https://mlsanity.com/paper/2608.03171/) (2026)
- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)

## Abstract (arXiv)

The goal of fair division is to distribute resources among competing players in a "fair" way. Envy-freeness is the most extensively studied fairness notion in fair division. Envy-free allocations do not always exist with indivisible goods, motivating the study of relaxed versions of envy-freeness. We study the envy-freeness up to any good (EFX) property, which states that no player prefers the bundle of another player following the removal of any single good, and prove the first general results about this property. We use the leximin solution to show existence of EFX allocations in several contexts, sometimes in conjunction with Pareto optimality. For two players with valuations obeying a mild assumption, one of these results provides stronger guarantees than the currently deployed algorithm on Spliddit, a popular fair division website. Unfortunately, finding the leximin solution can require exponential time. We show that this is necessary by proving an exponential lower bound on the number of value queries needed to identify an EFX allocation, even for two players with identical valuations. We consider both additive and more general valuations, and our work suggests that there is a rich landscape of problems to explore in the fair division of indivisible goods with different classes of player valuations.