标题： 关于受限图类上的近似MMS分配 显示英文标题

标题： On Approximate MMS Allocations on Restricted Graph Classes

摘要： 我们研究在存在连通性约束的情况下，对一组不可分商品进行公平分配的问题。 具体而言，我们假设商品表示为一个连通图的顶点，分配给代理的商品集合是该图的连通子图。 我们关注的是广泛研究的最多最少份额公平标准。 已经证明，即使没有连通性约束，即如果商品图是完全图，满足该标准的分配可能不存在。 鉴于此，自然地寻求近似分配，以保证每个代理获得价值至少为其最多最少份额值的常数分数的连通商品集合。 已知对于某些图类，如完全图、环和对于任何固定$d$的$d$-无爪图，这样的近似分配确实存在。 然而，对于所有图类，它们是否存在仍然是一个开放问题。 在本文中，我们继续系统地研究在受限图类上近似分配的存在性。 特别是，我们证明对于几个广泛研究的图类，包括块图、仙人掌图、完全多部图和分割图，这样的分配存在。 显示英文摘要

摘要： 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.