stable marriage


Random stable roommates ★★

Author(s): Mertens

\begin{conjecture} The probability that a random instance of the stable roommates problem on $n \in 2{\mathbb N}$ people admits a solution is $\Theta( n ^{-1/4} )$. \end{conjecture}

Keywords: stable marriage; stable roommates

Syndicate content