On Likely Solutions of a Stable Marriage Problem

An (n men-n women) stable marriage problem is studied under the assumption that the individual preferences for a marriage partner are uniformly random and mutually independent. We show that the total number of stable matchings (marriages) is at least (n/logn)1/2 with high probability (whp) as n.. and also that the total number of stable marriage partners of each woman (man) is asymptotically normal with mean and variance close to logn. It is proved that in the male (female) optimal stable marriage the largest rank of a wife (husband) is whp of order log2n, while the largest rank of a husband (wife) is asymptotic to n. Earlier, we proved that for either of these extreme matchings the total rank is whp close to n2/logn. Now, we are able to establish a whp existence of an egalitarian marriage for which the total rank is close to 2n3/2 and the largest rank of a partner is of order n1/2logn. Quite unexpectedly, the stable matchings obey, statistically, a "law of hyperbola": namely, whp the product of the sum of husbands' ranks and the sum of wives' ranks in a stable matching turns out to be asymptotic to n3, uniformly over all stable marriages. The key elements of the proofs are extensions of the McVitie-Wilson proposal algorithm and of Knuth's integral formula for the probability that a given matching is stable, and also a notion of rotations due to Irving. Methods developed in this paper may, in our opinion, be found useful in probabilistic analysis of other combinatorial algorithms.