All Title Author
Keywords Abstract

Mathematics  1990 

Stable husbands

Full-Text   Cite this paper   Add to My Lib


Suppose $n$ boys and $n$ girls rank each other at random. We show that any particular girl has at least $({1\over 2}-\epsilon) \ln n$ and at most $(1+\epsilon)\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 $\epsilon$ is any positive constant. The proof emphasizes general methods that appear to be useful for the analysis of many other combinatorial algorithms.


comments powered by Disqus

Contact Us


微信:OALib Journal