On Likely Solutions of a Stable Marriage Problem
Pittel, Boris
Ann. Appl. Probab., Tome 2 (1992) no. 4, p. 358-401 / Harvested from Project Euclid
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 \rightarrow \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^2 n$, 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 $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.
Publié le : 1992-05-14
Classification:  Stable matching,  random preferences,  ranks,  asymptotic behavior,  limit theorems,  60C05,  60F99,  05A05,  05C70,  41A60,  41A63
@article{1177005708,
     author = {Pittel, Boris},
     title = {On Likely Solutions of a Stable Marriage Problem},
     journal = {Ann. Appl. Probab.},
     volume = {2},
     number = {4},
     year = {1992},
     pages = { 358-401},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1177005708}
}
Pittel, Boris. On Likely Solutions of a Stable Marriage Problem. Ann. Appl. Probab., Tome 2 (1992) no. 4, pp.  358-401. http://gdmltest.u-ga.fr/item/1177005708/