@inproceedings{15096b3759cc44e68ee9bc8c3eec3f9b,
title = "EFX Exists for Three Agents",
abstract = "We study the problem of distributing a set of indivisible items among agents with additive valuations in a fairmanner. The fairness notion under consideration is Envy-freeness up to anyitem (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.[9] 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.",
keywords = "EFX allocations, discrete fair division, nash welfare",
author = "Chaudhury, {Bhaskar Ray} and Jugal Garg and Kurt Mehlhorn",
note = "Publisher Copyright: {\textcopyright} 2020 ACM.; 21st ACM Conference on Economics and Computation, EC 2020 ; Conference date: 13-07-2020 Through 17-07-2020",
year = "2020",
month = jul,
day = "13",
doi = "10.1145/3391403.3399511",
language = "English (US)",
series = "EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation",
publisher = "Association for Computing Machinery",
pages = "1--19",
booktitle = "EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation",
address = "United States",
}