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

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 ℳ the parameters 𝒲(ℳ) and ℋ(ℳ), which are the total rank of “wives” and the total rank of “husbands,” as ranked by their “spouses” in ℳ. We found the deterministic parameters w(n, N) and h(n, N) such that the set of scaled pairs (𝒲(ℳ)/w(n, N), ℋ(ℳ)/h(n, N)) converges to a single point. In particular, w(n, n + 1) ∼ n log n, h(n, n + 1) ∼ n²/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\gg \sqrt{n}$.