The random stable roommates problem typically has no solution
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.07612
curl -X POST /api/v1/records/arxiv/2601.07612/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.07612/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'