研究在特定图结构下如何公平分配不可分物品，确保每人获得价值不低于其最大最小份额的连通物品组。
On Approximate MMS Allocations on Restricted Graph Classes
- 针对连通子图约束下的物品分配问题，提出近似最大最小份额分配方案。
- 证明在块图、仙人掌图、完全多部图和分裂图等类图上存在此类近似分配。
- 为复杂图结构上的公平分配提供理论保障，适合研究公平算法与组合优化者参考。
我们研究在连通性约束下对不可分物品进行公平分配的问题。具体而言，将物品视为连通图的顶点，要求分配给各参与者的物品集合构成该图的连通子图。研究聚焦于广泛使用的最大最小份额（MMS）公平性标准。已知即使在无连通性限制的情况下（如物品图为完全图），满足该标准的分配也可能不存在。因此，自然考虑近似分配：即保证每位参与者获得的连通物品组价值至少为其个人最大最小份额的一个常数比例。已有结果表明，在完全图、环图以及任意固定 $d$-爪自由图等图类上，此类近似分配确实存在。然而，对于所有图类是否存在仍为开放问题。本文继续系统研究受限图类上近似分配的存在性，证明在块图、仙人掌图、完全多部图和分裂图等几类经典图类上，此类近似分配均存在。
原文摘要 · Abstract (English)
We study the problem of fair division of a set of indivisible goods with connectivity constraints. Specifically, we assume that the goods are represented as vertices of a connected graph, and sets of goods allocated to the agents are connected subgraphs of this graph. We focus on the widely-studied maximin share criterion of fairness. It has been shown that an allocation satisfying this criterion may not exist even without connectivity constraints, i.e., if the graph of goods is complete. In view of this, it is natural to seek approximate allocations that guarantee each agent a connected bundle of goods with value at least a constant fraction of the maximin share value to the agent. It is known that for some classes of graphs, such as complete graphs, cycles, and $d$-claw-free graphs for any fixed $d$, such approximate allocations indeed exist. However, it is an open problem whether they exist for the class of all graphs. In this paper, we continue the systematic study of the existence of approximate allocations on restricted graph classes. In particular, we show that such allocations exist for several well-studied classes, including block graphs, cacti, complete multipartite graphs, and split graphs.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。