# EFX Allocations Exist for Binary Valuations

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 10 Aug 2023.

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

- [Almost Envy-Freeness with General Valuations](https://mlsanity.com/paper/1707.04769/) (2017)
- [EFX Exists for Three Agents](https://mlsanity.com/paper/2002.05119/) (2020)
- [Fair and Truthful Mechanisms for Dichotomous Valuations](https://mlsanity.com/paper/2002.10704/) (2020)
- [A Little Charity Guarantees Almost Envy-Freeness](https://mlsanity.com/paper/1907.04596/) (2019)
- [Envy-freeness up to any item with high Nash welfare: The virtue of donating items](https://mlsanity.com/paper/1902.04319/) (2019)
- [Finding Fair and Efficient Allocations](https://mlsanity.com/paper/1707.04731/) (2017)
- [The Price of Fairness for Indivisible Goods](https://mlsanity.com/paper/1905.04910/) (2019)
- [The Conference Paper Assignment Problem: Using Order Weighted Averages to Assign Indivisible Goods](https://mlsanity.com/paper/1705.06840/) (2017)
- [Computing Welfare-Maximizing Fair Allocations of Indivisible Goods](https://mlsanity.com/paper/2012.03979/) (2020)
- [Approximability Landscape of Welfare Maximization within Fair Allocations](https://mlsanity.com/paper/2205.14296/) (2022)
- [Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goods](https://mlsanity.com/paper/2204.14229/) (2022)
- [On Existence of Truthful Fair Cake Cutting Mechanisms](https://mlsanity.com/paper/2104.07387/) (2021)
- [On Optimal Tradeoffs between EFX and Nash Welfare](https://mlsanity.com/paper/2302.09633/) (2023)
- [Fair Division of Mixed Divisible and Indivisible Goods](https://mlsanity.com/paper/1911.07048/) (2019)

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

- [The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Items](https://mlsanity.com/paper/2601.12849/) (2026)
- [Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division](https://mlsanity.com/paper/2507.14957/) (2025)
- [Simultaneous Envy and Equitability Guarantees](https://mlsanity.com/paper/2608.26410/) (2026)

## Abstract (arXiv)

We study the fair division problem and the existence of allocations satisfying the fairness criterion envy-freeness up to any item (EFX). The existence of EFX allocations is a major open problem in the fair division literature. We consider binary valuations where the marginal gain of the value by receiving an extra item is either 0 or 1. Babaioff et al. [2021] proved that EFX allocations always exist for binary and submodular valuations. In this paper, by using completely different techniques, we extend this existence result to general binary valuations that are not necessarily submodular, and we present a polynomial time algorithm for computing an EFX allocation.