文章基本信息

标题：Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds
本地全文：下载
作者：Karthik Gajulapalli ; James A. Liu ; Tung Mai 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-15
DOI：10.4230/LIPIcs.FSTTCS.2020.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：stable matching; mechanism design; NP-Hardness