摘要
arXiv:2502.09777v1 宣告类型: cross
摘要: 我们研究了一种“公平”分割不可分割物品的问题,这些物品由几个具有物品集合估值函数的代理进行估值。作为公平的标准,我们考虑的是“ envy-free up to any good (EFX) ”的分配,即没有任何代理会嫉妒其他代理所分配的任何物品的任何子集。是否存在或不存在 EFX 分配是公平分割领域的重大开放问题,目前只有针对特殊案例的积极结果。
[George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] 根据图结构对代理的估值进行了限制:顶点对应于代理,边对应于物品,每个顶点/代理对不相邻的边/物品具有零边际价值(换句话说,他们对此是无所谓的)。对于具有通用单调估值的简单图,[George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] 已证明存在 EFX 分配,并且对于具有限制性加性估值的多重图,[Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024] 也证明了这一点。
在这项工作中,我们进一步推进了现有技术水平,并证明了在多重图和普遍单调估值条件下,如果满足以下三个条件之一,则始终存在 EFX 分配:(a)多重图是二部图,或(b)每个代理的邻居数不超过 $\lceil \frac{n}{4} \rceil -1$,其中 $n$ 是代理的总数,或(c)最短的非平行边组成的环的长度至少为 6。