Indivisible Mixed Manna: On the Computability of MMS+PO Allocations
Indivisible Mixed Manna: On the Computability of MMS+PO Allocations
复制标题
不可分割的混合甘露：关于 MMS PO 分配的可计算性
DOI：
10.1145/3465456.3467553
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Taki, Setareh
中科院分区：
文献类型：
--
作者：
Kulkarni, Rucha;Mehta, Ruta;Taki, Setareh
在这篇文章中，我们研究了在N个具有加性估值的代理人集合中寻找公平有效的分配混合甘露的问题，即M个离散的商品/家务物品的集合。我们注意到，混合甘露允许一项物品对一些代理人来说是好的(正价值)，而对另一些代理人来说是家务(负价值)，从而严格地推广了广泛研究的商品(家务)甘露。为了衡量公平和效率，我们分别考虑了流行和研究广泛的最大份额(MMS)和帕累托最优(PO)概念。MMS分配是指每个代理至少获得她的MMS值。然而，[6]表明MMS分配并不总是存在的。这促使了一系列关于𝛼-MMS分配的有效计算的工作，其中每个代理获得至少𝛼(1/𝛼)倍于她的MMS值的货物(家务)甘露，以获得逐渐更好的𝛼∈[0，1]；到目前为止已知的最好的因子是
In this paper we study the problem of finding fair and efficient allocations of a mixed manna, ie, a set M of discrete items that are goods/chores, among a set N of agents with additive valuations. We note that a mixed manna allows an item to be a good (positively valued) for some agents, and a chore (negatively valued) for others, and thereby strictly generalizes the extensively studied goods (chores) manna. To measure fairness and efficiency we consider the popular and well studied notions of maximin-share (MMS) and Pareto optimality (PO) respectively.An MMS allocation is one where every agent gets at least her MMS value. However,[6] showed that an MMS allocation may not always exist. This prompted a series of works on the efficient computation of 𝛼-MMS allocations, where every agent gets at least 𝛼 (1/𝛼) times her MMS value for a goods (chores) manna, for progressively better 𝛼∈[0, 1]; the best factor known so far is
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
DOI：
--
发表时间：
2019
期刊：
ACM Conference on Economics and Computation
影响因子：
--
作者：
Xin Huang;P. Lu
通讯作者：
P. Lu