Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap
Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap
Shayan Chashm Jahan, Masoud Seddighin, Seyed-Mohammad Seyed-Javadi, Mohammad Sharifi
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Main Track. Pages 2572-2580.
https://doi.org/10.24963/ijcai.2023/286
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 fairness notion 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^(β/β+1) .log(n)^(γ/β+1)) number of discarded goods. The best upper bound on R(d) is improved in a series of works to O(d^4), O(d^(2+o(1))), and finally to O(d^2). Also, via a simple observation, we have R(d) ∈ Ω(d).
In this paper, we introduce another problem in extremal combinatorics. For a parameter l, we define the rainbow path degree and denote it by H(l). We show that any lower bound on H(l) yields an upper bound on R(d). Next, we prove that H(l) ∈ Ω(l^2 / log(l)) which yields an almost tight upper bound of R(d) ∈ Ω(d.log(d)). This, in turn, proves the existence of (1−ϵ)-EFX allocation with O_ϵ(√n .log(n)) number of discarded goods. In addition, for the special case of the Rainbow Cycle problem that the edges in each part form a permutation, we improve the upper bound to R(d) ≤ 2d−4. We leverage H(l) to achieve this bound.
Our conjecture is that the exact value of H(l) is ⌊l^2/2⌋ − 1. We provide some experiments that support this conjecture. Assuming this conjecture is correct, we have R(d) ∈ θ(d).
Keywords:
Game Theory and Economic Paradigms: GTEP: Fair division
Multidisciplinary Topics and Applications: MDA: Economics