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/
Go to the corresponding LIPIcs Volume Portal


Berendsohn, Benjamin Aram ; Boyadzhiyska, Simona ; Kozma, László

Fixed-Point Cycles and Approximate EFX Allocations

pdf-format:
LIPIcs-MFCS-2022-17.pdf (0.8 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI