Complexity of finding Pareto-efficient allocations of highest welfare

Biró, Péter and Gudmundsson, Jens (2020) Complexity of finding Pareto-efficient allocations of highest welfare. European Journal of Operational Research, 2020 . DOI

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL:


We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the objectallocating 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.

Item Type:Article
Uncontrolled Keywords:assignment, Pareto-efficiency, welfare-maximization, complexity, integer programming
ID Code:6107
Deposited By: MTMT SWORD
Deposited On:30 Nov 2020 12:10
Last Modified:30 Nov 2020 12:12

Repository Staff Only: item control page


Downloads per month over past year

View more statistics