Stable Marriage

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.

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">{{hint}}</p>
<div class="cols">
  <div class="panel">
    <h4>{{h_app_pref}}</h4>
    <div id="apref" class="prefs"></div>
  </div>
  <div class="panel">
    <h4>{{h_co_pref}}</h4>
    <div id="copref" class="prefs"></div>
  </div>
</div>
<div class="matchbox" id="match"></div>
<div class="status" id="status">{{status_begin}}</div>
<div class="btns">
  <button id="next" type="button">{{btn_next}}</button>
  <button id="run" type="button">{{btn_run}}</button>
  <button id="verify" type="button" class="ghost">{{btn_verify}}</button>
  <button id="reset" type="button" class="ghost">{{btn_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; }

// Code not found

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.

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 $n^{2}$ proposals and runs in $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.

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

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.