EFX Exists for Three Agents

Abstract

We study the problem of distributing a set of indivisible items among agents with additive valuations in a $fair$ 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.

Full version of a paper published at Economics and Computation (EC) 2020

References in corpus (1)

• An Improved Approximation Algorithm for Maximin Shares

Cited by in corpus (5)

• Maximum Nash Welfare and Other Stories About EFX
• On the Number of Almost Envy-Free Allocations
• Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores
• Indivisible Mixed Manna: On the Computability of MMS + PO Allocations
• Envy-freeness up to one item: Shall we add or remove resources?