EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number

Hannaneh Akrami, Noga Alon, Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn, Ruta Mehta

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

4 Scopus citations

Abstract

The existence of EFX allocations is a fundamental open problem in discrete fair division. Since the general problem has been elusive, progress is made on two fronts: (i) proving existence when the number of agents is small, and (ii) proving the existence of relaxations of EFX. In this paper, we improve and simplify the state-of-the-art results on both fronts with new techniques.

Original languageEnglish (US)
Title of host publicationEC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Pages61
Number of pages1
ISBN (Electronic)9798400701047
DOIs
StatePublished - Jul 9 2023
Event24th ACM Conference on Economics and Computation, EC 2023 - London, United Kingdom
Duration: Jul 9 2023Jul 12 2023

Publication series

NameEC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation

Conference

Conference24th ACM Conference on Economics and Computation, EC 2023
Country/TerritoryUnited Kingdom
CityLondon
Period7/9/237/12/23

All Science Journal Classification (ASJC) codes

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

Fingerprint

Dive into the research topics of 'EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number'. Together they form a unique fingerprint.

Cite this