Two Algorithms for Additive and Fair Division of Mixed Manna

Abstract

We consider a fair division model in which agents have positive, zero and negative utilities for items. For this model, we analyse one existing fairness property - EFX - and three new and related properties - EFX${}_0$, EFX${}^3$ and EF1${}^3$ - in combination with Pareto-optimality. With general utilities, we give a modified version of an existing algorithm for computing an EF1${}^3$ allocation. With $-\alpha /0/\alpha$ utilities, this algorithm returns an EFX${}^3$ and PO allocation. With absolute identical utilities, we give a new algorithm for an EFX and PO allocation. With $-\alpha /0/\beta$ utilities, this algorithm also returns such an allocation. We report some new impossibility results as well.

14 pages, 2 algorithms, 1 table, 1 figure, KI 2020