Document Open Access Logo

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

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2020.21.pdf
  • Filesize: 0.49 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • stable matching
  • mechanism design
  • NP-Hardness

Metrics

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.

Cite As Get BibTex

Karthik Gajulapalli, James A. Liu, Tung Mai, and Vijay V. Vazirani. Stability-Preserving, Time-Efficient Mechanisms for School Choice in Two Rounds. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.21

Author Details

Karthik Gajulapalli
  • Department of Computer Science, University of California Irvine, CA, US
James A. Liu
  • K-Sky Limited, Hong Kong, Hong Kong
Tung Mai
  • Adobe Research, San Jose, CA, US
Vijay V. Vazirani
  • Department of Computer Science, University of California Irvine, CA, US

References

  1. Atila Abdulkadiroglu, Yeon-Koo Che, Parag A Pathak, Alvin E Roth, and Olivier Tercieux. Minimizing justified envy in school choice: The design of new orleans' oneapp. Technical report, National Bureau of Economic Research, 2017. Google Scholar
  2. Atila Abdulkadiroğlu, Parag A Pathak, and Alvin E Roth. Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match. American Economic Review, 99(5):1954-78, 2009. Google Scholar
  3. Atila Abdulkadiroğlu and Tayfun Sonmez. School choice: A mechanism design approach. American economic review, 93(3):729-747, 2003. Google Scholar
  4. Atila Abdulkadiroglu and Tayfun Sonmez. Matching markets: Theory and practice. Advances in Economics and Econometrics, 1:3-47, 2013. Google Scholar
  5. Tommy Andersson, Umut Dur, Sinan Ertemel, Onur Kesten, et al. Sequential school choice with public and private schools. Technical report, Lund University, 2018. Google Scholar
  6. Battal Dogan and M Bumin Yenmez. When does an additional stage improve welfare in centralized assignment?, 2018. Google Scholar
  7. Laura Doval. A theory of stability in dynamic matching markets. Technical report, Technical report, mimeo, 2018. Google Scholar
  8. Lester E Dubins and David A Freedman. Machiavelli and the gale-shapley algorithm. The American Mathematical Monthly, 88(7):485-494, 1981. Google Scholar
  9. Lester E Dubins and David A Freedman. Machiavelli and the Gale-Shapley algorithm. The American Mathematical Monthly, 88(7):485-494, 1981. Google Scholar
  10. Umut Dur and Onur Kesten. Sequential versus simultaneous assignment systems and two applications. Economic Theory, pages 1-33, 2014. Google Scholar
  11. Federico Echenique and Juan Sebastián Pereyra. Strategic complementarities and unraveling in matching markets. Theoretical Economics, 11(1):1-39, 2016. Google Scholar
  12. Itai Feigenbaum, Yash Kanoria, Irene Lo, and Jay Sethuraman. Dynamic matching in school choice: Efficient seat reallocation after late cancellations, 2018. Google Scholar
  13. Simons Institute for the Theory of Computing. Online and matching-based market design, 2019. URL: https://simons.berkeley.edu/programs/market2019.
  14. David Gale and Lloyd S Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9-15, 1962. Google Scholar
  15. Joseph Gasper, Stefanie DeLuca, and Angela Estacion. Switching schools: Revisiting the relationship between school mobility and high school dropout. American Educational Research Journal, 49(3):487-519, 2012. Google Scholar
  16. Dan Gusfield and Robert W Irving. The stable marriage problem: structure and algorithms. MIT press, 1989. Google Scholar
  17. Sangram V Kadam and Maciej H Kotowski. Multiperiod matching. International Economic Review, 59(4):1927-1947, 2018. Google Scholar
  18. Parag A Pathak. The mechanism design approach to student assignment. Annu. Rev. Econ., 3(1):513-536, 2011. Google Scholar
  19. Alvin E. Roth. Stability and polarization of interests in job matching. Econometrica: Journal of the Econometric Society, pages 47-57, 1984. Google Scholar
  20. Alvin E Roth. On the allocation of residents to rural hospitals: a general property of two-sided matching markets. Econometrica: Journal of the Econometric Society, pages 425-427, 1986. Google Scholar
  21. Alvin E Roth. What have we learned from market design? Innovations: Technology, Governance, Globalization, 3(1):119-147, 2008. Google Scholar
  22. Alvin E. Roth. Al Roth’s game theory, experimental economics, and market design page, 2016. URL: http://stanford.edu/~alroth/alroth.html#MarketDesign.
  23. Alvin E. Roth and LLoyd S. Shapley. Nobel Memorial Prize in Economics, 2012. URL: https://www.nobelprize.org/prizes/economic-sciences/2012/summary/.
  24. Alexander Westkamp. An analysis of the german university admissions system. Economic Theory, 53(3):561-589, 2013. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact