Dynamic Matching in School Choice: Efficient Seat Reassignment After Late Cancellations
研究了择校市场中初始分配后空出座位的重新分配问题，提出并验证了PLDA机制，该机制在保持激励相容和效率的同时最小化学生流动，基于纽约市高中录取数据支持了理论发现。
In the school choice market, where scarce public school seats are assigned to students, a key operational issue is how to reassign seats that are vacated after an initial round of centralized assignment. Practical solutions to the reassignment problem must be simple to implement, truthful, and efficient while also alleviating costly student movement between schools. We propose and axiomatically justify a class of reassignment mechanisms, the permuted lottery deferred acceptance (PLDA) mechanisms. Our mechanisms generalize the commonly used deferred acceptance (DA) school choice mechanism to a two-round setting and retain its desirable incentive and efficiency properties. School choice systems typically run DA with a lottery number assigned to each student to break ties in school priorities. We show that under natural conditions on demand, the second-round tie-breaking lottery can be correlated arbitrarily with that of the first round without affecting allocative welfare and that reversing the lottery order between rounds minimizes reassignment among all PLDA mechanisms. Empirical investigations based on data from New York City high school admissions support our theoretical findings. This paper was accepted by Gad Allon, operations management.