Random stable roommates

Definitions and mathematical statement

Let $n$ be an even positive integer and let the participants be $\{1,\ldots,n\}$. For each participant independently, choose a strict total ordering of the other $n-1$ participants uniformly from all $(n-1)!$ orders. These random rankings constitute the random stable-roommates model: there is one population, with no prescribed bipartition into two sides.

A matching is a partition of all participants into unordered pairs. If $M(i)$ denotes the partner of participant $i$, a blocking pair is a pair $\{i,j\}$ not in the matching for which $i$ ranks $j$ above $M(i)$ and $j$ ranks $i$ above $M(j)$. A matching is stable if no blocking pair exists. Let $P_n$ be the probability, over all independent rankings, that at least one stable matching exists.

The conjecture is \[ P_n=\Theta(n^{-1/4}) \qquad(n\longrightarrow\infty,\ n\text{ even}). \] Explicitly, there should be constants $0<c\le C<\infty$ and an integer $N$ such that $c n^{-1/4}\le P_n\le C n^{-1/4}$ for every even $n\ge N$.

The probability concerns existence of any stable matching, rather than stability of one predetermined matching or the expected number of stable matchings. Rankings contain neither ties nor unacceptable partners, and stability is tested against every unmatched pair. Determining a leading asymptotic constant would strengthen the stated problem but is not required by the two-sided order estimate.

Short English statement

For independent uniformly random roommate preferences, is the probability that any stable pairing exists of order n to the power minus one quarter?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3182 (OPG-743), OpenGarden. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Random stable roommates. Original problem and discussion. http://www.openproblemgarden.org/op/random_stable_roommates.