Abstract

We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted $\cR_1$ and $\cR_2$. In round $\cR_1$, the capacity of each school is fixed and mechanism $\cM_1$ finds a student optimal stable matching. In round $\cR_2$, certain parameters change, e.g., new students move into the City or the City is happy to allocate extra seats to specific schools. We study a number of Settings of this kind and give polynomial time algorithms for obtaining a stable matching for the new situations.

It is well established that switching the school of a student midway, unsynchronized with her classmates, can cause traumatic effects. This fact guides us to two types of results, the first simply disallows any re-allocations in round $\cR_2$, and the second asks for a stable matching that minimizes the number of re-allocations. For the latter, we prove that the stable matchings which minimize the number of re-allocations form a sublattice of the lattice of stable matchings. Observations about incentive compatibility are woven into these results. We also give a third type of results, namely proofs of NP-hardness for a mechanism for round $\cR_2$ under certain settings.

Note:  This is joint work with James Liu, Tung Mai and Vijay Vazirani.