Varun Sivashankar's linear rainbow cycle proof yields optimal EFX allocation
Researcher proves R(d) < ed, giving a linear bound and near-optimal unallocated goods
A fundamental open question in fair division asks whether every instance with additive valuations admits a complete EFX (envy-free up to any good) allocation. Because full EFX has resisted resolution, researchers have studied relaxations that leave some goods unallocated while guaranteeing (1−ε)-EFX. The rainbow cycle number R(d) was introduced to quantify the trade-off: smaller upper bounds on R(d) translate directly to fewer unallocated goods in the resulting partial allocation. The previous best bound, R(d) = O(d log d), produced O_ε(√(n log n)) unallocated goods for n agents, leaving room for improvement.
In a new arXiv paper, Varun Sivashankar resolves a long-standing conjecture by proving that R(d) is linear, specifically R(d) < ed (where e is Euler's number). This improvement immediately sharpens the guarantee to O(√(n/ε)) unallocated goods for any additive valuation instance with n agents, matching the best asymptotic result obtainable via the rainbow-cycle reduction. The paper also presents a randomized algorithm that finds such a partial (1−ε)-EFX allocation in expected polynomial time in the size of the input and in 1/ε. Beyond its direct application to fair division, the proof technique offers fresh insights into combinatorial cycle problems, potentially influencing other areas of theoretical computer science.
- Proves R(d) < ed, resolving the linear-bound conjecture and improving on the previous O(d log d) upper bound
- Yields partial (1−ε)-EFX allocations with O(√(n/ε)) unallocated goods for n agents, the best possible via the rainbow-cycle reduction
- Includes a randomized algorithm that runs in expected polynomial time in the input size and 1/ε
Why It Matters
Settles a major open question in fair division, enabling near-optimal approximate EFX guarantees with practical randomized algorithms.