Fair Allocation of Indivisible Goods to Asymmetric Agents
Fair Allocation of Indivisible Goods to Asymmetric Agents
复制标题
不可分割的商品公平分配给不对称代理
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Hadi Yami
中科院分区：
文献类型：
--
作者：
Alireza Farhadi;M. Hajiaghayi;M. Ghodsi;Sébastien Lahaie;David M. Pennock;Masoud Seddighin;Saeed Seddighin;Hadi Yami
我们研究将不可分割的商品公平分配给具有不平等权利的代理人。公平分配一直是可分割和不可分割环境中许多研究的主题。我们的重点是货物不可分割且代理人权利不平等的情况。这个问题是 Procaccia 和 Wang (2014) 工作的概括，其中假设代理人关于他们的权利是对称的。尽管 Procaccia 和 Wang 表明在他们的设置中存在几乎公平（恒定近似）的分配，但我们的主要结果与他们的观察形成鲜明对比。我们表明，在某些情况下，有 n 个代理，当权利不一定相等时，任何分配都不能保证优于 1/n 近似的公平分配。此外，我们设计了一种简单的算法来确保 1/n 近似保证。
我们的第二个结果是该问题的限制版本，其中每个代理人对每种商品的估价受到他希望在公平分配中获得的总价值的限制。尽管这个假设看起来不失一般性，但我们证明它使我们能够通过贪婪算法找到 1/2 近似公平分配。最后，我们对现实世界的数据进行了一些实验，并表明，在实践中，公平分配是可能存在的。我们还通过显示问题的两个随机变体（即随机代理和随机项）的积极结果来支持我们的实验。
We study fair allocation of indivisible goods to agents with unequal entitlements. Fair allocation has been the subject of many studies in both divisible and indivisible settings. Our emphasis is on the case where the goods are indivisible and agents have unequal entitlements. This problem is a generalization of the work by Procaccia and Wang (2014) wherein the agents are assumed to be symmetric with respect to their entitlements. Although Procaccia and Wang show an almost fair (constant approximation) allocation exists in their setting, our main result is in sharp contrast to their observation. We show that, in some cases with n agents, no allocation can guarantee better than 1/n approximation of a fair allocation when the entitlements are not necessarily equal. Furthermore, we devise a simple algorithm that ensures a 1/n approximation guarantee.
Our second result is for a restricted version of the problem where the valuation of every agent for each good is bounded by the total value he wishes to receive in a fair allocation. Although this assumption might seem without loss of generality, we show it enables us to find a 1/2 approximation fair allocation via a greedy algorithm. Finally, we run some experiments on real-world data and show that, in practice, a fair allocation is likely to exist. We also support our experiments by showing positive results for two stochastic variants of the problem, namely stochastic agents and stochastic items.