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
APA
Vancouver
Author
Bibtex
}
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