# A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation

arXiv: https://arxiv.org/abs/1909.00740 · HTML: https://mlsanity.com/paper/1909.00740/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Sep 2019.

## Built on by (most cited first, 6 of 6)

- [Online Fair Division with Additional Information](https://mlsanity.com/paper/2505.24503/) (2025)
- [Approximate Proportionality in Online Fair Division](https://mlsanity.com/paper/2508.03253/) (2025)
- [Fast Online Value-Maximizing Prediction Sets with Conformal Cost Control](https://mlsanity.com/paper/2302.00839/) (2023)
- [Understanding EFX Allocations: Counting and Variants](https://mlsanity.com/paper/2504.03951/) (2025)
- [PROPm Allocations of Indivisible Goods to Multiple Agents](https://mlsanity.com/paper/2105.11348/) (2021)
- [(Almost) Envy-Free, Proportional and Efficient Allocations of an Indivisible Mixed Manna](https://mlsanity.com/paper/2202.02672/) (2022)

## Abstract (arXiv)

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.