mlsanityData to 14 Oct 2026

EFX Allocations Exist for Binary Valuations

arXiv 2308.05503 ↗First posted 10 Aug 2023cs.CE cs.AI cs.CCcited by 3

Not on the map. Why?

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.

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

14 of 32 references.

References · 14

  1. 2017Almost Envy-Freeness with General Valuationscited by 22
  2. 2020EFX Exists for Three Agentscited by 14
  3. 2020Fair and Truthful Mechanisms for Dichotomous Valuationscited by 13
  4. 2019A Little Charity Guarantees Almost Envy-Freenesscited by 12
  5. 2019Envy-freeness up to any item with high Nash welfare: The virtue of donating itemscited by 10
  6. 2017Finding Fair and Efficient Allocationscited by 9
  7. 2019The Price of Fairness for Indivisible Goodscited by 8
  8. 2017The Conference Paper Assignment Problem: Using Order Weighted Averages to Assign Indivisible Goodscited by 6
  9. 2020Computing Welfare-Maximizing Fair Allocations of Indivisible Goodscited by 5
  10. 2022Approximability Landscape of Welfare Maximization within Fair Allocationscited by 4
  11. 2022Computing Pareto-Optimal and Almost Envy-Free Allocations of Indivisible Goodscited by 3
  12. 2021On Existence of Truthful Fair Cake Cutting Mechanismscited by 2
2 more
  1. 2023On Optimal Tradeoffs between EFX and Nash Welfarecited by 2
  2. 2019Fair Division of Mixed Divisible and Indivisible Goodscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 2.

3 papers.

  1. 2026The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Itemscited by 1
  2. 2025Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Divisioncited by 0
  3. 2026Simultaneous Envy and Equitability Guaranteescited by 0