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

Hannaneh Akrami (), Noga Alon (), Bhaskar Ray Chaudhury (), Jugal Garg (), Kurt Mehlhorn () and Ruta Mehta ()
Additional contact information
Hannaneh Akrami: Max Planck Institute for Informatics and Universität des Saarlandes, 66123 Saarbrücken, Germany
Noga Alon: Princeton University, Princeton, New Jersey 08544
Bhaskar Ray Chaudhury: University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
Jugal Garg: University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
Kurt Mehlhorn: Max Planck Institute for Informatics and Universität des Saarlandes, 66123 Saarbrücken, Germany
Ruta Mehta: University of Illinois at Urbana-Champaign, Urbana, Illinois 61801

Operations Research, 2025, vol. 73, issue 2, 738-751

Abstract: The existence of envy-freeness up to any good (EFX) allocations is a fundamental open problem in discrete fair division. The goal is to determine the existence of an allocation of a set of indivisible goods among n agents for which no agent envies another, following the removal of any single good from the other agent’s bundle. Because the general problem has been elusive, progress is made on two fronts: (i) proving existence when n 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. For the case of three agents, the existence of EFX was first shown with additive valuations and then extended to nice-cancelable valuations. As our first main result, we simplify and improve this result by showing the existence of EFX allocations when two of the agents have general monotone valuations and one has a maximin share (MMS)–feasible valuation (a strict generalization of nice-cancelable valuation functions). Our approach is significantly simpler than the previous ones, and it also avoids using the standard concepts of envy graph and champion graph and may find use in other fair-division problems. Second, we consider approximate EFX allocations with few unallocated goods (charity). Through a promising new method using a problem in extremal combinatorics called rainbow cycle number (RCN), the existence of ( 1 − ϵ ) -EFX allocation with O ( ( n / ϵ ) 4 5 ) charity was established. This is done by upper bounding the RCN by O ( d 4 ) in d -dimension. They conjecture RCN to be O ( d ) . We almost settle this conjecture by improving the upper bound to O ( d log d ) and thereby get (almost) optimal charity of O ˜ ( ( n / ϵ ) 1 2 ) that is possible through this method. Our technique is much simpler than the previous ones and is based on the probabilistic method.

Keywords: Market; Analytics; and; Revenue; Management; discrete fair division; EFX allocations; rainbow cycle number (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2023.0433 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:73:y:2025:i:2:p:738-751

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().