Monday, August 3, 2015

Course allocation at Wharton: looking under the hood

A new paper by Budish, Cachon, Kessler and Othman gives more detail on how the course allocation tool at Wharton works at a computational level. It's a great example of practical market design as economic engineering.

Course Match: A Large-Scale Implementationof Approximate Competitive Equilibrium from Equal Incomesfor Combinatorial Allocation
Eric Budish, Gerard P. Cachon, Judd Kessler, and Abraham Othman¶
July 23, 2015

Abstract:  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
*****************

In the conclusion, they write

"A critical feature for the success of Course Match is its “strategy-proof” property — a student’s best strategy is to report her true preferences no matter what preferences other students report or what capacities are assigned to each course. This greatly simplifies the student’s reporting task because the student need not form beliefs about how other students will “play” or what clearing prices might be for courses. In contrast, the Wharton Auction (as well as all other course-allocation mechanisms implemented in practice) was not strategy-proof. For example, if a student desires a course but believes that it will have a zero clearing price, then the student should rationally submit a low bid and save tokens to bid on other courses. However, the student may make a mistake and not receive the course she desires if the clearing price turns out to be higher than expected. This bidding mistake is not trivial and it could even lead a student with ample tokens to receive zero courses. Such errors do not happen with Course Match because Course Match effectively bids on behalf of students after all of the clearing prices have been revealed."
...
"while the Course Match mechanism has many desirable theoretical properties, if the preference language given to students is not sufficiently rich (i.e., it does not allow students to express critical preferences) or if students are not able to “speak” this language (i.e., they cannot use the language to correctly report their preferences), then Course Match may not yield desirable results. We are not able to provide direct evidence of the quality of the Course Match preference reporting language and user interface, but the high overall student satisfaction scores provide indirect evidence that the Course Match language is su!ciently rich and easy to use."
...
"We do not claim that the Course Match computational architecture is “optimal.” Indeed, an important question left for future research is whether there are better approaches to finding approximate market-clearing prices than that described here. We do show, however, that the Course Match computational architecture works at Wharton. To borrow a common analogy (e.g., Roth [2002]), ours is an exercise of engineering rather than physics."