Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap
share
Recently, some studies on the fair allocation of indivisible goods notice a connection between a purely combinatorial problem called the Rainbow Cycle problem and a notion of fairness known as EFX: assuming that the rainbow cycle number for parameter d (i.e. R(d)) is O(d^βlog^γ d), we can find a (1-ϵ)-EFX allocation with O_ϵ(n^β/β+1log^γ/β +1 n) number of discarded goods [7]. The best upper bound on R(d) improved in series of works to O(d^4) [7], O(d^2+o(1)) [2], and finally to O(d^2) [1]. Also, via a simple observation, we have R(d) ∈Ω(d) [7]. In this paper, we almost close the gap between the upper bound and the lower bound and show that R(d) ∈ O(d log d). This in turn proves the existence of (1-ϵ)-EFX allocation with O_ϵ(√(n)) number of discarded goods.
READ FULL TEXT