Assignment problems with complementarities

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.