{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:46:03Z","timestamp":1767339963418},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,8]]},"abstract":"<jats:p>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^\u03b2 .log(d)^\u03b3), we can find a (1 \u2212 \u03f5)-EFX allocation with O_\u03f5(n^(\u03b2\/\u03b2+1) .log(n)^(\u03b3\/\u03b2+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) \u2208 \u2126(d).\n\nIn 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) \u2208 \u03a9(l^2 \/ log(l)) which yields an almost tight upper bound of R(d) \u2208 \u03a9(d.log(d)).  This, in turn, proves the existence of (1\u2212\u03f5)-EFX allocation with O_\u03f5(\u221an .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) \u2264 2d\u22124. We leverage H(l) to achieve this bound.\n\nOur conjecture is that the exact value of H(l) is \u230al^2\/2\u230b \u2212 1. We provide some experiments that support this conjecture. Assuming this conjecture is correct, we have R(d) \u2208 \u03b8(d).<\/jats:p>","DOI":"10.24963\/ijcai.2023\/286","type":"proceedings-article","created":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:31:30Z","timestamp":1691742690000},"page":"2572-2580","source":"Crossref","is-referenced-by-count":2,"title":["Rainbow Cycle Number and EFX Allocations: (Almost) Closing the Gap"],"prefix":"10.24963","author":[{"given":"Shayan","family":"Chashm Jahan","sequence":"first","affiliation":[{"name":"Sharif University of Technology"}]},{"given":"Masoud","family":"Seddighin","sequence":"additional","affiliation":[{"name":"Tehran Institute for Advanced Studies, Khatam University, Iran"}]},{"given":"Seyed-Mohammad","family":"Seyed-Javadi","sequence":"additional","affiliation":[{"name":"Sharif University of Technology"}]},{"given":"Mohammad","family":"Sharifi","sequence":"additional","affiliation":[{"name":"Sharif University of Technology"}]}],"member":"10584","event":{"number":"32","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"acronym":"IJCAI-2023","name":"Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}","start":{"date-parts":[[2023,8,19]]},"theme":"Artificial Intelligence","location":"Macau, SAR China","end":{"date-parts":[[2023,8,25]]}},"container-title":["Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2023,8,11]],"date-time":"2023-08-11T08:44:23Z","timestamp":1691743463000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2023\/286"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2023,8]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2023\/286","relation":{},"subject":[],"published":{"date-parts":[[2023,8]]}}}