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

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 the state-of-the-art by showing the existence of EFX allocations when two of the agents have general monotone valuations and one has additive or more generally MMS-feasible valuation (a strict generalization of nice-cancelable valuation functions). In contrast to the previous works, our new algorithm moves in the space of complete allocations, improving a potential, as long as the allocation is not EFX.

Secondly, we consider relaxations of EFX allocations, namely, approximate-EFX allocations and EFX allocations with few unallocated goods (charity). Through a promising new method using a problem in extremal combinatorics called Rainbow Cycle Number (RCN), Chaudhury et al. managed to show the existence of (1-epsilon)-EFX allocation with sub-linear charity, namely O((n/epsilon)^(4/5)) charity, where n is the number of agents. This is done by upper bounding the RCN by O(d^4) in d-dimension. They conjectured this number to be O(d) and gave a matching lower bound. We almost settle this conjecture by improving the upper bound to O(d log(d)) and thereby get (almost) optimal charity of \tilde{O}((n/ epsilon)^(1/2)) that is possible through this method. Our technique is based on probabilistic method. We also derandomize the approach to construct such an allocation in deterministic polynomial time.