The random stable roommates problem typically has no solution
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917196183109632 |
|---|---|
| author | Chin, Byron Michelen, Marcus |
| author_facet | Chin, Byron Michelen, Marcus |
| contents | Assume that $n = 2k$ potential roommates each have an ordered preference of the $n-1$ others. A stable matching is a perfect matching of the $n$ roommates in which no two unmatched people prefer each other to their matched partners. In their seminal 1962 stable marriage paper, Gale and Shapley noted that not every instance of the stable roommates problem admits a stable matching. In the case when the preferences are chosen uniformly at random, Gusfield and Irving predicted in 1989 that there is no stable matching with high probability for large $n$. We prove this conjecture and show that for $n$ sufficiently large, the probability there is a stable matching is at most $n^{-1/17}$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_07612 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The random stable roommates problem typically has no solution Chin, Byron Michelen, Marcus Combinatorics Probability Assume that $n = 2k$ potential roommates each have an ordered preference of the $n-1$ others. A stable matching is a perfect matching of the $n$ roommates in which no two unmatched people prefer each other to their matched partners. In their seminal 1962 stable marriage paper, Gale and Shapley noted that not every instance of the stable roommates problem admits a stable matching. In the case when the preferences are chosen uniformly at random, Gusfield and Irving predicted in 1989 that there is no stable matching with high probability for large $n$. We prove this conjecture and show that for $n$ sufficiently large, the probability there is a stable matching is at most $n^{-1/17}$. |
| title | The random stable roommates problem typically has no solution |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2601.07612 |