# 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