Complexity of finding Pareto-efficient allocations of highest welfare

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. (c) 2020 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/)

Automated summary

This paper discusses the allocation of objects to agents, encoding welfare judgments as edge weights in an acceptability graph, introducing a constrained welfare-maximizing solution, and briefly discussing incentives for reporting preferences truthfully.