Assignment problems with complementarities

• 成果类型: Article
• 署名作者: Thanh Nguyen; Peivandi, Ahmad; Vohra, Rakesh
• 署名单位: Purdue University System; Purdue University; University System of Georgia; Georgia State University; University of Pennsylvania
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2016.04.006
• 发表日期: 2016
• 页码: 209-241
• 关键词: One sided matching; complementarities; strategy-proof; efficient; Envy-free; mechanism

摘要

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. Published by Elsevier Inc.