EFX Exists for Three Agents

Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages1-19
Number of pages19
ISBN (Electronic)9781450379755
DOIs
StatePublished - Jul 13 2020
Event21st ACM Conference on Economics and Computation, EC 2020 - Virtual, Online, Hungary
Duration: Jul 13 2020Jul 17 2020

Publication series

NameEC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation

Conference

Conference21st ACM Conference on Economics and Computation, EC 2020
CountryHungary
CityVirtual, Online
Period7/13/207/17/20

Keywords

  • discrete fair division
  • EFX allocations
  • nash welfare

ASJC Scopus subject areas

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Statistics and Probability
  • Computational Mathematics

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

  • Cite this

    Chaudhury, B. R., Garg, J., & Mehlhorn, K. (2020). EFX Exists for Three Agents. In EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation (pp. 1-19). [3399511] (EC 2020 - Proceedings of the 21st ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3391403.3399511