mlsanityData to 7 Oct 2026

EFX Exists for Three Agents

arXiv 2002.05119 ↗First posted 12 Feb 2020cs.GTcited by 14

Not on the map. Why?

Abstract (arXiv)

We study the problem of distributing a set of indivisible items among agents with additive valuations in a mathitfair manner. The fairness notion under consideration is Envy-freeness up to any item (EFX). Despite significant efforts by many researchers for several years, the existence of EFX allocations has not been settled beyond the simple case of two agents. In this paper, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture by Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some items are not allocated) with higher Nash welfare than that of any complete EFX allocation.

Key facts. Cited by 14 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Feb 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 2; 2023: 2; 2024: 1; 2025: 4; 2026: 2.

14 papers.

Sort:

  1. 2025Online Fair Division with Additional Informationcited by 6
  2. 2024Pushing the Frontier on Approximate EFX Allocationscited by 4
  3. 2021Fair and Efficient Resource Allocation with Partial Informationcited by 3
  4. 2021Allocating Indivisible Goods to Strategic Agents: Pure Nash Equilibria and Fairnesscited by 3
  5. 2023EFX Allocations Exist for Binary Valuationscited by 3
  6. 2023The Fairness Fair: Bringing Human Perception into Collective Decision-Makingcited by 2
  7. 2021PROPm Allocations of Indivisible Goods to Multiple Agentscited by 1
  8. 2022Reforming an Envy-Free Matchingcited by 1
  9. 2025On the existence of EFX allocations in multigraphscited by 1
  10. 2026The Cost of EFX: Generalized-Mean Welfare and Complexity Dichotomies with Few Surplus Itemscited by 1
  11. 2022(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Mannacited by 0
  12. 2025Polynomial-Time Algorithms for Fair Orientations of Chorescited by 0
2 more
  1. 2025Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Divisioncited by 0
  2. 2026Simultaneous Envy and Equitability Guaranteescited by 0