论文标题
通过不可分割的商品与最大值项目达到比例性
Achieving Proportionality up to the Maximin Item with Indivisible Goods
论文作者
论文摘要
我们研究了相当分配不可分割的商品的问题，并专注于相称的经典公平概念。众所周知，货物的不可分割性在实现公平性方面构成了高度非平凡的障碍，并且非常活跃的研究旨在使用适当的近似公平概念来规避它们。最近的工作已经确定，即使在小实例中，即使是相称的近似版本（Propx）也可能无法实现，而最著名的可实现近似值（Prop1）也弱得多。我们将比例性概念介绍到最大值项目（Propm），并展示如何达到满足此概念的分配，以涉及多达五个具有添加估值的代理商的情况。 Propm在Prop1和Propx之间提供了充分动机的中间场地，同时还捕获了经过良好研究的最大值共享（MMS）基准的某些元素：相称性的另一种放松，引起了很多关注。
We study the problem of fairly allocating indivisible goods and focus on the classic fairness notion of proportionality. The indivisibility of the goods is long known to pose highly non-trivial obstacles to achieving fairness, and a very vibrant line of research has aimed to circumvent them using appropriate notions of approximate fairness. Recent work has established that even approximate versions of proportionality (PROPx) may be impossible to achieve even for small instances, while the best known achievable approximations (PROP1) are much weaker. We introduce the notion of proportionality up to the maximin item (PROPm) and show how to reach an allocation satisfying this notion for any instance involving up to five agents with additive valuations. PROPm provides a well-motivated middle-ground between PROP1 and PROPx, while also capturing some elements of the well-studied maximin share (MMS) benchmark: another relaxation of proportionality that has attracted a lot of attention.
