In many centralized school admission systems, a significant fraction of allocated seats are later vacated, often due to students obtaining better outside options. We consider the problem of reassigning these seats in a fair and efficient manner while also minimizing the movement of students between schools. Centralized admissions are typically conducted using the Deferred Acceptance (DA) algorithm, with a lottery used to break ties caused by indifferences in school priorities. We introduce the Permuted Lottery Deferred Acceptance (PLDA) mechanisms, which reassign vacated seats using a second round of Deferred Acceptance with a lottery given by a suitable permutation of the first round lottery numbers. We show that a mechanism based on a simple reversal of the first round lottery order performs the best among all PLDA mechanisms. We also characterize PLDA mechanisms as the class of truthful mechanisms satisfying some natural efficiency and fairness properties. Empirical investigations based on data from NYC high school admissions support our theoretical findings.
Feigenbaum, Itai, Yash Kanoria, Irene Lo, and Jay Sethuraman. "Dynamic Matching in School Choice: Efficient Seat Reallocation After Late Cancellations." Columbia Business School, February 2017.
Each author name for a Columbia Business School faculty member is linked to a faculty research page, which lists additional publications by that faculty member.
Each topic is linked to an index of publications on that topic.