Stable husbands
Loading...
Date
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
Suppose $n$ boys and $n$ girls rank each other at random. We show that any particular girl has at least $({1\over 2}-ε) \ln n$ and at most $(1+ε)\ln n$ different husbands in the set of all Gale/Shapley stable matchings defined by these rankings, with probability approaching 1 as $n \to \infty$, if $ε$ is any positive constant. The proof emphasizes general methods that appear to be useful for the analysis of many other combinatorial algorithms.