摘要：We address the following dynamic version of the school choice question: a city, named City, admits students in two temporally-separated rounds, denoted Râ, and Râ,,. In round Râ,, the capacity of each school is fixed and mechanism Mâ, finds a student optimal stable matching. In round Râ,,, 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 Râ,,, 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 Râ,, under certain settings.
