Abstract
The many-to-one matching problem is commonly referred as the hospitals/residents problem which assigns each resident a hospital in an efficient and fair way. This paper considers a multi-period hospitals/residents problem that consists of assigning positions to overlapping generations of residents. From one period to another, residents can either retain their current positions or can choose a more preferred one. In this situation, a fairness criterion is introduced with the condition of the individual rationality for the matching. Moreover, it has been proven that the matching satisfying such criterion always exists and can be obtained by iteratively eliminating Pareto improvement cycles and unjustified claim cycles from any acceptable matching. This paper presents a novel algorithm to compute a matching with minimal unjustified claims under the premise of satisfying the individual rationality and the Pareto efficiency. The complexity of the proposed algorithm is bounded by \(O(Q^{3}n^{3})\) in each period, where n and Q are the number of the residents and the total number of positions of the hospitals in the corresponding period, respectively.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Abdulkadiroğlu A, Parag A, Pathak, Roth AE (2005) The New York City high school match. Am Econ Rev 95(2):364–367
Abdulkadiroğlu A, Angrist J, Pathak P (2014) The Elite illusion: achievement effects at Boston and New York exam schools. Econometrica 82(1):137–196
Abdulkadiroğlu A, Sönmez T (2003) School choice: a mechanism design approach. Am Econ Rev 93(3):729–747
Abdulkadiroğlu A, Che YK, Yasuda Y (2015) Expanding “choice” in school choice. Am Econ J Microecon 7(1):1–42
Bloch F, Cantala D (2013) Markovian assignment rules. Soc Choice Welf 40(1):1–25
Erdil A, Ergin H (2008) What’s the matter with tie-breaking? Improving efficiency in school choice. Am Econ Rev 98(3):669–689
Gale D, Shapley L (1962) College admissions and the stability of marriage. Am Math Mon 69(1):9–15
Gusfield D, Irving RW (1989) The stable marriage problem: structure and algorithms. MIT Press, Cambridge
Kurino M (2009) Credibility, efficiency and stability: a theory of dynamic matching markets. Working paper, Pittsburgh Unviersity
Kennes J, Monte D, Tumennasan N (2014) The daycare assignment: a dynamic matching problem. Am Econ J 6(4):362–406
Pereyra JS (2013) A dynamic school choice model. Games Econ Behav 80(6):100–114
Roth AE (1991) A natural experiment in the organization of entry level labor markets: regional markets for new physicians and surgeons in the United Kingdom. Am Econ Rev 81:415–440
Roth AE (1996) The national residency matching program as a labor market. J Am Med Assoc 275(13):1054–1056
Roth AE, Peranson E (1999) The redesign of the matching market for American Physicians: some engineering aspects of economic design. Am Econ Rev 89(4):748–780
Shapley L, Scarf H (1974) On cores and indivisibility. J Math Econ 1(1):23–37
Acknowledgments
This work was supported by the National Natural Science Foundation of China (Grant No. 71071063, 61273206).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Xiong, X., Zhao, Y. & Chen, Y. A computational approach to the multi-period many-to-one matching with ties. J Comb Optim 33, 183–201 (2017). https://doi.org/10.1007/s10878-015-9944-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-015-9944-0