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

doi:10.1145/3580507.3597799

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

Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

13 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 language	English (US)
Title of host publication	EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation
Publisher	Association for Computing Machinery, Inc
Pages	61
Number of pages	1
ISBN (Electronic)	9798400701047
DOIs	https://doi.org/10.1145/3580507.3597799
State	Published - Jul 9 2023
Event	24th ACM Conference on Economics and Computation, EC 2023 - London, United Kingdom Duration: Jul 9 2023 → Jul 12 2023

Publication series

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

Conference

Conference	24th ACM Conference on Economics and Computation, EC 2023
Country/Territory	United Kingdom
City	London
Period	7/9/23 → 7/12/23

All Science Journal Classification (ASJC) codes

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

Access to Document

10.1145/3580507.3597799

Cite this

Akrami, H., Alon, N., Chaudhury, B. R., Garg, J., Mehlhorn, K., & Mehta, R. (2023). EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. In EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation (pp. 61). (EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation). Association for Computing Machinery, Inc. https://doi.org/10.1145/3580507.3597799

@inproceedings{b4751cdfb6864354b69a10e58d8713eb,

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

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.",

author = "Hannaneh Akrami and Noga Alon and Chaudhury, {Bhaskar Ray} and Jugal Garg and Kurt Mehlhorn and Ruta Mehta",

note = "Publisher Copyright: {\textcopyright} 2023 Owner/Author(s).; 24th ACM Conference on Economics and Computation, EC 2023 ; Conference date: 09-07-2023 Through 12-07-2023",

year = "2023",

month = jul,

day = "9",

doi = "10.1145/3580507.3597799",

language = "English (US)",

series = "EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation",

publisher = "Association for Computing Machinery, Inc",

pages = "61",

booktitle = "EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation",

}

Akrami, H, Alon, N, Chaudhury, BR, Garg, J, Mehlhorn, K & Mehta, R 2023, EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. in EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation. EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation, Association for Computing Machinery, Inc, pp. 61, 24th ACM Conference on Economics and Computation, EC 2023, London, United Kingdom, 7/9/23. https://doi.org/10.1145/3580507.3597799

EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. / Akrami, Hannaneh; Alon, Noga; Chaudhury, Bhaskar Ray et al.
EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation. Association for Computing Machinery, Inc, 2023. p. 61 (EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - EFX

T2 - 24th ACM Conference on Economics and Computation, EC 2023

AU - Akrami, Hannaneh

AU - Alon, Noga

AU - Chaudhury, Bhaskar Ray

AU - Garg, Jugal

AU - Mehlhorn, Kurt

AU - Mehta, Ruta

PY - 2023/7/9

Y1 - 2023/7/9

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85167886529&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85167886529&partnerID=8YFLogxK

U2 - 10.1145/3580507.3597799

DO - 10.1145/3580507.3597799

M3 - Conference contribution

AN - SCOPUS:85167886529

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

SP - 61

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

PB - Association for Computing Machinery, Inc

Y2 - 9 July 2023 through 12 July 2023

ER -

Akrami H, Alon N, Chaudhury BR, Garg J, Mehlhorn K, Mehta R. EFX: A Simpler Approach and an (Almost) Optimal Guarantee via Rainbow Cycle Number. In EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation. Association for Computing Machinery, Inc. 2023. p. 61. (EC 2023 - Proceedings of the 24th ACM Conference on Economics and Computation). doi: 10.1145/3580507.3597799

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

Abstract

Publication series

Conference

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this