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

• 成果类型: Article
• 署名作者: Budish, Eric; Cachon, Gerard P.; Kessler, Judd B.; Othman, Abraham
• 署名单位: University of Chicago; University of Chicago; University of Pennsylvania; University of Pennsylvania; University of Pennsylvania; University of Pennsylvania
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2016.1544
• 发表日期: 2017
• 页码: 314-336
• 关键词: business schools; kidney exchange; complexity; DESIGN; MARKET

摘要

Combinatorial allocation involves assigning bundles of items to agents when the 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 recently developed mechanism is attractive in theory but has several features that limit its feasibility for practice. This paper reports on the design and implementation of a new course allocation mechanism, Course Match, that is suitable in 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 (the Wharton School of Business, 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.