Designing Random Allocation Mechanisms: Theory and Applications

Coauthors: Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom
American Economic Review, (2013): 103, no. 2, 585-623. [PDF]
Randomization is commonplace in everyday resource allocation. We generalize the theory of randomized assignment to accommodate multi-unit allocations and various real-world constraints, such as group-specific quotas (“controlled choice”) in school choice and house allocation, and scheduling and curriculum constraints in course allocation. We develop new mechanisms that are ex ante efficient and fair in these environments, and that incorporate certain non-additive substitutable preferences. We also develop a “utility guarantee” technique that limits ex post unfairness in random allocations, supplementing the ex ante fairness promoted by randomization. This can be applied to multi-unit assignment problems and certain two-sided matching problems.

Appendix

Online Appendices with Yeon-Koo Che, Fuhito Kojima, and Paul Milgrom. American Economic Review 103, no. 2 (2013): 585-623.. [PDF]

Designing Random Allocation Mechanisms Seminar Slides (Oct 2010)

[PDF]