All Title Author
Keywords Abstract

Mathematics  1990 

Stable husbands

Full-Text   Cite this paper   Add to My Lib

Abstract:

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.

Full-Text

comments powered by Disqus

Contact Us

service@oalib.com

QQ:3279437679

微信:OALib Journal