A Linear Bound on the Rainbow Cycle Number and Approximate EFX

Abstract

It is open whether every fair-division instance with additive valuations admits a complete envy-free-up-to-any-good (EFX) allocation. A well-studied relaxation allows some goods to remain unallocated and asks for $(1-\varepsilon)$-EFX. The rainbow cycle number $R(d)$ was introduced to study this problem: upper bounds on $R(d)$ yield approximate EFX allocations with few unallocated goods. The best previous bound, $R(d)=O(d\log d)$, gives $O_\varepsilon(\sqrt{n\log n})$ unallocated goods. We resolve the conjecture that $R(d)$ is linear by proving $R(d)<ed$. It follows that every instance with $n$ agents admits a partial $(1-\varepsilon)$-EFX allocation with $O(\sqrt{n/\varepsilon})$ unallocated goods. This is the best possible asymptotic guarantee on the number of unallocated goods obtainable from the rainbow-cycle reduction. We also give a randomized algorithm that finds such an allocation in expected time polynomial in the input size and $1/\varepsilon$.