EFX Exists for Three Agents

Research output: Contribution to journalArticlepeer-review


We study the problem of distributing a set of indivisible goods among agents with additive valuations in a fair manner. The fairness notion under consideration is envy-freeness up to any good (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 article, we show constructively that an EFX allocation always exists for three agents. Furthermore, we falsify the conjecture of Caragiannis et al. by showing an instance with three agents for which there is a partial EFX allocation (some goods are not allocated) with higher Nash welfare than that of any complete EFX allocation.

Original languageEnglish (US)
Article number4
JournalJournal of the ACM
Issue number1
StatePublished - Feb 12 2024


  • Discrete fair division
  • EFX allocations
  • Nash welfare

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


Dive into the research topics of 'EFX Exists for Three Agents'. Together they form a unique fingerprint.

Cite this