• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

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

Operations Research Letters. 2020. Vol. 48. No. 5. P. 573-578.
Moulin H., Aziz H., Sandomirskiy F.

We consider fair allocation of indivisible items under additive utilities. 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. The result does not hold if either of Pareto optimality or PROP1 is replaced with slightly stronger concepts.