Guaranteeing Maximin Shares: Some Agents Left Behind
Guaranteeing Maximin Shares: Some Agents Left Behind
复制标题
DOI：
10.24963/ijcai.2021/34
复制
发表时间：
2021-05
期刊：
影响因子：
--
通讯作者：
Hadi Hosseini;Andrew Searns
中科院分区：
文献类型：
--
作者：
Hadi Hosseini;Andrew Searns
最大份额保证是分配不可分割物品时理想的公平概念。虽然MMS分配并不总是存在，但已经开发了几种近似技术，以确保所有代理都获得其最大份额的一小部分。我们专注于另一种近似概念，基于智能体总体，寻求保证一小部分智能体的MMS。我们证明了最优逼近算法不能满足超过常数数量的智能体，并讨论了除一个智能体外所有智能体的MMS的存在性和计算，以及它与近似MMS保证的关系。然后，我们证明了分配的存在性，保证了2/3的代理的MMS，并设计了一个多项式时间算法，该算法最多可为9个代理实现这一界限。我们的结果的一个关键含义是分配的存在，通过将商品划分为3n/2个束来保证代理收到的价值，改进了当商品划分为2n-2个束时最著名的保证。最后，利用合成数据进行了实证实验。
The maximin share (MMS) guarantee is a desirable fairness notion for allocating indivisible goods. While MMS allocations do not always exist, several approximation techniques have been developed to ensure that all agents receive a fraction of their maximin share. We focus on an alternative approximation notion, based on the population of agents, that seeks to guarantee MMS for a fraction of agents. We show that no optimal approximation algorithm can satisfy more than a constant number of agents, and discuss the existence and computation of MMS for all but one agent and its relation to approximate MMS guarantees. We then prove the existence of allocations that guarantee MMS for 2/3 of agents, and devise a polynomial time algorithm that achieves this bound for up to nine agents. A key implication of our result is the existence of allocations that guarantee the value that an agent receives by partitioning the goods into 3n/2 bundles, improving the best known guarantee when goods are partitioned into 2n-2 bundles. Finally, we provide empirical experiments using synthetic data.