Stable Roommates

Imagine a dorm where an even number of students must be split into pairs of roommates. Each student has ranked everyone else from most to least preferred. You want a pairing that is stable: no two students who aren't paired together would both rather ditch their assigned roommate and move in with each other.

Such a troublesome duo is called a blocking pair — two people who mutually prefer each other to their current partners. A pairing is stable exactly when it has zero blocking pairs.

This sounds like the famous stable marriage problem, where the people split neatly into two sides. But here there are no sides — anyone can pair with anyone. That one change has a startling consequence: a stable pairing might not exist at all.

Below are four people, each with a ranking of the other three. Pick a pairing by clicking, and the demo highlights any blocking pair — two people who would both rather be together than with their assigned roommate. A pairing with no blocking pairs is stable.

<p class="hint">{{hint}}</p>
<div class="prefs" id="prefs"></div>
<div class="scenario">
  <button id="sc-stable" type="button" class="pill active">{{btn_stable}}</button>
  <button id="sc-impossible" type="button" class="pill">{{btn_impossible}}</button>
</div>
<p class="sub">{{sub}}</p>
<div class="choices" id="choices"></div>
<div class="status" id="status">{{pick_prompt}}</div>
<div class="btns">
  <button id="solve" type="button">{{btn_solve}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.sub { font-size: .85rem; color: #555; margin: .6rem 0 .3rem; font-weight: 600; }
.prefs { display: grid; grid-template-columns: repeat(2, 1fr); gap: .4rem; }
.pref { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px;
        padding: .4rem .6rem; font-size: .85rem; }
.pref b { color: #1d3557; }
.scenario { display: flex; gap: .5rem; margin: .7rem 0 .2rem; flex-wrap: wrap; }
.pill { font: 600 13px system-ui, sans-serif; padding: .35rem .8rem; border-radius: 999px;
        border: 1px solid #1d3557; background: #fff; color: #1d3557; cursor: pointer; }
.pill.active { background: #1d3557; color: #fff; }
.choices { display: flex; flex-direction: column; gap: .4rem; }
.choice { display: flex; align-items: center; gap: .5rem; cursor: pointer;
          background: #f4f6f9; border: 1px solid #d8e0e8; border-radius: 8px; padding: .5rem .7rem;
          font-size: .9rem; transition: all .1s; }
.choice:hover { background: #e9eef4; }
.choice.sel { border-color: #1d3557; background: #dde7f1; }
.choice .tag { margin-left: auto; font-size: .78rem; font-weight: 700; padding: .15rem .5rem;
               border-radius: 6px; }
.choice .tag.ok { background: #cdeccd; color: #0a7d33; }
.choice .tag.bad { background: #f7d4d8; color: #c92f3c; }
.status { font-size: 1rem; font-weight: 600; margin: .6rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; }
button#solve { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }

// Code not found

Toggle between the two scenarios. In the stable case, one pairing has no blocking pairs at all. In the impossible case — a classic example — every one of the three possible pairings has a blocking pair, so no stable matching exists. Press Solve to let the algorithm search and announce the verdict.

What makes stable roommates fascinating is not that it is hard, but that an answer may simply not exist — and we can tell, fast.

• Existence is not guaranteed. Unlike stable marriage, which always has a stable matching (Gale & Shapley, 1962), stable roommates can have none. The smallest example has just four people.
• It is solved and efficient. In 1985, Robert W. Irving gave an algorithm that runs in $O(n^{2})$ time — polynomial — and either outputs a stable matching or reports, with certainty, that none exists.
• How it works. Phase 1 is a round of proposals like stable marriage: people propose down their lists and get provisionally held or rejected, pruning impossible options. Phase 2 hunts down "rotations" — cyclic chains of preference — and eliminates them. If the lists collapse to one partner each, that's the stable matching; if anyone's list empties out, no stable matching exists.

So this problem sits firmly in P, the class of efficiently solvable problems — far from the intractable wall of P vs NP. The twist is purely about existence: the algorithm's real job is to decide whether the question even has an answer.

Whenever members of a single group must be matched among themselves — with no natural two-sided split — you are in stable-roommates territory:

• Roommate and partner assignment: dorms, ride-sharing pools and study pairs where anyone could be paired with anyone.
• Peer-to-peer networks: nodes pairing up to swap data, each preferring faster or closer peers.
• Tournament pairings: pairing players of similar strength while respecting who has already played whom.
• Kidney exchange: patient–donor pairs swap kidneys; modeling who can stably trade with whom is a cousin of this problem.

It also reshaped economics: the stable-matching theory behind it earned Lloyd Shapley and Alvin Roth the 2012 Nobel Memorial Prize. The roommates variant is the cautionary tale — a reminder that in one-sided markets, a perfectly stable outcome may be mathematically out of reach. Related reading: stable marriage and maximum matching.

Stable roommates is a rare and beautiful case in computer science: a question that can genuinely have no answer, paired with an algorithm that tells you so quickly. Drop the two-sided structure of marriage, and the guarantee of stability evaporates — yet Irving's $O(n^{2})$ method still decides the matter with total confidence.

The lesson outlasts the dorm. Many real systems ask people, machines or markets to pair off among equals, and "is there even a stable way to do this?" is not always a yes. Sometimes the honest, provable answer is no — and knowing that, efficiently, is its own kind of victory.