License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.17
URN: urn:nbn:de:0030-drops-168153
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16815/
Berendsohn, Benjamin Aram ;
Boyadzhiyska, Simona ;
Kozma, László
Fixed-Point Cycles and Approximate EFX Allocations
Abstract
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.}
BibTeX - Entry
@InProceedings{berendsohn_et_al:LIPIcs.MFCS.2022.17,
author = {Berendsohn, Benjamin Aram and Boyadzhiyska, Simona and Kozma, L\'{a}szl\'{o}},
title = {{Fixed-Point Cycles and Approximate EFX Allocations}},
booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
pages = {17:1--17:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-256-3},
ISSN = {1868-8969},
year = {2022},
volume = {241},
editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16815},
URN = {urn:nbn:de:0030-drops-168153},
doi = {10.4230/LIPIcs.MFCS.2022.17},
annote = {Keywords: fixed-point, zero-sum cycle, Ramsey theory, fair allocation, EFX}
}
|
Keywords: |
|
fixed-point, zero-sum cycle, Ramsey theory, fair allocation, EFX |
|
Collection: |
|
47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
22.08.2022 |
