License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.21
URN: urn:nbn:de:0030-drops-132626
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13262/
Gajulapalli, Karthik ;
Liu, James A. ;
Mai, Tung ;
Vazirani, Vijay V.
Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds
Abstract
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.
BibTeX - Entry
@InProceedings{gajulapalli_et_al:LIPIcs:2020:13262,
author = {Karthik Gajulapalli and James A. Liu and Tung Mai and Vijay V. Vazirani},
title = {{Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {21:1--21:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13262},
URN = {urn:nbn:de:0030-drops-132626},
doi = {10.4230/LIPIcs.FSTTCS.2020.21},
annote = {Keywords: stable matching, mechanism design, NP-Hardness}
}
|
Keywords: |
|
stable matching, mechanism design, NP-Hardness |
|
Collection: |
|
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
