Abstract
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.