论文标题
不可分割的混合甘露：关于MMS + PO分配的可计算性
Indivisible Mixed Manna: On the Computability of MMS + PO Allocations
论文作者
论文摘要
在本文中，我们启动了研究不可分割的混合甘露的公平有效分配的研究：在最大含量份额（MMS）公平概念（MMS）和Pareto -Optimation（PO）的公平概念下，n个药物之间的不可分割的项目分配了不可分割的项目。混合的甘露可以使某些物品对某些代理商有益，而对其他代理商则是一种琐事。找到（近）最佳$α\ in（0,1] $的$α$ -MMS分配的问题，即使对于经常有许多代理商的商品甘露来说，也无法解决，而找到$α$ -MMMS+PO分配的问题尚未针对任何$α\ in（0,1,1] $中的任何$α\。 我们在上述混合甘露的问题上取得了重大进展。首先，我们表明，对于任何$α> 0 $，可能总是存在$α$ -MMS分配，因此排除解决固定$α$的问题。其次，要以最佳的$α$计算$α$ -MMS+PO分配，我们获得了二分法结果：我们得出了两个条件，并表明在这两个条件下问题是可以解决的，同时丢弃了问题，这使问题棘手。这两个条件是：（i）代理的数量是常数，并且（ii）对于每个代理，她的所有项目的绝对值至少是所有商品或所有杂货的总数（绝对）值的恒定因素。 特别是，首先，对于满足（i）和（ii）的实例，我们设计了PTA-一种有效的算法，可以找到$（α-ε）$ -MMS和$γ$ -PO分配时，如果给出$α，γ> 0 $，以最高的$α\ in（0,1] $。 $α\ in（0,1] $是np-hard，即使存在解决方案的$α= 1 $。据我们所知，我们的第一个算法是确保近似MMS和PO保证的第一个算法。
In this paper we initiate the study of finding fair and efficient allocations of an indivisible mixed manna: Divide m indivisible items among n agents under the fairness notion of maximin share (MMS) and the efficiency notion of Pareto optimality (PO). A mixed manna allows an item to be a good for some agents and a chore for others. The problem of finding $α$-MMS allocation for the (near) best $α\in(0,1]$ for which it exists, remains unresolved even for a goods manna with constantly many agents, while the problem of finding $α$-MMS+PO allocation is unexplored for any $α\in(0,1]$. We make significant progress on the above questions for a mixed manna. First, we show that for any $α>0$, an $α$-MMS allocation may not always exist, thus ruling out solving the problem for a fixed $α$. Second, towards computing $α$-MMS+PO allocation for the best possible $α$, we obtain a dichotomous result: We derive two conditions and show that the problem is tractable under these two conditions, while dropping either renders the problem intractable. The two conditions are: (i) number of agents is a constant, and (ii) for every agent, her absolute value for all the items is at least a constant factor of her total (absolute) value for all the goods or all the chores. In particular, first, for instances satisfying (i) and (ii) we design a PTAS - an efficient algorithm to find an $(α-ε)$-MMS and $γ$-PO allocation when given $ε,γ>0$, for the highest possible $α\in(0,1]$. Second, we show that if either condition is not satisfied then finding an $α$-MMS allocation for any $α\in(0,1]$ is NP-hard, even when a solution exists for $α=1$. To the best of our knowledge, ours is the first algorithm that ensures both approximate MMS and PO guarantees.
