Maximin Shares Under Cardinality Constraints
Maximin Shares Under Cardinality Constraints
复制标题
DOI：
10.1007/978-3-031-20614-6_11
复制
发表时间：
2021-06
期刊：
影响因子：
--
通讯作者：
Halvard Hummel;Magnus Lie Hetland
中科院分区：
文献类型：
--
作者：
Halvard Hummel;Magnus Lie Hetland
我们研究了基数约束下，在具有附加值的代理之间公平分配一组不可分项目的问题。在此设置中，项目被划分为类别，每个类别都有自己的项目数量限制，它可以贡献给任何捆绑包。我们认为公平性措施被称为themaximin份额（MMS）的保证，并提出了一种新的多项式时间算法，找到1/2近似MMS分配货物的改进，从以前最好的保证11/30。对于单类别的情况下，我们表明，我们的算法的修改后的变体是保证产生2/3近似MMS分配。在各种其他的存在性和不存在的结果，我们表明，a-近似MMS分配总是存在的商品。对于杂务，我们展示了与商品相似的结果，在一般情况下使用2-近似算法，对于单类别实例使用3/2-近似算法。我们扩展了与有序和约简实例相关的概念和算法，使其适用于基数约束，并将这些概念和算法与袋填充式过程联合收割机相结合来构建我们的算法。
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 themaximin 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-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 toorderedandreduced instancesto work with cardinality constraints, and combine these withbag fillingstyle procedures to construct our algorithms.