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$.
翻译:公平分割不可分割货物的问题最近引起了人们的极大关注,在可辨别货物环境中总是可以满足嫉妒自由的突出标准(例如,见\cite{BT95}),但在不可分割货物环境中往往不能满足,这导致许多商品的放松。我们研究了存在最大份额分配(MMS)的问题,这是这种放松的一个问题。以前的工作表明,保证在所有情况下都存在多边管理系统拨款,如果有n美元玩家,如果有$=leq n+4美元,则有m美元。我们将这一保证扩大到$=n+5美元,并表明同样的保证不能达到n+6美元。