Complexity of finding Pareto-efficient allocations of highest welfare

Research output: Contribution to journal › Journal article › Research › peer-review

Standard

Complexity of finding Pareto-efficient allocations of highest welfare. / Biró, Péter; Gudmundsson, Jens.

In: European Journal of Operational Research, Vol. 91, No. 2, 2021, p. 614-628.

Research output: Contribution to journal › Journal article › Research › peer-review

Harvard

Biró, P & Gudmundsson, J 2021, 'Complexity of finding Pareto-efficient allocations of highest welfare', European Journal of Operational Research, vol. 91, no. 2, pp. 614-628. https://doi.org/10.1016/j.ejor.2020.03.018

APA

Biró, P., & Gudmundsson, J. (2021). Complexity of finding Pareto-efficient allocations of highest welfare. European Journal of Operational Research, 91(2), 614-628. https://doi.org/10.1016/j.ejor.2020.03.018

Vancouver

Biró P, Gudmundsson J. Complexity of finding Pareto-efficient allocations of highest welfare. European Journal of Operational Research. 2021;91(2):614-628. https://doi.org/10.1016/j.ejor.2020.03.018

Author

Biró, Péter ; Gudmundsson, Jens. / Complexity of finding Pareto-efficient allocations of highest welfare. In: European Journal of Operational Research. 2021 ; Vol. 91, No. 2. pp. 614-628.

Bibtex

@article{d2cc7abe93434c41b73160f8e5933def,
title = "Complexity of finding Pareto-efficient allocations of highest welfare",
abstract = "We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the object-allocating agency are encoded as edge weights in the acceptability graph. The welfare of an allocation is the sum of its edge weights. We introduce the constrained welfare-maximizing solution, which is the allocation of highest welfare among the Pareto-efficient allocations. We identify conditions under which this solution is easily determined from a computational point of view. For the unrestricted case, we formulate an integer program and find this to be viable in practice as it quickly solves a real-world instance of kindergarten allocation and large-scale simulated instances. Incentives to report preferences truthfully are discussed briefly.",
author = "P{\'e}ter Bir{\'o} and Jens Gudmundsson",
year = "2021",
doi = "10.1016/j.ejor.2020.03.018",
language = "English",
volume = "91",
pages = "614--628",
journal = "European Journal of Operational Research",
issn = "0377-2217",
publisher = "Elsevier",
number = "2",

}

RIS

TY - JOUR

T1 - Complexity of finding Pareto-efficient allocations of highest welfare

AU - Biró, Péter

AU - Gudmundsson, Jens

PY - 2021

Y1 - 2021

N2 - We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the object-allocating agency are encoded as edge weights in the acceptability graph. The welfare of an allocation is the sum of its edge weights. We introduce the constrained welfare-maximizing solution, which is the allocation of highest welfare among the Pareto-efficient allocations. We identify conditions under which this solution is easily determined from a computational point of view. For the unrestricted case, we formulate an integer program and find this to be viable in practice as it quickly solves a real-world instance of kindergarten allocation and large-scale simulated instances. Incentives to report preferences truthfully are discussed briefly.

AB - We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the object-allocating agency are encoded as edge weights in the acceptability graph. The welfare of an allocation is the sum of its edge weights. We introduce the constrained welfare-maximizing solution, which is the allocation of highest welfare among the Pareto-efficient allocations. We identify conditions under which this solution is easily determined from a computational point of view. For the unrestricted case, we formulate an integer program and find this to be viable in practice as it quickly solves a real-world instance of kindergarten allocation and large-scale simulated instances. Incentives to report preferences truthfully are discussed briefly.

U2 - 10.1016/j.ejor.2020.03.018

DO - 10.1016/j.ejor.2020.03.018

M3 - Journal article

VL - 91

SP - 614

EP - 628

JO - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 2

ER -

ID: 238675374