Bureaucrats, editor, Administrators
373
edits
Changes
→Abstract
The problem of allocating bundles of indivisible objects without transfers arises in the assignment of courses to students, the assignment of computing resources like CPU time, memory and disk space to computing tasks and the assignment of truck loads 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 efficiency, envyfreeness and asymptotic strategy-proofness.
The problem of allocating bundles of indivisible objects without transfers arises in the assignment of courses to students, the assignment of computing resources like CPU time, memory and disk space to computing tasks and the assignment of truck loads 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 efficiency, envyfreeness and asymptotic strategy-proofness.
Informally, we assume that agents do not want bundles that are to large. There will be a parameter k such that the marginal utility of any item relative to a bundle of size k or larger is zero. We call such preferences k-demand preferences. Given this parameter we show how to represent probability shares over bundles as lotteries over approximately deterministic feasible integer allocations. The degree of infeasibility in these integer allocations will be controlled by the parameter k. In particular, ex-post, no good is over allocated by at most k-1 units.
Informally, we assume that agents do not want bundles that are too large. There will be a parameter k such that the marginal utility of any item relative to a bundle of size k or larger is zero. We call such preferences k-demand preferences. Given this parameter we show how to represent probability shares over bundles as lotteries over approximately deterministic feasible integer allocations. The degree of infeasibility in these integer allocations will be controlled by the parameter k. In particular, ex-post, no good is over allocated by at most k-1 units.
Based on joint work with Thanh Nguyen and Ahmad Peivandi.
Based on joint work with Thanh Nguyen and Ahmad Peivandi.