Course Match : A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation

Combinatorial allocation involves assigning bundles of items to agents when the use of money is not allowed. Course allocation is one common application of combinatorial allocation, in which the bundles are schedules of courses and the assignees are students. Existing mechanisms used in practice have been shown to have serious flaws, which lead to allocations that are inefficient, unfair, or both. A new mechanism proposed by Budish [2011] is attractive in theory, but has several features that limit its feasibility for practice: reporting complexity, computational complexity, and approximations that can lead to violations of capacity constraints. This paper reports on the design and implementation of a new course allocation mechanism, Course Match, that enhances the Budish [2011] mechanism in various ways to make it suitable for practice. To find allocations, Course Match performs a massive parallel heuristic search that solves billions of Mixed-Integer Programs to output an approximate competitive equilibrium in a fake-money economy for courses. Quantitative summary statistics for two semesters of full-scale use at a large business school (Wharton, which has about 1,700 students and up to 350 courses in each semester) demonstrate that Course Match is both fair and efficient, a finding reinforced by student surveys showing large gains in satisfaction and perceived fairness