Abstract
Stable matching in a community consisting of men and women is a classical combinatorial problem that has been the subject of intense theoretical and empirical study since its introduction in 1962 in a seminal paper by Gale and Shapley, who designed the celebrated “deferred acceptance” algorithm for the problem.
In the input, each participant ranks participants of the opposite type, so the input consists of a collection of permutations, representing the preference lists. A bipartite matching is unstable if some man-woman pair is blocking: both strictly prefer each other to their partner in the matching. Stability is an important economics concept in matching markets from the viewpoint of manipulability. The unicity of a stable matching implies non-manipulability, and near-unicity implies limited manipulability, thus these are mathematical properties related to the quality of stable matching algorithms.
This paper is a theoretical study of the effect of correlations on approximate manipulability of stable matching algorithms. Our approach is to go beyond worst case, assuming that some of the input preference lists are drawn from a distribution. Approximate manipulability is approached from several angles: when all stable partners of a person have approximately the same rank; or when most persons have a unique stable partner.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abdulkadiroğlu, A., Pathak, P.A., Roth, A.E.: The New York city high school match. Am. Econ. Rev. 95(2), 364–367 (2005)
Abdulkadiroğlu, A., Pathak, P.A., Roth, A.E., Sönmez, T.: The Boston Public School match. Am. Econ. Rev. 95(2), 368–371 (2005)
Ashlagi, I., Braverman, M., Thomas, C., Zhao, G.: Tiered random matching markets: rank is proportional to popularity. In: 12th Innovations in Theoretical Computer Science Conference (ITCS). Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2021)
Ashlagi, I., Kanoria, Y., Leshno, J.D.: Unbalanced random matching markets: the stark effect of competition. J. Polit. Econ. 125(1), 69–98 (2017)
Azevedo, E.M., Leshno, J.D.: A supply and demand framework for two-sided matching markets. J. Polit. Econ. 124(5), 1235–1268 (2016)
Banerjee, A., Duflo, E., Ghatak, M., Lafortune, J.: Marry for what? Caste and mate selection in modern India. Am. Econ. J. Microecon. 5(2), 33–72 (2013)
Biró, P., Hassidim, A., Romm, A., Shorrer, R.I., Sóvágó, S.: Need versus merit: the large core of college admissions markets. arXiv preprint arXiv:2010.08631 (2020)
Correa, J., et al.: School choice in Chile. In: Proceedings of the 2019 ACM Conference on Economics and Computation, pp. 325–343 (2019)
Demange, G., Gale, D., Sotomayor, M.: A further note on the stable matching problem. Discret. Appl. Math. 16(3), 217–222 (1987)
Dubins, L.E., Freedman, D.A.: Machiavelli and the Gale-Shapley algorithm. Am. Math. Mon. 88(7), 485–494 (1981)
Gale, D., Shapley, L.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9–15 (1962)
Gale, D., Sotomayor, M.: Some remarks on the stable matching problem. Discret. Appl. Math. 11(3), 223–232 (1985)
Gimbert, H., Mathieu, C., Mauras, S.: Two-sided matching markets with strongly correlated preferences. arXiv preprint arXiv:1904.03890 (2019)
Gusfield, D.: Three fast algorithms for four problems in stable marriage. SIAM J. Comput. 16(1), 111–128 (1987)
Gusfield, D., Irving, R.W.: The Stable Marriage Problem: Structure and Algorithms. MIT Press, Cambridge (1989)
Hitsch, G.J., Hortaçsu, A., Ariely, D.: Matching and sorting in online dating. Am. Econ. Rev. 100(1), 130–63 (2010)
Immorlica, N., Mahdian, M.: Incentives in large random two-sided markets. ACM Trans. Econ. Comput. 3(3), 14 (2015)
Kanoria, Y., Min, S., Qian, P.: In which matching markets does the short side enjoy an advantage? In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1374–1386. SIAM (2021)
Knuth, D.E., Motwani, R., Pittel, B.: Stable husbands. In: Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 397–404 (1990)
Kojima, F., Pathak, P.A.: Incentives and stability in large two-sided matching markets. Am. Econ. Rev. 99(3), 608–27 (2009)
Lee, S.: Incentive compatibility of large centralized matching markets. Rev. Econ. Stud. 84(1), 444–463 (2016)
Lennon, C., Pittel, B.: On the likely number of solutions for the stable marriage problem. Comb. Probab. Comput. 18(3), 371–421 (2009)
Pathak, P.A., Sönmez, T.: Leveling the playing field: sincere and sophisticated players in the Boston mechanism. Am. Econ. Rev. 98(4), 1636–52 (2008)
Pittel, B.: The average number of stable matchings. SIAM J. Discret. Math. 2(4), 530–549 (1989)
Pittel, B.: On likely solutions of a stable marriage problem. Ann. Appl. Probab. 2, 358–401 (1992)
Pittel, B., Shepp, L., Veklerov, E.: On the number of fixed pairs in a random instance of the stable marriage problem. SIAM J. Discret. Math. 21(4), 947–958 (2007)
Rheingans-Yoo, R., Street, J.: Large random matching markets with localized preference structures can exhibit large cores. Technical report, Mimeo (2020)
Roth, A.E.: The economics of matching: stability and incentives. Math. Oper. Res. 7(4), 617–628 (1982)
Roth, A.E., Peranson, E.: The redesign of the matching market for American physicians: some engineering aspects of economic design. Am. Econ. Rev. 89(4), 748–780 (1999)
Acknowledgements
This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Gimbert, H., Mathieu, C., Mauras, S. (2021). Two-Sided Matching Markets with Strongly Correlated Preferences. In: Bampis, E., Pagourtzis, A. (eds) Fundamentals of Computation Theory. FCT 2021. Lecture Notes in Computer Science(), vol 12867. Springer, Cham. https://doi.org/10.1007/978-3-030-86593-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-86593-1_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-86592-4
Online ISBN: 978-3-030-86593-1
eBook Packages: Computer ScienceComputer Science (R0)