Fair-Share Allocations for Agents with Arbitrary Entitlements
Fair-Share Allocations for Agents with Arbitrary Entitlements
复制标题
具有任意权利的代理的公平份额分配
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
U. Feige
中科院分区：
文献类型：
--
作者：
Moshe Babaioff;Tomer Ezra;U. Feige
我们考虑的问题，公平分配不可分割的商品的n个代理人，没有转让。当代理人有平等的权利，最大份额（MMS）的既定概念作为一个有吸引力的公平标准，在那里有资格作为公平的，分配需要给每个代理人至少一个相当大的一部分，她的MMS。在本文中，我们考虑的情况下，任意（不平等）的权利。我们解释了在以前的尝试，MMS扩展到不平等的权利的缺点。我们的概念性贡献是引入了一个新的共享概念，即AnyPrice共享（APS），适用于具有任意权限的设置。代理人的AnyPrice份额是她可以保证自己的价值，如果她得到的预算等于她的权利，她买她的最高价值负担得起的设置时，项目是对立的定价与总价格等于总权利。即使对于平等权利的情况，这个概念也是新的，并且满足APS ≥ MMS，其中不等式有时是严格的。我们还提出了一种替代定义的APS作为一个最大化的问题（一个分数版本的MMS），并提供APS和以前的公平概念之间的比较。我们的主要结果涉及添加剂的估值和任意的权利，我们提供了一个多项式时间算法，使每个代理至少有3/5的分数，她的APS。这个算法也可以被看作是提供一个策略，在一定的自然投标游戏，这个策略确保每个代理，使用它至少有3/5的分数，她的APS，无论其他代理使用的策略。
We consider the problem of fair allocation of indivisible goods to n agents, with no transfers. When agents have equal entitlements, the well established notion of the maximin share (MMS) serves as an attractive fairness criterion, where to qualify as fair, an allocation needs to give every agent at least a substantial fraction of her MMS. In this paper we consider the case of arbitrary (unequal) entitlements. We explain shortcomings in previous attempts that extend the MMS to unequal entitlements. Our conceptual contribution is the introduction of a new notion of a share, the AnyPrice share (APS), that is appropriate for settings with arbitrary entitlements. The AnyPrice share of an agent is the value she can guarantee to herself if she is given a budget equal to her entitlement, and she buys her highest value affordable set when items are adversarially priced with a total price equal to the total entitlements. Even for the equal entitlements case, this notion is new, and satisfies APS ≥ MMS, where the inequality is sometimes strict. We also present an alternative definition for the APS as a maximization problem (a fractional version of the MMS), and provide comparisons between the APS and previous notions of fairness. Our main result concerns additive valuations and arbitrary entitlements, for which we provide a polynomial-time algorithm that gives every agent at least a 3/5-fraction of her APS. This algorithm can also be viewed as providing a strategy in a certain natural bidding game, and this strategy secures each agent that uses it at least a 3/5-fraction of her APS, regardless of the strategies used by other agents.
DOI：
10.1145/3391403.3399526
发表时间：
2019-02
期刊：
Proceedings of the 21st ACM Conference on Economics and Computation
影响因子：
--
作者：
J. Garg;Setareh Taki
通讯作者：
J. Garg;Setareh Taki