Introduction

Suppose you have two equal groups — say, applicants and hospitals — and everyone ranks the other side from most to least preferred. You want to pair them up one-to-one. A matching is unstable if there is some pair who are not matched to each other yet both prefer each other over their assigned partners. That pair would simply break away — and the whole arrangement unravels.

The goal is a stable matching: one where no such runaway pair exists. Everyone has a partner, and nobody can find a willing partner they like more.

Two questions immediately follow. Does a stable matching always exist, no matter how tangled the preferences? And if so, can we find one quickly? In 1962 David Gale and Lloyd Shapley answered both with a single elegant procedure — and decades later it earned a Nobel Prize.

Run the Algorithm

Here are four applicants (A–D) and four companies (1–4), each with a private ranking of the other side. Press Next round to let every unmatched applicant propose to their most-preferred company that hasn't yet rejected them. Each company tentatively holds its best proposer and turns the rest away.

<p class="hint">Four applicants (A–D) and four companies (1–4) each rank the other side. Each round, every free applicant proposes to its top remaining choice; each company tentatively holds its best proposer and rejects the rest. Watch the holds settle into a stable matching.</p>
<div class="cols">
  <div class="panel">
    <h4>Applicants → prefer</h4>
    <div id="apref" class="prefs"></div>
  </div>
  <div class="panel">
    <h4>Companies → prefer</h4>
    <div id="copref" class="prefs"></div>
  </div>
</div>
<div class="matchbox" id="match"></div>
<div class="status" id="status">Press "Next round" to begin.</div>
<div class="btns">
  <button id="next" type="button">Next round</button>
  <button id="run" type="button">Run to end</button>
  <button id="verify" type="button" class="ghost">Verify stability</button>
  <button id="reset" type="button" class="ghost">Reset</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; }
.cols { display: flex; gap: 1rem; flex-wrap: wrap; }
.panel { flex: 1 1 220px; }
h4 { margin: 0 0 .4rem; font-size: .85rem; color: #1d3557; }
.prefs { font: 600 13px ui-monospace, monospace; line-height: 1.7; color: #333; }
.prefs .who { color: #1d3557; }
.matchbox { display: grid; grid-template-columns: repeat(4, 1fr); gap: 6px; margin: .8rem 0 .3rem; }
.pair { background: #e8eef3; border: 1px solid #cdd9e3; border-radius: 8px;
        padding: .5rem; text-align: center; font: 700 15px ui-monospace, monospace; color: #1d3557; }
.pair.free { background: #f3f4f6; color: #9aa0a6; border-color: #e2e4e8; }
.pair small { display: block; font: 600 10px system-ui; color: #6b7480; margin-top: 2px; }
.pair.changed { background: #d7ead9; border-color: #8fc79a; }
.status { font-size: 1rem; font-weight: 600; margin: .5rem 0; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .45; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Gale-Shapley deferred acceptance (1962). Applicants propose; companies hold the best proposer so far and reject the rest. Always yields a STABLE matching in O(n^2).
const APPS = ['A','B','C','D'];
const COS  = ['1','2','3','4'];
// Each applicant's ranking of companies (most preferred first).
const APREF = { A:['1','2','3','4'], B:['1','4','3','2'], C:['2','1','4','3'], D:['4','2','3','1'] };
// Each company's ranking of applicants (most preferred first).
const COPREF = { '1':['C','A','D','B'], '2':['A','C','B','D'], '3':['B','D','A','C'], '4':['D','B','A','C'] };

let next, held, prevHeld, done;
function reset(){
  next = {}; APPS.forEach(a => next[a] = 0); // index into APREF[a] of next company to ask
  held = {}; COS.forEach(c => held[c] = null); // company -> currently held applicant
  prevHeld = {}; done = false;
  setStatus('Press "Next round" to begin.','');
  render();
}
const rank = (list, x) => list.indexOf(x);

// One round: every currently-free applicant proposes to its next choice.
function round(){
  if (done) return;
  prevHeld = Object.assign({}, held);
  const matchedApps = new Set(Object.values(held).filter(Boolean));
  const proposers = APPS.filter(a => !matchedApps.has(a) && next[a] < COS.length);
  if (proposers.length === 0){ done = true; setStatus('Done — every applicant is matched. The holds are now final.','ok'); render(); return; }
  let events = 0;
  for (const a of proposers){
    const c = APREF[a][next[a]]; next[a]++;
    const cur = held[c];
    if (cur === null){ held[c] = a; events++; }
    else if (rank(COPREF[c], a) < rank(COPREF[c], cur)){ held[c] = a; events++; } // a is better
    // else: company keeps cur, a is rejected and will try its next choice later
  }
  setStatus(fmt('%length% applicant(s) proposed; %events% tentative hold(s) updated.', { length: proposers.length, events: events }),'');
  render();
}

// A matching is stable iff no applicant a and company c both prefer each other over their current partners.
function partnerOf(){ const p = {}; for (const c of COS){ if (held[c]) p[held[c]] = c; } return p; }
function verify(){
  const p = partnerOf();
  for (const a of APPS){
    const ac = p[a];
    for (const c of COS){
      if (c === ac) continue;
      const cur = held[c];
      const aPrefersC = ac == null || rank(APREF[a], c) < rank(APREF[a], ac);
      const cPrefersA = cur == null || rank(COPREF[c], a) < rank(COPREF[c], cur);
      if (aPrefersC && cPrefersA){
        setStatus(fmt('UNSTABLE: %a% and %c% both prefer each other!', { a: a, c: c }),'bad');
        console.log('blocking pair', a, c); return false;
      }
    }
  }
  setStatus('Stable — no pair would run away. ✓','ok');
  console.log('matching', p, 'is stable'); return true;
}

function render(){
  const ap = document.getElementById('apref'); ap.innerHTML = APPS.map(a =>
    '<div><span class="who">'+a+'</span>: '+APREF[a].join(' > ')+'</div>').join('');
  const cp = document.getElementById('copref'); cp.innerHTML = COS.map(c =>
    '<div><span class="who">'+c+'</span>: '+COPREF[c].join(' > ')+'</div>').join('');
  const p = partnerOf();
  document.getElementById('match').innerHTML = APPS.map(a => {
    const c = p[a];
    const changed = c && prevHeld[c] !== held[c];
    return '<div class="pair '+(c?'':'free')+(changed?' changed':'')+'">'+a+
      (c? ' &harr; '+c : ' &harr; ?')+'<small>'+(c?'held':'free')+'</small></div>';
  }).join('');
  document.getElementById('next').disabled = done;
  document.getElementById('run').disabled = done;
}
function setStatus(t,cls){ const s=document.getElementById('status'); s.textContent=t; s.className='status '+cls; }

document.getElementById('next').addEventListener('click', round);
document.getElementById('run').addEventListener('click', ()=>{ let g=0; while(!done && g++<50) round(); });
document.getElementById('verify').addEventListener('click', verify);
document.getElementById('reset').addEventListener('click', reset);
reset();
Result
Console

Watch how a company can drop a tentative partner the moment a better proposer shows up — that "deferred acceptance" is the whole trick. After at most a handful of rounds, nobody is left proposing and the holds become final. The result is always stable: check any pair you like, and at least one of them prefers who they ended up with. Try pressing Verify: the demo searches for any runaway pair and finds none.

The Real Complexity

What makes stable marriage remarkable is how clean the answer is.

  • A solution always exists. Gale and Shapley proved in 1962 that for any set of preference lists, at least one stable matching exists. No exceptions, no pathological inputs.
  • It is found in polynomial time. Their deferred acceptance algorithm terminates after at most n2n^{2} proposals and runs in O(n2)O(n^{2}) time — fast and practical even for tens of thousands of participants.
  • The proof is the algorithm. Each rejected applicant only moves down their list, so the process must stop; when it does, no runaway pair can exist. Existence and efficiency come from the very same argument.
  • It has a bias. The side that proposes gets its best possible stable partner, while the receiving side gets its worst possible one. Same problem, but who proposes matters.

So unlike the traveling salesman or SAT — where finding an answer may be intractable — stable marriage sits firmly in P. In 2012, Lloyd Shapley and Alvin Roth shared the Nobel Memorial Prize in Economic Sciences: Shapley for the theory, Roth for turning it into systems that match real people.

Where It Matters

"Pair two sides by preference so nobody wants to defect" is a shape that appears across the real world, and deferred acceptance is its workhorse:

  • Medical residency: the U.S. National Resident Matching Program places tens of thousands of new doctors into hospitals every year using a Gale-Shapley-style algorithm.
  • School choice: cities like New York and Boston assign students to schools with deferred acceptance, replacing earlier systems that punished honest ranking.
  • Kidney exchange: matching markets pair incompatible donor-patient pairs into chains, closely related to organ matching.
  • Market design: the broader field Roth helped build uses stability as the rule that keeps a centralized market from quietly falling apart.

Learn why stability matters and you've met market design — the engineering of fair, efficient matchings that people won't try to game or escape.

Conclusion

Stable marriage is the happy opposite of the hard problems. A solution is guaranteed to exist, the proof of existence is itself a fast algorithm, and the result is fair in a precise, defensible sense. That trio — exists, efficient, principled — is exactly why deferred acceptance escaped the textbook and now quietly assigns doctors, students, and donors.

The next time you're sorted into a school, a residency, or a program and it just feels right that no swap would make two people happier, you may be looking at Gale and Shapley's idea at work — a polynomial-time guarantee that, against the odds, everyone can live with.

Share this article

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

Comments

Loading comments...

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