证明了在特定条件下,多图结构下可实现无嫉妒的公平分配。
On the existence of EFX allocations in multigraphs
- 基于多图结构建模资源分配,结合图论约束条件
- 在三类条件下(二分图、低度邻居、长环)保证存在EFX解
- 为公平分配难题提供新理论支持,适合算法与博弈研究者
我们研究将不可分物品公平分配给多个具有集合估值函数的代理问题。公平性以“对任意物品无嫉妒”(EFX)为准,即任一代理不嫉妒其他代理所得物品的任何真子集。是否存在EFX分配是公平分配领域的重大开放问题,目前仅在特殊情况下有正面结果。[George Christodoulou et al., 2023] 引入基于图结构的估值限制:顶点代表代理,边代表物品,每个代理对非相邻物品的边际价值为零(即不关心)。已有研究证明简单图上一般单调估值下存在EFX分配,以及多图上受限加性估值下也存在。本文进一步推进:在多图和一般单调估值下,若满足以下任一条件,则总存在EFX分配:(a) 多图是二分图;(b) 每个代理邻居数不超过 ⌈n/4⌉−1,其中 n 为总代理数;(c) 非平行边构成的最短环长度至少为6。
原文摘要 · Abstract (English)
We study the problem of "fairly" dividing indivisible goods to several agents that have valuation set functions over the sets of goods. As fair we consider the allocations that are envy-free up to any good (EFX), i.e., no agent envies any proper subset of the goods given to any other agent. The existence or not of EFX allocations is a major open problem in Fair Division, and there are only positive results for special cases. [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023] introduced a restriction on the agents' valuations according to a graph structure: the vertices correspond to agents and the edges to goods, and each vertex/agent has zero marginal value (or in other words, they are indifferent) for the edges/goods that are not adjacent to them. The existence of EFX allocations has been shown for simple graphs with general monotone valuations [George Christodoulou, Amos Fiat, Elias Koutsoupias, Alkmini Sgouritsa 2023], and for multigraphs for restricted additive valuations [Alireza Kaviani, Masoud Seddighin, Amir Mohammad Shahrezaei 2024]. In this work, we push the state-of-the-art further, and show that the EFX allocations always exists in multigraphs and general monotone valuations if any of the following three conditions hold: either (a) the multigraph is bipartite, or (b) each agent has at most $\lceil \frac{n}{4} \rceil -1$ neighbors, where $n$ is the total number of agents, or (c) the shortest cycle with non-parallel edges has length at least 6.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。