On likely solutions of a stable marriage problem. (English) Zbl 0753.60016

Pittel, Boris

Ann. Appl. Probab. 2, No. 2, 358-401 (1992).

Summary: 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/\log n)^{1/2}\) with high probability (whp) as \(n\to\infty\) and also that the total number of stable marriage partners of each woman (man) is asymptotically normal with mean and variance close to \(\log n\). It is proved that in the male (female) optimal stable marriage the largest rank of a wife (husband) is whp of order \(\log^ 2n\), while the largest rank of a husband (wife) is asymptotic to \(n\). Earlier [SIAM J. Discrete Math. 2, No. 4, 530-549 (1989; Zbl 0729.05004)], we proved that for either of these extreme matchings the total rank is whp close to \(n^ 2/\log n\). Now, we are able to establish a whp existence of an egalitarian marriage for which the total rank is close to \(2n^{3/2}\) and the largest rank of a partner is of order \(n^{1/2}\log n\). 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 \(n^ 3\), 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.

MSC:

60C05	Combinatorial probability
05A05	Permutations, words, matrices
05C70	Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
41A60	Asymptotic approximations, asymptotic expansions (steepest descent, etc.)
41A63	Multidimensional problems
60F99	Limit theorems in probability theory

Keywords:

random preferences; ranks; limit theorems; stable marriage problem; stable matchings; extreme matchings; combinatorial algorithms

Citations:

Zbl 0729.05004