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
Go to the corresponding LIPIcs Volume Portal

Gajulapalli, Karthik ; Liu, James A. ; Mai, Tung ; Vazirani, Vijay V.

Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds

LIPIcs-FSTTCS-2020-21.pdf (0.5 MB)


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

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI