Pittel, Boris One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences. (English) Zbl 1512.05020 Discrete Appl. Math. 292, 1-18 (2021). Summary: For a two-sided \((n\) men/\(n\) women) stable matching problem) D. Gale and L. S. Shapley [Am. Math. Mon. 69, 9–15 (1962; Zbl 0109.24403)] studied a proposal algorithm (men propose/women select, or the other way around), that determines a matching, not blocked by any unmatched pair. R. W. Irving [J. Algorithms 6, 577–595 (1985; Zbl 0581.05001)] used this algorithm as a first phase of his algorithm for one-sided (stable roommates) matching problem with \(n\) agents. We analyze a fully extended version of Irving’s proposal algorithm that runs all the way until either each agent holds a proposal or an agent gets rejected by everybody on the agent’s preference list. It is shown that the terminal, directed, partnerships form a permutation satisfying a certain stability condition, similar to, but different from the one introduced by J. J. M. Tan [ibid. 12, No. 1, 154–178 (1991; Zbl 0715.68069)]. A likely behavior of the proposal algorithm is studied under assumption that all \(n\) rankings are independently uniform. It is proved that with high probability (w.h.p.) every agent has a partner, and that both the number of agents in cycles of length \(\geq 3\) and the total number of stable matchings are bounded in probability. W.h.p. the total number of proposals is asymptotic to \(0.5 n^{3/2}\). MSC: 05A05 Permutations, words, matrices 60C05 Combinatorial probability 91B68 Matching models Keywords:stable permutations; random preferences; asymptotics Citations:Zbl 0109.24403; Zbl 0581.05001; Zbl 0715.68069 PDFBibTeX XMLCite \textit{B. Pittel}, Discrete Appl. Math. 292, 1--18 (2021; Zbl 1512.05020) Full Text: DOI arXiv References: [1] Ashlagi, I.; Kanoria, Y.; Leshno, J. D., Unbalanced random matching markets: The stark effect of competition, J. Political Econ., 125, 69-98 (2017) [2] Dubhashi, D.; Ranjan, D., Balls and bins: a study in negative dependence, Random Structures Algorithms, 13, 99-124 (1998) · Zbl 0964.60503 [3] Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 9-15 (1962) · Zbl 0109.24403 [4] Gusfield, D.; Irving, R. W., (The Stable Marriage Problem, Structure and Algorithms. The Stable Marriage Problem, Structure and Algorithms, Foundations of Computing Series (1989)) · Zbl 0703.68046 [5] Irving, R. W., An efficient algorithm for the stable roommates problem, J. Algorithms, 6, 577-595 (1985) · Zbl 0581.05001 [6] Irving, R. W.; Pittel, B., An upper bound for the solvability probability of a random stable roommates instance, Random Structures Algorithms, 5, 465-486 (1994) · Zbl 0805.60010 [7] Karlin, S.; Taylor, H. M., A Second Course in Stochastic Processes (1981), Academic Press: Academic Press Cambridge · Zbl 0469.60001 [8] Knuth, D. E., Mariages Stables et Leurs Relations D’autres Problémes Combinatoires (1976), Les Presses de l’Université de Montréal: Les Presses de l’Université de Montréal Montréal · Zbl 0358.68057 [9] Knuth, D. E., (Stable Marriage and Its Relation to Other Combinatorial Problems: an Introduction to the Mathematical Analysis of Algorithms. Stable Marriage and Its Relation to Other Combinatorial Problems: an Introduction to the Mathematical Analysis of Algorithms, CRM Proceedings and Lecture Notes (1996)) · Zbl 0860.68054 [10] Knuth, D. E.; Motwani, R.; Pittel, B., Stable husbands, Random Structures Algorithms, 1, 1-14 (1990) · Zbl 0719.05001 [11] Lennon, C.; Pittel, B., On the likely number of solutions for the stable matching problem, Combin. Probab. Comput., 18, 371-421 (2009) · Zbl 1200.05174 [12] Manlove, D. F., Algorithmics of matching under preferences, Theoret. Comput. Sci. (2013) · Zbl 1283.68018 [13] McVitie, D. G.; Wilson, L. B., The stable marriage problem, Commun. ACM, 14, 486-490 (1971) [14] Mertens, S., Random stable matchings, J. Stat. Mech. Theory Exp., 10, P10008 (2005) · Zbl 1456.91065 [15] Pittel, B., The average number of stable matchings, SIAM J. Discrete Math., 2, 530-549 (1989) · Zbl 0729.05004 [16] Pittel, B., On likely solutions of a stable marriage problem, Ann. Appl. Probab., 2, 358-401 (1992) · Zbl 0753.60016 [17] Pittel, B., On a random instance of a “stable roommates” problem: likely behavior of the proposal algorithm, Combin. Probab. Comput., 2, 53-92 (1993) · Zbl 0793.60007 [18] Pittel, B., The stable roommates problem with random preferences, Ann. Probab., 21, 1441-1477 (1993) · Zbl 0778.60005 [19] Pittel, B., On likely solutions of the stable matching problem with unequal numbers of men and women, Math. Oper. Res., 44, 122-146 (2019) · Zbl 1435.91128 [20] Pittel, B., On random stable partitions, Internat. J. Game Theory, 48, 433-480 (2019) · Zbl 1417.91385 [21] Tan, J. J.M., A necessary and sufficient condition for the existence of a complete stable matching, J. Algorithms, 12, 154-178 (1991) · Zbl 0715.68069 [22] Tan, J. J.M., Stable matchings and stable partitions, Int. J. Comput. Math., 39, 11-20 (1991) · Zbl 0742.68047 [23] Tan, J. J.M.; Hsueh, Y.-C., A generalization of the stable matching problem, Discrete Appl. Math., 59, 87-102 (1995) · Zbl 0827.90120 [24] Wilson, L. B., An analysis of the stable marriage assignment problem, BIT, 12, 569-575 (1972) · Zbl 0249.05006 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.