2026-07-23T13:53:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16815 2024-03-06T10:58:24Z ddc:004 open_access

Fixed-Point Cycles and Approximate EFX Allocations Berendsohn, Benjamin Aram Boyadzhiyska, Simona Kozma, László fixed-point zero-sum cycle Ramsey theory fair allocation EFX We study edge-labelings of the complete bidirected graph K^↔_n with functions that map the set [d] = {1, … , d} to itself. We call a directed cycle in K^↔_n a fixed-point cycle if composing the labels of its edges in order results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given d, we ask for the largest value of n, denoted R_f(d), for which there exists a fixed-point-free labeling of K^↔_n. Determining R_f(d) for all d > 0 is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra [EC 2021], who proved that d ≤ R_f(d) ≤ d⁴+d and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory. In this paper we show the improved bound R_f(d) ≤ d^{2 + o(1)}, yielding an efficient (1-ε)-EFX allocation with n agents and O((n/ε)^{0.67}) unallocated goods; this improves the bound of O((n/ε)^{0.8}) of Chaudhury, Garg, Mehlhorn, Mehta, and Misra. {Additionally, we prove the stronger upper bound 2d-2, in the case where all edge-labels are permutations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of ℤ_d, was recently considered by Alon and Krivelevich [JGT 2021] and by Mészáros and Steiner [EJC 2021]. Our result improves the bounds obtained by these authors and extends them to labelings with elements of an arbitrary (not necessarily commutative) group, while also simplifying the proof.} Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benjamin Aram Berendsohn and Simona Boyadzhiyska and László Kozma 2022 Is Part Of LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2022.17 urn:nbn:de:0030-drops-168153 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.17 eng https://creativecommons.org/licenses/by/4.0/legalcode