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

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 $\mathcal{O}({(n/ϵ)}^{\frac{4}{5}})$ charity was established. This is done by upper bounding the RCN by $\mathcal{O}(d^4)$ in d-dimension. They conjecture RCN to be $\mathcal{O}(d)$. We almost settle this conjecture by improving the upper bound to $\mathcal{O}(d\log d)$ and thereby get (almost) optimal charity of $\tilde{\mathcal{O}}({(n/ϵ)}^{\frac{1}{2}})$ that is possible through this method. Our technique is much simpler than the previous ones and is based on the probabilistic method.

Funding: This work was supported by the Division of Computing and Communication Foundations (B. R. Chaudhury, R. Mehta, J. Garg) [Grants CCF-1750436, CCF-1942321, CCF-2334461], the National Science Foundation (N. Alon) [Grant DMS-2154082], and the United States–Israel Binational Science Foundation (N. Alon) [Grant 2018267].