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

DOI10.1016/j.orl.2020.07.005zbMath1478.91091arXiv1909.00740OpenAlexW3041947696MaRDI QIDQ2661522

Fedor Sandomirskiy, Haris Aziz, Hervé Moulin

Publication date: 7 April 2021

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1909.00740

zbMATH Keywords

Pareto optimalityfair divisionproportionality

Mathematics Subject Classification ID

Multi-objective and goal programming (90C29) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items

Almost envy-freeness for groups: improved bounds via discrepancy theory, When dividing mixed manna is easier than dividing goods: competitive equilibria with a constant number of chores, Efficient Fair Division with Minimal Sharing, Computing welfare-maximizing fair allocations of indivisible goods, Fair division of indivisible goods: recent progress and open questions, Approximately EFX allocations for indivisible chores, Weighted fair division with matroid-rank valuations: monotonicity and strategyproofness, Picking sequences and monotonicity in weighted fair division, Fair in the Eyes of Others

Cites Work

• Efficient reallocation under additive and responsive preferences
• On the Complexity of Efficiency and Envy-Freeness in Fair Division of Indivisible Goods with Additive Preferences
• Fair Allocation of Indivisible Goods to Asymmetric Agents