论文标题
放松嫉妒的图表
Relaxations of Envy-Freeness Over Graphs
论文作者
论文摘要
当在代理商中分配一组不可分割的项目时，不能总是实现嫉妒的理想条件。嫉妒的柔和（EFX）和嫉妒$ k $隐藏的物品（hef- $ k $）是两种令人信服的令人羡慕的嫉妒，在许多情况下仍然难以捉摸。我们研究了这两种公平限制的自然放松，其中我们将代理放置在无向图的顶点上，并且只要求我们的分配满足图表边缘的EFX（resp。HEF）约束。我们将这些分配称为Graph-EFX（rups。Graph-Hef）或简单的$ G $ -EFX（分别$ G $ -HEF）。我们表明，对于任何图$ g $，总是存在$ g $ -hef- $ k $的商品分配，其中$ k $是$ g $的最低顶点封面的大小，这本质上是紧密的。我们表明，$ g $ -EFX的商品分配存在于三个不同类别的图表中 - 其中两个概括了星级$ k_ {1，n-1} $，第三个概括了三边路路径$ p_4 $。这些结果中的许多也扩展到杂务的分配。总体而言，我们显示了几种自然设置，其中图形结构有助于获得强大的公平保证。最后，我们使用SplidDit的问题实例评估了算法，以表明$ G $ -EFX分配似乎存在于PATHS $ P_N $中，这指着向更广泛的图形家庭展示EFX的道路。
When allocating a set of indivisible items among agents, the ideal condition of envy-freeness cannot always be achieved. Envy-freeness up to any good (EFX), and envy-freeness with $k$ hidden items (HEF-$k$) are two very compelling relaxations of envy-freeness, which remain elusive in many settings. We study a natural relaxation of these two fairness constraints, where we place the agents on the vertices of an undirected graph, and only require that our allocations satisfy the EFX (resp. HEF) constraint on the edges of the graph. We refer to these allocations as graph-EFX (resp. graph-HEF) or simply $G$-EFX (resp. $G$-HEF) allocations. We show that for any graph $G$, there always exists a $G$-HEF-$k$ allocation of goods, where $k$ is the size of a minimum vertex cover of $G$, and that this is essentially tight. We show that $G$-EFX allocations of goods exist for three different classes of graphs -- two of them generalizing the star $K_{1, n-1}$ and the third generalizing the three-edge path $P_4$. Many of these results extend to allocations of chores as well. Overall, we show several natural settings in which the graph structure helps obtain strong fairness guarantees. Finally, we evaluate an algorithm using problem instances from Spliddit to show that $G$-EFX allocations appear to exist for paths $P_n$, pointing the way towards showing EFX for even broader families of graphs.
