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 indifference in school priorities. For reassignment, we propose a class of mechanisms called Permuted Lottery Deferred Acceptance (PLDA). After the initial (first-round) assignment is computed via DA, students' preferences change (get truncated) due to the revelation of their outside options. A PLDA mechanism then computes a reassignment of the students by re-running DA; however, students are guaranteed to get at least their first-round assignment (if they still want it) or a school they prefer, and ties are broken according to a permutation of the first-round lottery order. We show that a PLDA based on a reversal of the first-round lottery order performs well. Our theoretical analysis takes place in a continuum model with no school priorities. We characterize PLDA mechanisms as the class of mechanisms that satisfy a few natural properties, which include not removing students from their first-round assignments against their will, a strong form of strategyproofness (against manipulations involving misreporting both the original and changed preferences), and certain efficiency and fairness axioms. We then identify a technical condition, called the order condition, essentially requiring that the change in preferences does not modify the relative overdemand for schools. When the order condition is satisfied, all PLDA mechanisms yield identical allocative efficiency, and among all of them, the lottery-reversal based PLDA reassigns the minimal amount of students (from their first-round assignments). Finally, we conduct computational experiments and obtain results that support our theoretical findings. Specifically, we use data from NYC's school choice program to simulate the performance of different PLDA mechanisms in the presence of school priorities, and find that all simulated PLDAs have similar allocative efficiency, while the lottery-reversal based PLDA minimizes the number of reassigned students.
展开▼
