Matching with Bundle Preferences: Tradeoff between Fairness and Truthfulness

Matching with Bundle Preferences: Tradeoff between Fairness and Truthfulness

Course assignment is a widespread problem in education. Often students have preferences for course schedules over the week. First-Come First-Served (FCFS) is the most widely used rule to assign students to courses in practice, but recent research led to alternatives with attractive properties. Bundled Probabilistic Serial (BPS) is a randomized mechanism satisfying ordinal efficiency, envy-freeness, weak strategy-proofness, and polynomial runtime. We report a first application of BPS in a large-scale course assignment application and discuss advantages over FCFS comparing a number of metrics such as the size, the average rank, the profile, and the popularity of the assignments. The exponential number of possible course schedules is a central problem in the implementation of combinatorial assignment mechanisms. We propose a new way to elicit preferences, which limits the number of parameters a student needs to provide. This yields a computationally very effective tool to solve course assignment problems with thousands of students in practice.