On Likely Solutions of the Stable Matching Problem with Unequal Numbers of Men and Women

• 成果类型: Article
• 署名作者: Pittel, Boris
• 署名单位: University System of Ohio; Ohio State University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2017.0917
• 发表日期: 2019
• 页码: 122-146

摘要

Following up a recent work by Ashlagi, Kanoria, and Leshno, we study a stable matching problem with unequal side sizes, n men and N > n women, whose preferences for a partner are uniformly random and independent. An asymptotic formula for the expected number of stable matchings is obtained. In particular, for N = n +1 this number is close to n/(e log n), in notable contrast with (n log n)/e, the formula for the balanced case N = n that we obtained in 1988. We associate with each stable matching m the parameters W(M) and H(M), which are the total rank of wives and the total rank of husbands, as ranked by their spouses in M. We found the deterministic parameters w(n, N) and h(n, N) such that the set of scaled pairs (W(M)/w(n, N),H(M)/h(n, N)) converges to a single point. In particular, w(n, n +1) similar to n log n, h(n, n +1) similar to n(2)/log n. To compare, for the balanced case n = N we previously found that w(n, n) = h(n, n) = n(3/2), and that the pairs of scaled total ranks converged to a hyperbolic arc xy = 1, connecting the rank pairs of two extreme stable matchings, men-optimal and women-optimal. We also show that the expected fraction of persons with more than one stable spouse is vanishingly small if N - n >>root n.