Abstract. We consider fair allocation of indivisible items under additive utilities. When the utilities can be negative, the existence and complexity of an allocation that satisfies Pareto optimality and proportionality up to one item (PROP1) is an open problem. We show that there exists a strongly polynomial-time algorithm that always computes an allocation satisfying Pareto optimality and proportionality up to one item even if the utilities are mixed and the agents have asymmetric weights. We point out that the result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.
Recently, REF propose a polynomial-time algorithm for computing an allocation of a pool of goods and chores that satisfies both Pareto optimality and weighted proportionality up to one item (PROP1) for agents with asymmetric weights.
A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation
ArXiv
ArXiv
Mathematics Computer Science