2026-07-22T20:50:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13262 2024-03-06T10:51:58Z ddc:004 open_access

Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds Gajulapalli, Karthik Liu, James A. Mai, Tung Vazirani, Vijay V. stable matching mechanism design NP-Hardness 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Karthik Gajulapalli and James A. Liu and Tung Mai and Vijay V. Vazirani 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.21 urn:nbn:de:0030-drops-132626 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.21 eng https://creativecommons.org/licenses/by/3.0/legalcode