×

Paths to stability and uniqueness in two-sided matching markets. (English) Zbl 1418.91394

Summary: The deferred acceptance algorithm introduced by D. Gale and L. S. Shapley [Am. Math. Mon. 69, 9–15 (1962; Zbl 0109.24403)] is a centralized algorithm, where a social planner solicits the preferences from two sides of a market and generates a stable matching. On the other hand, the algorithm proposed by D. E. Knuth [Stable marriage and its relation to other combinatorial problems. An introduction to the mathematical analysis of algorithms. Providence, RI: AMS, American Mathematical Society (1996; Zbl 0860.68054)] is a decentralized algorithm. In this article, we discuss conditions leading to the convergence of Knuth’s decentralized algorithm. In particular, we show that Knuth’s decentralized algorithm converges to a stable matching if either the sequential preference condition (SPC) holds or if the market admits no cycle. In fact, acyclicity turns out to be a special case of SPC. We then consider markets where agents may prefer to remain single rather than being matched with someone. We introduce a generalized version of SPC for such markets. Under this notion of generalized SPC, we show that the market admits a unique stable matching, and that Knuth’s decentralized algorithm converges. The generalized SPC seems to be the most general condition available in the literature for uniqueness in two-sided matching markets.

MSC:

91B68 Matching models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alcalde, J., Exchange-proofness or divorce-proofness? Stability in one-sided matching markets, Econ Des, 1, 275-287, (1994) · doi:10.1007/BF02716626
[2] Banerjee, S.; Konishi, H.; Sönmez, T., Core in a simple coalition formation game, Soc Choice Welf, 18, 135-153, (2001) · Zbl 1069.91504 · doi:10.1007/s003550000067
[3] Becker, Gary S., A Theory of Marriage: Part II, Journal of Political Economy, 82, s11-s26, (1974) · doi:10.1086/260287
[4] Clark S (2006) The uniqueness of stable matchings. Contrib Theor Econ 6:Art. 8. https://doi.org/10.2202/1534-5971.1283(electronic) · doi:10.2202/1534-5971.1283
[5] Drgas-Burchardt, E., A note on the uniqueness of stable marriage matching, Discussiones Mathematicae Graph Theory, 33, 49-55, (2013) · Zbl 1293.05289 · doi:10.7151/dmgt.1667
[6] Dubins, LE; Freedman, DA, Machiavelli and the Gale-Shapley algorithm, Am Math Mon, 88, 485-494, (1981) · Zbl 0449.92024 · doi:10.2307/2321753
[7] Eeckhout, Jan, On the uniqueness of stable marriage matchings, Economics Letters, 69, 1-8, (2000) · Zbl 0960.91052 · doi:10.1016/S0165-1765(00)00263-9
[8] Ehlers, Lars; Massó, Jordi, Incomplete information and singleton cores in matching markets, Journal of Economic Theory, 136, 587-600, (2007) · Zbl 1281.91123 · doi:10.1016/j.jet.2006.10.007
[9] Eriksson, K.; Häggström, O., Instability of matchings in decentralized markets with various preference structures, Int J Game Theory, 36, 409-420, (2008) · Zbl 1139.91025 · doi:10.1007/s00182-007-0081-6
[10] Gale, D.; Shapley, LS, College admissions and the stability of marriage, Am Math Mon, 69, 9-15, (1962) · Zbl 0109.24403 · doi:10.2307/2312726
[11] Gusfield DM, Irving RW (2003) The stable marriage problem: structure and algorithms. MIT Press, Cambridge
[12] Klaus, B.; Klijn, F., Corrigendum to “On randomized matching mechanisms” [Economic Theory 8(1996) 377-381], Econ Theory, 32, 411-416, (2007) · Zbl 1159.91438 · doi:10.1007/s00199-006-0117-3
[13] Knuth DE (1976) Mariages stables et leurs relations avec d’autres problèmes combinatoires. Les Presses de l’Université de Montréal, Montreal, Que., introduction à l’analyse mathématique des algorithmes, Collection de la Chaire Aisenstadt
[14] Knuth DE (1997) Stable marriage and its relation to other combinatorial problems: an introduction to the mathematical analysis of algorithms. AMS, Providence
[15] Lauermann, Stephan; Nöldeke, Georg, Stable marriages and search frictions, Journal of Economic Theory, 151, 163-195, (2014) · Zbl 1296.91209 · doi:10.1016/j.jet.2013.11.001
[16] Ma, J., On randomized matching mechanisms, Econ Theory, 8, 377-381, (1996) · Zbl 0859.90009 · doi:10.1007/BF01211824
[17] Park, J., Competitive equilibrium and singleton cores in generalized matching problems, Int J Game Theory, 46, 487-509, (2017) · Zbl 1398.91459 · doi:10.1007/s00182-016-0543-9
[18] Romero-Medina, Antonio; Triossi, Matteo, Acyclicity and singleton cores in matching markets, Economics Letters, 118, 237-239, (2013) · Zbl 1284.91418 · doi:10.1016/j.econlet.2012.10.032
[19] Romero-Medina, A.; Triossi, M., Games with capacity manipulation: incentives and Nash equilibria, Soc Choice Welf, 41, 701-720, (2013) · Zbl 1288.91154 · doi:10.1007/s00355-012-0703-1
[20] Roth, AE, The economics of matching: stability and incentives, Math Oper Res, 7, 617-628, (1982) · Zbl 0496.90008 · doi:10.1287/moor.7.4.617
[21] Roth AE, Sotomayor M (1992) Two-sided matching: a study in game-theoretic modeling and analysis. Cambridge University Press, Cambridge
[22] Roth, AE; Vande Vate, JH, Random paths to stability in two-sided matching, Econometrica, 58, 1475-1480, (1990) · Zbl 0731.90007 · doi:10.2307/2938326
[23] Tamura, Akihisa, Transformation from arbitrary matchings to stable matchings, Journal of Combinatorial Theory, Series A, 62, 310-323, (1993) · Zbl 0771.05096 · doi:10.1016/0097-3165(93)90051-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.