Introduction

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.

Try It

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">Four people, each ranking the other three. Click a pairing below. A <b>blocking pair</b> is two people who'd both rather be together than with their assigned roommate. A pairing with <b>no</b> blocking pairs is stable.</p>
<div class="prefs" id="prefs"></div>
<div class="scenario">
  <button id="sc-stable" type="button" class="pill active">Stable scenario</button>
  <button id="sc-impossible" type="button" class="pill">Impossible scenario</button>
</div>
<p class="sub">Choose a pairing:</p>
<div class="choices" id="choices"></div>
<div class="status" id="status">Pick a pairing, or press Solve.</div>
<div class="btns">
  <button id="solve" type="button">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Stable roommates: 4 people, each ranks the other three. A "pairing" splits them
// into two pairs. A blocking pair = two people NOT paired together who each prefer
// the other to their current roommate. A pairing is stable iff it has no blocking
// pair. With n=4 there are exactly 3 perfect pairings; we just check all three.
const PEOPLE = ['A','B','C','D'];

// Preference lists (most preferred first). Two scenarios.
const SCENARIOS = {
  // Stable: A-B + C-D is stable (verified below).
  stable: { A:['B','C','D'], B:['A','C','D'], C:['D','A','B'], D:['C','A','B'] },
  // Classic impossible instance: A,B,C cyclically prefer each other; D is last for all.
  impossible: { A:['B','C','D'], B:['C','A','D'], C:['A','B','D'], D:['A','B','C'] }
};

// The 3 ways to split 4 people into two pairs.
const PAIRINGS = [
  [['A','B'],['C','D']],
  [['A','C'],['B','D']],
  [['A','D'],['B','C']]
];

let scenario = 'stable';
let selected = -1;

// rank(prefs,x,y): position of y in x's list (0 = most preferred). Lower = better.
function rank(prefs, x, y){ return prefs[x].indexOf(y); }
// partner of x within a pairing
function partnerOf(pairing, x){
  for(const [a,b] of pairing){ if(a===x) return b; if(b===x) return a; }
  return null;
}
// Find a blocking pair in a pairing, or null if stable.
function blockingPair(prefs, pairing){
  for(let i=0;i<PEOPLE.length;i++)for(let j=i+1;j<PEOPLE.length;j++){
    const x=PEOPLE[i], y=PEOPLE[j];
    if(partnerOf(pairing,x)===y) continue; // already together
    const xPrefersY = rank(prefs,x,y) < rank(prefs,x,partnerOf(pairing,x));
    const yPrefersX = rank(prefs,y,x) < rank(prefs,y,partnerOf(pairing,y));
    if(xPrefersY && yPrefersX) return [x,y];
  }
  return null;
}

function fmtPairing(p){ return p.map(([a,b])=>a+'-'+b).join('  &  '); }

function renderPrefs(){
  const prefs = SCENARIOS[scenario];
  const el = document.getElementById('prefs'); el.innerHTML='';
  PEOPLE.forEach(p=>{
    const d=document.createElement('div'); d.className='pref';
    d.innerHTML=fmt('<b>%p%</b> prefers: %v%', { p: p, v: prefs[p].join(' &gt; ') });
    el.appendChild(d);
  });
}
function renderChoices(){
  const prefs = SCENARIOS[scenario];
  const el = document.getElementById('choices'); el.innerHTML='';
  PAIRINGS.forEach((p,i)=>{
    const d=document.createElement('div'); d.className='choice'+(selected===i?' sel':'');
    const bp = blockingPair(prefs,p);
    let tag='';
    if(selected===i){
      tag = bp ? fmt('<span class="tag bad">blocked: %bp%</span>', { bp: bp.join('+') })
               : '<span class="tag ok">stable</span>';
    }
    d.innerHTML='<span>'+fmtPairing(p)+'</span>'+tag;
    d.addEventListener('click',()=>{
      selected=i; renderChoices();
      if(bp) setStatus(fmt('Blocking pair %v%+%v2% — both prefer each other. Not stable.', { v: bp[0], v2: bp[1] }),'bad');
      else setStatus('No blocking pair — this pairing is stable!','ok');
    });
    el.appendChild(d);
  });
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+(cls||''); }

function solve(){
  const prefs = SCENARIOS[scenario];
  for(let i=0;i<PAIRINGS.length;i++){
    if(!blockingPair(prefs,PAIRINGS[i])){
      selected=i; renderChoices();
      setStatus(fmt('Solved: %fmtPairing% is stable (0 blocking pairs).', { fmtPairing: fmtPairing(PAIRINGS[i]) }),'ok');
      console.log('Stable matching:', fmtPairing(PAIRINGS[i]));
      return;
    }
  }
  selected=-1; renderChoices();
  setStatus('No stable matching exists — every pairing has a blocking pair.','bad');
  console.log('No stable matching exists for scenario:', scenario);
}
function setScenario(s){
  scenario=s; selected=-1;
  document.getElementById('sc-stable').classList.toggle('active', s==='stable');
  document.getElementById('sc-impossible').classList.toggle('active', s==='impossible');
  renderPrefs(); renderChoices(); setStatus('Pick a pairing, or press Solve.','');
}
document.getElementById('sc-stable').addEventListener('click',()=>setScenario('stable'));
document.getElementById('sc-impossible').addEventListener('click',()=>setScenario('impossible'));
document.getElementById('solve').addEventListener('click',solve);
setScenario('stable');
Result
Console

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.

The Real Complexity

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(n2)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.

Where It Matters

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.

Conclusion

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(n2)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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/stable-roommates/Content licensed under CC BY-NC 4.0.