Groupwise Maximin Fair Allocation of Indivisible Goods
Groupwise Maximin Fair Allocation of Indivisible Goods
复制标题
不可分割商品的分组最大化公平分配
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Y. Narahari
中科院分区：
文献类型：
--
作者：
Siddharth Barman;Arpita Biswas;Sanath Kumar Krishnamurthy;Y. Narahari
我们以公平的方式研究了在n个代理商中分配不可分割的商品的问题。对于这个问题，Maximin共享（MMS）是一个经过良好研究的解决方案概念，提供了公平的阈值。具体而言，最大值份额被定义为代理商可以保证自己的最低效用，当被要求将货物集划分为n个捆绑包中，以使剩下的（N-1）代理商在对手方面挑选捆绑包。如果每个代理商都得到一个至少是她的最大值份额的捆绑包，则认为分配是公平的。即使Maximin份额为公平性提供了自然的基准，但它具有自己的缺点，尤其是不足以排除不满意的分配。受这些考虑的激励，在这项工作中，我们定义了更强的公平概念，称为GroupWise Maximin份额保证（GMMS）。在GMM中，我们要求最大值共享保证不仅在大捆绑包中实现，而且还可以在所有代理亚组中实现。因此，该解决方案概念增强了MMS并提供了前公平保证。我们表明，在特定的设置中，GMMS分配始终存在。我们还建立了在加性估值下的近似GMM分配的存在，并开发了多项式时间算法以查找此类分配。此外，我们建立了一个公平的规模，其中我们表明GMM意味着近似嫉妒的疯子。最后，我们从经验上证明了在大量随机生成的实例中存在GMMS分配的存在。对于相同的实例，我们还表明，我们的算法达到的近似因素比已建立的最差案例结合更好。
We study the problem of allocating indivisible goods among n agents in a fair manner. For this problem, maximin share (MMS) is a well-studied solution concept which provides a fairness threshold. Specifically, maximin share is defined as the minimum utility that an agent can guarantee for herself when asked to partition the set of goods into n bundles such that the remaining (n-1) agents pick their bundles adversarially. An allocation is deemed to be fair if every agent gets a bundle whose valuation is at least her maximin share. Even though maximin shares provide a natural benchmark for fairness, it has its own drawbacks and, in particular, it is not sufficient to rule out unsatisfactory allocations. Motivated by these considerations, in this work we define a stronger notion of fairness, called groupwise maximin share guarantee (GMMS). In GMMS, we require that the maximin share guarantee is achieved not just with respect to the grand bundle, but also among all the subgroups of agents. Hence, this solution concept strengthens MMS and provides an ex-post fairness guarantee. We show that in specific settings, GMMS allocations always exist. We also establish the existence of approximate GMMS allocations under additive valuations, and develop a polynomial-time algorithm to find such allocations. Moreover, we establish a scale of fairness wherein we show that GMMS implies approximate envy freeness. Finally, we empirically demonstrate the existence of GMMS allocations in a large set of randomly generated instances. For the same set of instances, we additionally show that our algorithm achieves an approximation factor better than the established, worst-case bound.