Matching with Couples

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.

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">
  {{hint}}
</div>
<div id="scene">
  <div class="panel">
    <h3>{{h_matching}}</h3>
    <div id="matching-display"></div>
  </div>
  <div class="panel">
    <h3>{{h_prefs}}</h3>
    <div id="prefs-display"></div>
  </div>
</div>
<div class="status-box" id="status-box">{{status_initial}}</div>
<div class="btns">
  <button id="btn-couple" type="button">{{btn_couple}}</button>
  <button id="btn-cycle" type="button" disabled>{{btn_cycle}}</button>
  <button id="btn-check" type="button">{{btn_check}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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

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.

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.