Assignment problems with complementarities

Thành Nguyen, Ahmad Peivandi and Rakesh Vohra

Journal of Economic Theory, 2016, vol. 165, issue C, 209-241

Abstract: The problem of allocating bundles of indivisible objects without transfers arises in many practical settings, including the assignment of courses to students, of siblings to schools, and of truckloads of food to food banks. In these settings, the complementarities in preferences are small compared with the size of the market. We exploit this to design mechanisms satisfying constrained efficiency and asymptotic strategy-proofness. We introduce two mechanisms, one for cardinal and the other for ordinal preferences. When agents do not want bundles of size larger than k, these mechanisms over-allocate each good by at most k−1 units, ex-post. These results are based on a generalization of the Birkhoff–von Neumann theorem on how probability shares of bundles can be expressed as lotteries over approximately feasible allocations, which is of independent interest.

Keywords: One sided matching; Complementarities; Strategy-proof; Efficient; Envy-free; Mechanism (search for similar items in EconPapers)
JEL-codes: C78 D47 D82 (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (23)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0022053116300151
Full text for ScienceDirect subscribers only

Related works:
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:eee:jetheo:v:165:y:2016:i:c:p:209-241

DOI: 10.1016/j.jet.2016.04.006

Access Statistics for this article

Journal of Economic Theory is currently edited by A. Lizzeri and K. Shell

More articles in Journal of Economic Theory from Elsevier
Bibliographic data for series maintained by Catherine Liu ().