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

Haris Aziz; Hervé Moulin; Fedor Sandomirskiy

doi:10.1016/j.orl.2020.07.005

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

Haris Aziz, Hervé Moulin, Fedor Sandomirskiy

Research output: Contribution to journal › Article › peer-review

61 Scopus citations

Abstract

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.

Original language	English (US)
Pages (from-to)	573-578
Number of pages	6
Journal	Operations Research Letters
Volume	48
Issue number	5
DOIs	https://doi.org/10.1016/j.orl.2020.07.005
State	Published - Sep 2020
Externally published	Yes

All Science Journal Classification (ASJC) codes

Software
Management Science and Operations Research
Industrial and Manufacturing Engineering
Applied Mathematics

Keywords

Fair division
Pareto optimality
Proportionality

Access to Document

10.1016/j.orl.2020.07.005

Cite this

@article{c9696f66283342faabd956ed7cd304eb,

title = "A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation",

abstract = "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.",

keywords = "Fair division, Pareto optimality, Proportionality",

author = "Haris Aziz and Herv{\'e} Moulin and Fedor Sandomirskiy",

note = "Publisher Copyright: {\textcopyright} 2020",

year = "2020",

month = sep,

doi = "10.1016/j.orl.2020.07.005",

language = "English (US)",

volume = "48",

pages = "573--578",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

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

AU - Aziz, Haris

AU - Moulin, Hervé

AU - Sandomirskiy, Fedor

PY - 2020/9

Y1 - 2020/9

N2 - 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.

AB - 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.

KW - Fair division

KW - Pareto optimality

KW - Proportionality

UR - http://www.scopus.com/inward/record.url?scp=85087938873&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85087938873&partnerID=8YFLogxK

U2 - 10.1016/j.orl.2020.07.005

DO - 10.1016/j.orl.2020.07.005

M3 - Article

AN - SCOPUS:85087938873

SN - 0167-6377

VL - 48

SP - 573

EP - 578

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this