论文标题
定点周期和EFX分配
Fixed-point cycles and EFX allocations
论文作者
论文摘要
我们研究了完整的双向图$ \ overset {\ tiny \ leftrightArrow} {k} _n $的边缘标记，并从集合$ [d] = \ {1，\ dots，d \} $带有功能。我们将$ \ overset {\ tiny \ leftrightArrow} {k} _n $称为固定点周期，如果构成其边缘的标签会导致具有固定点的地图，并且我们说，如果不存在固定点，则标签是固定点的。对于给定的$ d $，我们要求最大的$ n $值，表示为$ r_f（d）$，其中存在$ \ overset {\ tiny \ tiny \ leftrightArrow} {k} {k} {k} _n $的无定点标签。确定所有$ d> 0 $的$ r_f（d）$是一个天然的拉姆西型问题，在极端组合中概括了一些良好的零和零问题。该问题最近是由Chaudhury，Garg，Mehlhorn，Mehta和Misra提出的，他们证明了$ d \ leq r_f（d）\ leq d^4+d $，并表明该问题与EFX分配有着密切的联系，这是社会选择理论中公平分配的核心分配问题。 在本文中，我们显示了改进的$ r_f（d）\ leq d^{2 + o（1）} $，得出有效的$ {（1- \ varepsilon）} $ - EFX分配$ n $ agents和$ o（n^{0.67}）$（n^{0.67}）$ nover $ \ varepssilon $ \ varepsilon \ varepsilon \ varepsilon; Chaudhury，Garg，Mehlhorn，Mehta和Misra的$ O（N^{0.8}）$。 此外，在所有边缘标签都是closulations的情况下，我们证明了更强的上限$ 2D-2 $。这个问题的一个非常特殊的情况是，在digraphs中找到零和周期的一个，其边缘的标记为$ \ mathbb {z} _d $，Alon和Krivelevich以及Mészáros和Steiner最近考虑了。我们的结果改善了这些作者获得的界限，并将其扩展到了任意（不一定是可交换）组的标签，同时也简化了证明。
We study edge-labelings of the complete bidirected graph $\overset{\tiny\leftrightarrow}{K}_n$ with functions from the set $[d] = \{1, \dots, d\}$ to itself. We call a cycle in $\overset{\tiny\leftrightarrow}{K}_n$ a fixed-point cycle if composing the labels of its edges 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 $\overset{\tiny\leftrightarrow}{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, who proved that $d \leq R_f(d) \leq d^4+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) \leq d^{2 + o(1)}$, yielding an efficient ${(1-\varepsilon)}$-EFX allocation with $n$ agents and $O(n^{0.67})$ unallocated goods for any constant $\varepsilon \in (0,1/2]$; 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 permulations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of $\mathbb{Z}_d$, was recently considered by Alon and Krivelevich and by Mészáros and Steiner. Our result improves the bounds obtained by these authors and extends them to labelings from an arbitrary (not necessarily commutative) group, while also simplifying the proof.
