Indivisible Mixed Manna: On the Computability of MMS + PO Allocations

Abstract

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 $\alpha$-MMS allocation for the (near) best $\alpha \in (0,1]$ for which it exists, remains unresolved even for a goods manna with constantly many agents, while the problem of finding $\alpha$-MMS+PO allocation is unexplored for any $\alpha \in (0,1]$. We make significant progress on the above questions for a mixed manna. First, we show that for any $\alpha >0$, an $\alpha$-MMS allocation may not always exist, thus ruling out solving the problem for a fixed $\alpha$. Second, towards computing $\alpha$-MMS+PO allocation for the best possible $\alpha$, 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 $(\alpha -\epsilon )$-MMS and $\gamma$-PO allocation when given $\epsilon ,\gamma >0$, for the highest possible $\alpha \in (0,1]$. Second, we show that if either condition is not satisfied then finding an $\alpha$-MMS allocation for any $\alpha \in (0,1]$ is NP-hard, even when a solution exists for $\alpha =1$. To the best of our knowledge, ours is the first algorithm that ensures both approximate MMS and PO guarantees.

References in corpus (7)

• Solving Empirical Risk Minimization in the Current Matrix Multiplication Time
• EFX Exists for Three Agents
• Greedy Algorithms for Fair Division of Mixed Manna
• Dividing Bads is Harder than Dividing Goods: On the Complexity of Fair and Efficient Division of Chores
• Weighted Maxmin Fair Share Allocation of Indivisible Chores
• Jealousy-freeness and other common properties in Fair Division of Mixed Manna
• Maximin share allocations on cycles