Introduction

Every year, thousands of medical students in the United States submit a ranked list of hospital residency programs, and each hospital ranks the applicants it would like to hire. A computer then finds the best possible assignment. The algorithm behind it — Gale-Shapley stable matching — runs in linear time and always finds a perfect stable matching when everyone is single.

A stable matching is one where no doctor and hospital both prefer each other to their current assignment. If such a blocking pair existed, they would defect, so stability is the natural fairness criterion.

But many medical students are couples — two doctors who want to train in the same city. They submit a joint ranked list of pairs of programs: "we would both go to Hospital A and Hospital B, or both to Hospital C and Hospital D, …". One partner cannot accept a position unless the other also has one nearby.

That single, reasonable constraint changes everything. Eitan Ronn proved in 1990 that deciding whether a stable matching even exists — let alone finding one — becomes NP-complete the moment couples enter the picture. The elegant linear-time algorithm breaks, and in the worst case no stable assignment exists at all.

This is not a theoretical curiosity. It is the real thorn inside the National Resident Matching Program (NRMP), the system that places 40,000+ doctors annually. Related work on stable matching and NP-completeness illuminates why this matters.

Try It

The demo below starts with a stable matching for three doctors and two hospitals — no blocking pairs exist. Then you add a couple who need to be co-located. Watch how their joint constraint creates a blocking pair in the current assignment, and how fixing it cascades into new instabilities.

<div class="hint">
  Three doctors compete for two hospitals. A <b>stable matching</b> has no blocking pair — no doctor and hospital both prefer each other over their current assignment. Add a couple who must <em>both</em> be placed, and watch every candidate matching become unstable.
</div>
<div id="scene">
  <div class="panel">
    <h3>Current Matching</h3>
    <div id="matching-display"></div>
  </div>
  <div class="panel">
    <h3>Preferences</h3>
    <div id="prefs-display"></div>
  </div>
</div>
<div class="status-box" id="status-box">Click "Check Stability" to start.</div>
<div class="btns">
  <button id="btn-couple" type="button">Add couple constraint</button>
  <button id="btn-cycle" type="button" disabled>Cycle candidate matchings</button>
  <button id="btn-check" type="button">Check stability</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: .92rem; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
#scene { display: flex; gap: 1rem; margin-bottom: .8rem; flex-wrap: wrap; }
.panel { flex: 1 1 180px; background: #f0f4f8; border-radius: 10px; padding: .75rem 1rem; }
.panel h3 { margin: 0 0 .5rem; font-size: .88rem; color: #1d3557; text-transform: uppercase; letter-spacing: .05em; }
.match-row { display: flex; align-items: center; gap: .4rem; margin: .28rem 0; font-weight: 600; font-size: .88rem; }
.doc { background: #1d3557; color: #fff; border-radius: 6px; padding: .12rem .45rem; }
.doc.ca { background: #6a4c93; }
.doc.cb { background: #a855f7; }
.hosp { background: #457b9d; color: #fff; border-radius: 6px; padding: .12rem .45rem; }
.arrow { color: #888; }
.unmatched { color: #888; font-style: italic; font-size: .85rem; }
.couple-badge { display: inline-block; background: #6a4c93; color: #fff;
                font-size: .7rem; border-radius: 4px; padding: 0 .3rem; margin-left: .25rem; }
.pref-row { margin: .22rem 0; font-size: .83rem; line-height: 1.4; }
.pref-label { font-weight: 700; color: #1d3557; }
.status-box { background: #e8eef3; border-radius: 8px; padding: .6rem .9rem;
              margin-bottom: .7rem; min-height: 2.4em; font-size: .88rem; line-height: 1.6; }
.status-box.ok  { background: #d4edda; color: #0a7d33; }
.status-box.bad { background: #fde8e8; color: #c92f3c; }
.status-box.warn { background: #fff3cd; color: #7d5a00; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 13px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Matching with Couples demo
//
// Doctors: A1 (couple), A2 (couple), B (single)
// Hospitals: H1 (cap 1), H2 (cap 1); one doctor goes unmatched.
//
// Preferences:
//   A1: H1 > H2 > unmatched
//   A2: H2 > H1 > unmatched
//   B:  H1 > H2 > unmatched
//   H1 ranks: B > A1 > A2
//   H2 ranks: A1 > A2 > B
//
// Singles-only stable matching: A1->H2, A2->unmatched, B->H1
//   (no blocking pairs — verified below)
//
// Couple constraint: A1 + A2 must BOTH be placed.
//   Joint pref list: (H1,H2) > (H2,H1) > (unmatched,unmatched)
//
// With couple constraint, try every valid assignment where both A1,A2 are placed:
//   Option (H1,H2) → A1->H1, A2->H2, B->null: blocking pair B+H1 (B wants H1, H1 prefers B over A1)
//   Option (H2,H1) → A1->H2, A2->H1, B->null: blocking pairs A1+H1 and B+H1
//   Result: NO stable matching exists when couple constraint is imposed.
//   This is Ronn's (1990) NP-hardness instantiated in a 3-doctor example.

const DOCS  = ['A1', 'A2', 'B'];
const HOSPS = ['H1', 'H2'];
const docPref  = { A1:['H1','H2',null], A2:['H2','H1',null], B:['H1','H2',null] };
const hospPref = { H1:['B','A1','A2'],   H2:['A1','A2','B'] };
const couplePref = [['H1','H2'],['H2','H1'],[null,null]];

// Candidates to cycle through once couple mode is on:
// 0: singles-stable (A1->H2,A2->null,B->H1)
// 1: couple option 1 (A1->H1,A2->H2,B->null)
// 2: couple option 2 (A1->H2,A2->H1,B->null)
const CANDIDATES = [
  { A1:'H2', A2:null,  B:'H1',  label:'Singles-stable: A1→H2, A2→unmatched, B→H1' },
  { A1:'H1', A2:'H2',  B:null,  label:'Couple option 1: A1→H1, A2→H2, B→unmatched' },
  { A1:'H2', A2:'H1',  B:null,  label:'Couple option 2: A1→H2, A2→H1, B→unmatched' },
];

let coupleMode = false;
let candidateIdx = 0;
let matching = Object.assign({}, CANDIDATES[0]);

function blockingPairs(m) {
  const pairs = [];
  for (const d of DOCS) {
    const curH = m[d];
    const curDocRank = curH === null ? 999 : docPref[d].indexOf(curH);
    for (const h of HOSPS) {
      if (h === curH) continue;
      const altRank = docPref[d].indexOf(h);
      if (altRank >= curDocRank) continue;
      const incumbent = DOCS.find(x => m[x] === h && x !== d) || null;
      const incRank = incumbent === null ? 999 : hospPref[h].indexOf(incumbent);
      if (hospPref[h].indexOf(d) < incRank) pairs.push({ doc:d, hosp:h, incumbent });
    }
  }
  return pairs;
}

function coupleOk(m) {
  for (const [ca,cb] of couplePref) {
    if (ca === m['A1'] && cb === m['A2']) return true;
  }
  return false;
}

function renderMatching() {
  const el = document.getElementById('matching-display');
  el.innerHTML = '';
  for (const d of DOCS) {
    const h = matching[d];
    const isA1 = coupleMode && d === 'A1';
    const isA2 = coupleMode && d === 'A2';
    const badge = (isA1 || isA2) ? '<span class="couple-badge">♥</span>' : '';
    el.innerHTML +=
      `<div class="match-row">` +
      `<span class="doc ${isA1?'ca':isA2?'cb':''}">${d}${badge}</span>` +
      `<span class="arrow">→</span>` +
      (h ? `<span class="hosp">${h}</span>` : '<span class="unmatched">unmatched</span>') +
      `</div>`;
  }
}

function renderPrefs() {
  const el = document.getElementById('prefs-display');
  el.innerHTML = '';
  for (const d of DOCS) {
    const isA1 = coupleMode && d === 'A1';
    const isA2 = coupleMode && d === 'A2';
    const badge = (isA1||isA2) ? '<span class="couple-badge">♥</span>' : '';
    el.innerHTML += `<div class="pref-row"><span class="pref-label">${d}${badge}:</span> ` +
      docPref[d].map(h=>h||'none').join(' > ') + `</div>`;
  }
  for (const h of HOSPS) {
    el.innerHTML += `<div class="pref-row"><span class="pref-label">${h}:</span> ` +
      hospPref[h].join(' > ') + `</div>`;
  }
  if (coupleMode) {
    el.innerHTML += fmt('<div class="pref-row" style="margin-top:.4rem;border-top:1px solid #cdd9e3;padding-top:.4rem"><span class="pref-label">Couple (A1+A2):</span><br>%map%</div>', { map: couplePref.map(([a,b])=>`(${a||'none'},${b||'none'})`).join(' > ') });
  }
}

function setStatus(msg, cls) {
  const el = document.getElementById('status-box');
  el.innerHTML = msg;
  el.className = 'status-box ' + (cls||'');
}

function check() {
  const bp = blockingPairs(matching);
  if (!coupleMode) {
    if (bp.length === 0) {
      setStatus('✓ Stable! No blocking pairs exist in the singles-only case.', 'ok');
    } else {
      const desc = bp.map(({doc,hosp})=>`<b>${doc}</b> and <b>${hosp}</b>`).join(', ');
      setStatus(fmt('✗ Unstable — blocking pair(s): %desc%', { desc: desc }), 'bad');
    }
    return;
  }
  const cOk = coupleOk(matching);
  const issues = [];
  if (!cOk) {
    const aH = matching['A1']||'unmatched', bH = matching['A2']||'unmatched';
    issues.push(fmt('Couple violated: A1@%aH% + A2@%bH% not on their joint list', { aH: aH, bH: bH }));
  }
  if (bp.length > 0) {
    issues.push(fmt('Blocking pair(s): %map%', { map: bp.map(({doc,hosp})=>`${doc}↔${hosp}`).join(', ') }));
  }
  if (issues.length === 0) {
    setStatus('✓ Stable and couple satisfied! (Try all 3 options — none are stable.)', 'ok');
  } else {
    setStatus('✗ ' + issues.join(' | ') +
      (candidateIdx===2 ? '<br><b>All options checked — no stable matching exists with the couple constraint!</b>' : ''), 'bad');
  }
}

document.getElementById('btn-couple').addEventListener('click', () => {
  coupleMode = true;
  candidateIdx = 0;
  matching = Object.assign({}, CANDIDATES[0]);
  document.getElementById('btn-couple').disabled = true;
  document.getElementById('btn-cycle').disabled = false;
  renderMatching();
  renderPrefs();
  setStatus('Couple constraint added! A1 + A2 must both be placed. Check stability for each candidate matching.', 'warn');
});

document.getElementById('btn-cycle').addEventListener('click', () => {
  candidateIdx = (candidateIdx + 1) % CANDIDATES.length;
  matching = Object.assign({}, CANDIDATES[candidateIdx]);
  renderMatching();
  const c = CANDIDATES[candidateIdx];
  setStatus(fmt('Now showing: %label%. Press "Check Stability".', { label: c.label }), '');
});

document.getElementById('btn-check').addEventListener('click', check);

document.getElementById('btn-reset').addEventListener('click', () => {
  coupleMode = false;
  candidateIdx = 0;
  matching = Object.assign({}, CANDIDATES[0]);
  document.getElementById('btn-couple').disabled = false;
  document.getElementById('btn-cycle').disabled = true;
  renderMatching();
  renderPrefs();
  setStatus('Click "Check Stability" to start.', '');
});

// Node-verifiable assertions (run at load; visible in console)
(function verify() {
  // 1. Singles-stable matching has 0 blocking pairs
  const m0 = CANDIDATES[0];
  const bp0 = blockingPairs(m0);
  console.assert(bp0.length === 0, 'FAIL: singles-stable should have 0 BP', bp0);
  console.log('VERIFY 1: singles-stable BP count =', bp0.length, '(expected 0) ✓');

  // 2. Singles-stable violates couple constraint (A2 unmatched)
  const c0 = coupleOk(m0);
  console.assert(c0 === false, 'FAIL: singles-stable should violate couple constraint');
  console.log('VERIFY 2: singles-stable couple ok =', c0, '(expected false) ✓');

  // 3. Couple option 1 has blocking pair (B+H1)
  const m1 = CANDIDATES[1];
  const bp1 = blockingPairs(m1);
  const hasB_H1 = bp1.some(x => x.doc==='B' && x.hosp==='H1');
  console.assert(hasB_H1, 'FAIL: option1 should have B+H1 blocking pair', bp1);
  console.log('VERIFY 3: option1 BP =', bp1.map(x=>x.doc+'+'+x.hosp), '(expected B+H1) ✓');

  // 4. Couple option 2 has blocking pairs (A1+H1 and B+H1)
  const m2 = CANDIDATES[2];
  const bp2 = blockingPairs(m2);
  const hasA1_H1 = bp2.some(x => x.doc==='A1' && x.hosp==='H1');
  const hasB_H1b = bp2.some(x => x.doc==='B'  && x.hosp==='H1');
  console.assert(hasA1_H1 && hasB_H1b, 'FAIL: option2 should have A1+H1 and B+H1', bp2);
  console.log('VERIFY 4: option2 BP =', bp2.map(x=>x.doc+'+'+x.hosp), '(expected A1+H1, B+H1) ✓');

  // 5. Both couple options satisfy couple constraint
  console.assert(coupleOk(m1), 'FAIL: option1 should satisfy couple pref (H1,H2)');
  console.assert(coupleOk(m2), 'FAIL: option2 should satisfy couple pref (H2,H1)');
  console.log('VERIFY 5: both couple options satisfy joint pref ✓');

  console.log('All verifications passed. No stable matching with couple constraint exists.');
})();

renderMatching();
renderPrefs();
Result
Console

Click Add couple constraint to introduce the couple, then Check stability to see which blocking pairs appear. Use Try to fix to watch the repair attempt — and notice it may never settle.

The Real Complexity

Why does one extra constraint flip an easy problem to a hard one?

The singles case is easy. The Gale-Shapley algorithm (1962) finds a stable matching in O(n2)O(n^{2}) time for n singles on each side. Everyone gets a match, stability is guaranteed, and the algorithm is optimal for the proposing side.

Couples destroy these guarantees. A couple must be placed at two hospitals simultaneously. If hospital A accepts one partner and hospital B accepts the other, great. But if either hospital rejects its partner — or is already full — the couple is unplaced, the displaced doctors re-enter the pool, and cascading rejections can cycle forever.

Ronn's 1990 result. Eitan Ronn showed by reduction from 3-SAT that the problem "does a stable matching exist?" is NP-complete even when only a single couple is present. This means:

  • No polynomial-time algorithm is known for the general case.
  • Unlike singles, a stable matching may not exist at all — the instance can simply be infeasible.
  • Checking a proposed matching for stability is still easy (polynomial), but finding one is as hard as SAT.

Practical scale matters. The NRMP typically has only a few hundred couples out of 40,000+ participants, and in practice a stable matching almost always exists. Heuristic extensions of Gale-Shapley work well on real data. But the worst-case guarantee is gone, and the algorithm can in principle loop or fail.

This is a vivid example of how a small, natural extension to a tractable problem can jump it into NP-hard territory — just as P vs NP predicts.

Where It Matters

The difficulty introduced by couples shows up wherever agents bundle their preferences:

  • Medical residency (NRMP): the largest real deployment. The NRMP runs a modified Gale-Shapley that handles couples heuristically; it succeeds in practice but has no worst-case guarantee.
  • Academic job market: spousal hires in academia are a direct analog — two candidates who both need offers from the same institution or nearby ones.
  • School choice: families with multiple children may insist all children attend schools in the same district, creating coupled constraints on what is otherwise a single-agent assignment.
  • Kidney exchange: paired donation chains where two patients each need a compatible kidney from each other's donor — both transplants must happen, or neither does.
  • Two-sided platforms: any marketplace where a participant's acceptance depends on a simultaneous outcome for a partner faces the same structural difficulty.

The theoretical lesson is equally important: it illustrates that small, natural extensions can push tractable problems into NP-hardness, a theme central to algorithmic complexity theory.

Conclusion

Stable matching is one of computer science's most beautiful results: a simple algorithm that always finds a fair assignment, provably optimal for one side. Couples shatter that elegance with a single joint constraint — and Ronn's 1990 proof shows the breakage runs deep, all the way to NP-completeness.

The NRMP and similar programs live with this every year, relying on heuristics that work well in practice even though the worst case is intractable. It is a reminder that real-world algorithms often succeed where theory says they might fail — and that understanding the theoretical limit is precisely what lets engineers build systems that skirt it wisely.

The next time you hear that two doctors "matched as a couple," remember: finding that match was, in the worst case, as hard as SAT — and might have been impossible altogether.

Share this article

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

Comments

Loading comments...

https://www.kipuhub.com/en/article/matching-with-couples/Content licensed under CC BY-NC 4.0.