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

Boris Pittel ()
Additional contact information
Boris Pittel: Department of Mathematics, The Ohio State University, Columbus, Ohio 43210

Mathematics of Operations Research, 2019, vol. 44, issue 1, 122-146

Abstract: 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 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 ≫ n .

Keywords: stable matching; random preferences; asymptotics (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
https://doi.org/10.1287/moor.2017.0917 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormoor:v:44:y:2019:i:1:p:122-146

Access Statistics for this article

More articles in Mathematics of Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().