Ordinal Maximin Share Approximation for Goods
Ordinal Maximin Share Approximation for Goods
复制标题
DOI：
10.1613/jair.1.13317
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Hadi Hosseini;Andrew Searns;Erel Segal-Halevi
中科院分区：
文献类型：
--
作者：
Hadi Hosseini;Andrew Searns;Erel Segal-Halevi
在不可分割货物的公平分配中，d中取最大最小份额（MMS）是代理人通过将货物分成d个捆绑包并选择最不偏好的捆绑包所能保证的价值。大多数现有的作品的目的是保证所有的代理人的一个恒定的分数，他们的1出n MMS。但这种保证对代理人基数估值的小扰动很敏感。我们考虑一个更强大的近似概念，这只取决于代理的有序排列的束。本文证明了对于任意整数<$1，商品分配问题存在一个从<$1到<$3n/2的整数（<$1 + 1/2）n的整数MMS分配问题，并给出了一个多项式时间算法，当<$1 =1时，该算法能找到一个从<$3n/2到1的整数MMS分配问题.我们进一步开发了一个算法，提供了一个较弱的序数近似MMS的任何n> 1。
In fair division of indivisible goods, ℓ-out-of-d maximin share (MMS) is the value that an agent can guarantee by partitioning the goods into d bundles and choosing the ℓ least preferred bundles. Most existing works aim to guarantee to all agents a constant fraction of their 1-out-of-n MMS. But this guarantee is sensitive to small perturbation in agents' cardinal valuations. We consider a more robust approximation notion, which depends only on the agents' ordinal rankings of bundles. We prove the existence of ℓ-out-of-⌊(ℓ + 1/2)n⌋ MMS allocations of goods for any integer ℓ ≥ 1, and present a polynomial-time algorithm that finds a 1-out-of-⌈3n/2⌉ MMS allocation when ℓ=1. We further develop an algorithm that provides a weaker ordinal approximation to MMS for any ℓ > 1.