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. One example of such a problem is allocating seats in a multitrack conference. 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. We extend the notions and algorithms related to ordered and reduced instances to work with cardinality constraints, and combine these with a bag filling style procedure. Our algorithm improves on that of Biswas and Barman (IJCAI-18), with its approximation ratio of $1/3$. We also present an optimizing algorithm, which for each instance, instead of fixing $\alpha = 1/2$, uses bisection to find the largest $\alpha$ for which our algorithm obtains a valid $\alpha$-approximate MMS allocation. Numerical tests show that our algorithm finds strictly better approximations than the guarantee of $1/2$ for most instances, in many cases surpassing $3/5$. The optimizing version of the algorithm produces MMS allocations in a comparable number of instances to that of Biswas and Barman's algorithm, on average achieving a better approximation when MMS is not obtained.
翻译:我们研究了在具有添加价值的代理商中公平分配一组不可分割项目的问题,在基本限制之下,我们研究了如何在具有添加价值的代理商中公平分配一组不可分割的项目的问题;在这种设置中,项目被分成类别,每个项目都对它可能帮助的任何捆绑的项目数量有其自己的限制;这种问题的一个例子是在多轨会议上分配席位;我们考虑所谓的最大份额保证(MMS)的公平度度量,并提议一个新颖的多元时间算法,以找到1/2美元接近MMS的分配额;我们把与订购和减少的事件有关的概念和算法扩大到与主要限制的工作,并将这些概念和算法与包装风格程序结合起来;我们的算法改进了Biswas和Barman(IJCAI-18)的算法,其近似比率为1/3美元;我们还提出了一种最优化的算法,即“最大份额”=1/2美元,用双倍算法找出我们算法获得有效美元-近似MMS的分配额;数字测试表明,我们的算法在最大比例1/2MS的公式中发现,比最高比例为1/5的比最高分配额。