  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.
