Relaxations of Envy-Freeness Over Graphs
Relaxations of Envy-Freeness Over Graphs
复制标题
DOI：
10.5555/3545946.3599032
复制
发表时间：
2022-02
期刊：
影响因子：
--
通讯作者：
Justin Payan;Rik Sengupta;V. Viswanathan
中科院分区：
文献类型：
--
作者：
Justin Payan;Rik Sengupta;V. Viswanathan
在智能体之间分配一组不可分割的物品时，并不总是能达到无嫉妒的理想状态。无嫉妒（EFX）和无嫉妒（HEF-$k$）是无嫉妒的两种非常引人注目的放松方式，在许多情况下仍然难以捉摸。我们研究了这两个公平约束的自然松弛，其中我们将代理放置在无向图的顶点上，并且只要求我们的分配满足EFX （resp）。HEF)约束在图的边上。我们将这些分配称为图- efx（见图1）。图- hef)或简单的$G$-EFX（见图1）。G医疗公平基金美元)分配。我们证明了对于任意图$G$，总是存在$G$- hef -$k$的商品分配，其中$k$是$G$的最小顶点覆盖的大小，并且这本质上是紧的。我们证明了商品的$G$-EFX分配存在于三种不同类型的图中——其中两种图推广了星形$K_{1, n-1}$，第三种图推广了三边路径$P_4$。其中许多结果也适用于家务的分配。总的来说，我们展示了几种自然设置，其中图结构有助于获得强公平性保证。最后，我们使用Spliddit中的问题实例来评估一种算法，以表明$G$-EFX分配似乎存在于路径$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.