Complexity of finding Pareto-efficient allocations of highest welfare

Péter Biró and Jens Gudmundsson

No 2016, CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies

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.

Keywords: Assignment; Pareto-efficiency; Welfare-maximization; Complexity; Integerprogrammin (search for similar items in EconPapers)
JEL-codes: C6 C78 D61 (search for similar items in EconPapers)
Pages: 36 pages
Date: 2020-04
New Economics Papers: this item is included in nep-cmp, nep-des and nep-ore
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mtakti.hu/wp-content/uploads/2020/04/CERSIEWP202016.pdf (application/pdf)

Related works:
Journal Article: Complexity of finding Pareto-efficient allocations of highest welfare (2021)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:has:discpr:2016

Access Statistics for this paper

More papers in CERS-IE WORKING PAPERS from Institute of Economics, Centre for Economic and Regional Studies Contact information at EDIRC.
Bibliographic data for series maintained by Nora Horvath ( this e-mail address is bad, please contact ).