Complexity of finding Pareto-efficient allocations of highest welfare

Research output: Contribution to journalJournal articlepeer-review

Documents

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.
Original languageEnglish
JournalEuropean Journal of Operational Research
Volume91
Issue number2
Pages (from-to)614-628
Number of pages15
ISSN0377-2217
DOIs
Publication statusPublished - 2021

Number of downloads are based on statistics from Google Scholar and www.ku.dk


No data available

ID: 238675374