theoretical computer science

A Linear Bound on the Rainbow Cycle Number and Approximate EFX

arXiv:2607.27455

summary

The paper proves that the rainbow cycle number grows linearly with the dimension, which yields a partial (1‑ε)-EFX allocation for any fair‑division instance with only O(√(n/ε)) unallocated goods, and provides a polynomial‑time randomized algorithm to find such an allocation.

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 - ε)$ -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 lo g d)$ , gives $O_{ε} (n lo g n)$ unallocated goods. We resolve the conjecture that $R (d)$ is linear by proving $R (d) < e d$ . It follows that every instance with $n$ agents admits a partial $(1 - ε)$ -EFX allocation with $O (n / ε)$ 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/ ε$ .

Topics & keywords

#fair division #envy-freeness #approximation algorithms #combinatorial bounds #randomized algorithmsEFX(1-ε)-EFXrainbow cycle numberlinear boundpartial allocationpolynomial-time algorithm