We study the problem of fair allocation of a set of indivisible items among agents with additive valuations, under cardinality constraints. In this setting, the items are partitioned into categories, each with its own limit on the number of items it may contribute to any bundle. We consider the fairness measure known as the maximin share (MMS) guarantee, and propose a novel polynomial-time algorithm for finding $1/2$-approximate MMS allocations for goods -- an improvement from the previously best available guarantee of $11/30$. For single-category instances, we show that a modified variant of our algorithm is guaranteed to produce $2/3$-approximate MMS allocations. Among various other existence and non-existence results, we show that a $(\sqrt{n}/(2\sqrt{n} - 1))$-approximate MMS allocation always exists for goods. For chores, we show similar results as for goods, with a $2$-approximate algorithm in the general case and a $3/2$-approximate algorithm for single-category instances. We extend the notions and algorithms related to ordered and reduced instances to work with cardinality constraints, and combine these with bag filling style procedures to construct our algorithms.
翻译:我们研究了在具有添加价值的代理人之间公平分配一组不可分割物品的问题,这是在基本限制下,在最基本限制下,我们研究了在具有添加价值的代理人之间公平分配一套不可分割物品的问题。在这一背景下,将物品分成若干类别,每个项目对它可能帮助任何捆绑的物品的数量都有自己的限制。我们考虑称为最大份额(MMS)保证的公平度标准,并提议一个新颖的多元时间算法,以寻找1/2美元接近MMS的货物分配款 -- -- 与以前最佳的11/30美元的保证相比,有了改进。对于单一类别的例子,我们表明我们的算法的修改变式保证产生2/3美元接近MMS的分配款。在各种存在和不存在的结果中,我们表明始终存在一个(sqrt{n}/(2\qrt{n}-1)-接近MMS的分配款。对于货物来说,我们显示了类似的结果,即从一般情况下的2美元接近的算法和单一类别案例的3/2美元近比值算法。我们把与订购和减少的情况有关的概念和算法扩大到带有基本限制的工作,并结合了这些装袋式。