Greedy Algorithms for Fair Division of Mixed Manna
This work addresses fair resource allocation in multi-agent systems with mixed utilities, providing theoretical insights and algorithms that are incremental to existing fair division literature.
The paper tackles the problem of fair division of mixed manna, where items can have positive, zero, or negative utilities for agents, by analyzing the existence and computability of allocations under fairness concepts like EF1, EFX, and EFX3, and efficiency concepts like PO, with results including impossibility proofs for some cases and polynomial-time algorithms for others, such as showing that EFX and PO allocations always exist with identical utilities.
We consider a multi-agent model for fair division of mixed manna (i.e. items for which agents can have positive, zero or negative utilities), in which agents have additive utilities for bundles of items. For this model, we give several general impossibility results and special possibility results for three common fairness concepts (i.e. EF1, EFX, EFX3) and one popular efficiency concept (i.e. PO). We also study how these interact with common welfare objectives such as the Nash, disutility Nash and egalitarian welfares. For example, we show that maximizing the Nash welfare with mixed manna (or minimizing the disutility Nash welfare) does not ensure an EF1 allocation whereas with goods and the Nash welfare it does. We also prove that an EFX3 allocation may not exist even with identical utilities. By comparison, with tertiary utilities, EFX and PO allocations, or EFX3 and PO allocations always exist. Also, with identical utilities, EFX and PO allocations always exist. For these cases, we give polynomial-time algorithms, returning such allocations and approximating further the Nash, disutility Nash and egalitarian welfares in special cases.