Berendsohn, Benjamin Aram ;
Boyadzhiyska, Simona ;
Kozma, László
FixedPoint Cycles and Approximate EFX Allocations
Abstract
We study edgelabelings 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 fixedpoint 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 fixedpointfree if no fixedpoint cycle exists. For a given d, we ask for the largest value of n, denoted R_f(d), for which there exists a fixedpointfree labeling of K^↔_n. Determining R_f(d) for all d > 0 is a natural Ramseytype question, generalizing some wellstudied zerosum 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 2d2, in the case where all edgelabels are permutations. A very special case of this problem, that of finding zerosum 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.}
BibTeX  Entry
@InProceedings{berendsohn_et_al:LIPIcs.MFCS.2022.17,
author = {Berendsohn, Benjamin Aram and Boyadzhiyska, Simona and Kozma, L\'{a}szl\'{o}},
title = {{FixedPoint Cycles and Approximate EFX Allocations}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {17:117:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772563},
ISSN = {18688969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16815},
URN = {urn:nbn:de:0030drops168153},
doi = {10.4230/LIPIcs.MFCS.2022.17},
annote = {Keywords: fixedpoint, zerosum cycle, Ramsey theory, fair allocation, EFX}
}
22.08.2022
Keywords: 

fixedpoint, zerosum cycle, Ramsey theory, fair allocation, EFX 
Seminar: 

47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Issue date: 

2022 
Date of publication: 

22.08.2022 