Improving EFX Guarantees through Rainbow Cycle Number

Bhaskar Ray Chaudhury, Jugal Garg, Kurt Mehlhorn +2

We study the problem of fairly allocating a set of indivisible goods among $n$ agents with additive valuations. Envy-freeness up to any good (EFX) is arguably the most compelling f…