TY - GEN
T1 - EFX Exists for Three Agents
AU - Chaudhury, Bhaskar Ray
AU - Garg, Jugal
AU - Mehlhorn, Kurt
N1 - We would like to thank Hannaneh Akrami, Corinna Coupette, Kavitha Telikepalli and Alkmini Sgouritsa for helpful discussions. We thank Corinna Coupette also for a careful reading of the manuscript. This work is partially supported by NSF Grants CCF-1755619 (CRII) and CCF-1942321 (CAREER).
PY - 2020/7/13
Y1 - 2020/7/13
N2 - 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.
AB - 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.
KW - EFX allocations
KW - discrete fair division
KW - nash welfare
UR - https://www.scopus.com/pages/publications/85088371727
UR - https://www.scopus.com/pages/publications/85088371727#tab=citedBy
U2 - 10.1145/3391403.3399511
DO - 10.1145/3391403.3399511
M3 - Conference contribution
AN - SCOPUS:85088371727
T3 - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
SP - 1
EP - 19
BT - EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PB - Association for Computing Machinery
T2 - 21st ACM Conference on Economics and Computation, EC 2020
Y2 - 13 July 2020 through 17 July 2020
ER -