论文标题
改进的最大值的下限共享商品分配
An Improved Lower Bound for Maximin Share Allocations of Goods
论文作者
论文摘要
不可分割的商品的公平划分问题最近引起了很多关注。嫉妒柔性的突出指标始终可以在可划分的商品设置中得到满足（例如，请参见\ cite {bt95}），但在不可分割的商品设置中通常无法满足。这导致了许多放松。我们研究{\ em最大值共享（MMS）}分配的存在，这就是这样的放松。先前的工作表明，如果$ n $ players和$ m $ leq n+4 $，则保证所有情况下的MMS分配都存在。我们将此保证扩展到$ M = N+5 $的情况，并表明相同的保证在$ M = N+6 $的情况下失败。
The problem of fair division of indivisible goods has been receiving much attention recently. The prominent metric of envy-freeness can always be satisfied in the divisible goods setting (see for example \cite{BT95}), but often cannot be satisfied in the indivisible goods setting. This has led to many relaxations thereof being introduced. We study the existence of {\em maximin share (MMS)} allocations, which is one such relaxation. Previous work has shown that MMS allocations are guaranteed to exist for all instances with $n$ players and $m$ goods if $m \leq n+4$. We extend this guarantee to the case of $m = n+5$ and show that the same guarantee fails for $m = n+6$.
