Parametrizing the Distribution of the Number of Stable Matchings

Abstract

We study the expected number and upper bound of stable matchings. Given n men and n women, each participant has a preference ranking over members of the opposite side, and a matching pairs each man with exactly one woman. A matching is stable if no unmatched man-woman pair mutually prefer each other over their assigned partners. Previous work has shown that, under independently and uniformly random preference lists, the expected number of stable matchings is asymptotic to e^-1 n ln n, even though the maximum possible number of stable matchings grows exponentially with n. However, little is known about accurate finite-size estimates when n is small or moderate. We use exhaustive enumeration and Monte Carlo simulation to estimate the lower-order terms in the expansion e^-1 n ln n + c n + d ln n. Using least-squares regression, we obtain the empirical estimates c ≈ -1.30 and d ≈ 3.33. We also study the probability a random instance has a unique stable matching. Monte Carlo simulations suggest this probability is well approximated by a logarithmic function, with coefficient of determination R² = 0.997. Finally, we investigate a structured preference model in which the positions of women in the men's preference lists satisfy a laminar interval structure. In this setting, any two intervals are either disjoint or one is contained in the other. Our goal is to determine how this structural restriction affects both the expected and worst-case number of stable matchings. This part of the work is still ongoing.