论文标题
（几乎）不可分割的混合甘露
(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna
论文作者
论文摘要
我们研究了一组不可分割的物品对一组代理的不可分割的物品的公平分配的问题，其中每个项目对某些代理商来说可能是一个好的（积极价值），而对其他代理商则可能是不良的（负价），即混合甘露。作为公平的概念，我们可以认为，嫉妒性和相称性的最强烈放松，即对任何物品（EFX和EFX $ _0 $）的无嫉妒，而与Maximin Good或任何Bad Bad（Propmx和Propmx and Propmx $ _0 $）的比例成比例。我们的效率概念是帕累托（Pareto）的概念（PO）。 我们研究两种类型的实例： （i）可分开的，可以将物品集可以分配到商品和坏处，以及（ii）限制的混合商品（RMG），对于每个项目$ j $，每个代理都有$ j $的非阳性价值，或者在相同的$ v_j> 0 $上都有$ j $的值$ j $。我们获得以下多项式时间算法： （i）可分离实例：propmx $ _0 $分配。 （ii）RMG实例：让纯粹的坏人成为每个人都否定的项目集。 - 普通纯坏的Propmx分配。 -EFX+PropMX分配，用于相同订购的纯坏。 -EFX+PROPMX+相同纯坏的PO分配。 最后，如果RMG实例进一步仅限于所有$ v_j $相同的二进制混合商品，我们将加强结果以保证EFX $ _0 $和PROPMX $ _0 $。
We study the problem of finding fair and efficient allocations of a set of indivisible items to a set of agents, where each item may be a good (positively valued) for some agents and a bad (negatively valued) for others, i.e., a mixed manna. As fairness notions, we consider arguably the strongest possible relaxations of envy-freeness and proportionality, namely envy-free up to any item (EFX and EFX$_0$), and proportional up to the maximin good or any bad (PropMX and PropMX$_0$). Our efficiency notion is Pareto-optimality (PO). We study two types of instances: (i) Separable, where the item set can be partitioned into goods and bads, and (ii) Restricted mixed goods (RMG), where for each item $j$, every agent has either a non-positive value for $j$, or values $j$ at the same $v_j>0$. We obtain polynomial-time algorithms for the following: (i) Separable instances: PropMX$_0$ allocation. (ii) RMG instances: Let pure bads be the set of items that everyone values negatively. - PropMX allocation for general pure bads. - EFX+PropMX allocation for identically-ordered pure bads. - EFX+PropMX+PO allocation for identical pure bads. Finally, if the RMG instances are further restricted to binary mixed goods where all the $v_j$'s are the same, we strengthen the results to guarantee EFX$_0$ and PropMX$_0$ respectively.
