Deferred Acceptance

Every year, thousands of medical students in the United States submit rank-ordered lists of residency programs. Hospitals submit rank-ordered lists of candidates. A computer runs for a few seconds, and every student learns where they will train. No one defects. No one has reason to.

The algorithm behind this is Gale–Shapley deferred acceptance, published in 1962 by David Gale and Lloyd Shapley. Its idea is disarmingly simple: one side proposes, the other side tentatively accepts — but reserves the right to swap a held proposal for a better one later. Proposals flow, rejections accumulate, and the process terminates in a stable matching: a pairing where no student and no hospital would both prefer to be matched to each other instead.

In 2012 the Nobel Prize in Economic Sciences went to Lloyd Shapley and Alvin Roth for this work and its real-world applications. The mathematics was clean; the social impact was enormous.

Below, four students (left) and four programs (right) each have a private preference list. Press Step to advance one round of proposals, or Run to watch the algorithm converge automatically. A dashed line means a tentative hold; a solid line means a final match.

<!-- {{c_html_intro}} -->
<p class="hint">{{hint_para}}</p>
<div class="arena">
  <div class="col" id="col-students">
    <div class="col-label">{{label_students}}</div>
  </div>
  <div class="col col-mid" id="col-lines">
    <svg id="lines-svg" width="160" height="300"></svg>
  </div>
  <div class="col" id="col-programs">
    <div class="col-label">{{label_programs}}</div>
  </div>
</div>
<div class="status-area" id="status">{{status_ready}}</div>
<div class="log-area" id="log"></div>
<div class="btns">
  <button id="btn-step" type="button">{{btn_step}}</button>
  <button id="btn-run" type="button">{{btn_run}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_intro}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
.arena { display: flex; align-items: flex-start; gap: 0; margin-bottom: .4rem; }
.col { display: flex; flex-direction: column; gap: 6px; min-width: 80px; }
.col-mid { flex: 1; align-items: center; padding-top: 28px; }
.col-label { font-size: .75rem; font-weight: 700; text-transform: uppercase;
             letter-spacing: .06em; color: #666; margin-bottom: 4px; text-align: center; }
.node { width: 70px; height: 40px; border-radius: 8px; display: flex; align-items: center;
        justify-content: center; font: 700 13px ui-monospace, monospace; user-select: none;
        border: 2px solid transparent; transition: background .15s, border-color .15s; }
.node.student { background: #dbeafe; color: #1e3a8a; border-color: #93c5fd; }
.node.program { background: #dcfce7; color: #14532d; border-color: #86efac; }
.node.matched { border-width: 2.5px; }
.node.student.matched { border-color: #2563eb; }
.node.program.matched { border-color: #16a34a; }
#lines-svg { overflow: visible; }
.status-area { font-size: .95rem; font-weight: 600; min-height: 1.4em; margin: .3rem 0; }
.status-area.ok { color: #0a7d33; }
.status-area.info { color: #1e3a8a; }
.log-area { font-size: .8rem; color: #555; min-height: 2.4em; line-height: 1.5; margin-bottom: .5rem; }
.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: not-allowed; }
.pref-list { font-size: .72rem; color: #777; margin-top: 1px; text-align: center; }

// Code not found

Notice: students propose in order of their preference. A program holds only its best current offer and defers accepting until no better proposal can arrive. Once a program rejects a student, that student moves on — rejections are final. The result is always stable.

Deferred acceptance looks like it might cycle or stall, but it doesn't. Here is why it is actually well-behaved — and where genuine difficulty lurks.

Runtime. Each student proposes to each program at most once, so the total number of proposals is at most $n^2$. The algorithm always terminates in $O(n^2)$ steps — polynomial, fast, no exponential search required.

Stability. The output is always stable: if student $s$ prefers program $p$ over their assigned match, then $p$ must have rejected $s$ at some round in favor of a better candidate — so $p$ does not prefer $s$ back. No blocking pair exists.

Optimality for proposers. The student-proposing version gives every student their best stable partner — the highest-ranked program they could be matched with in any stable matching. Programs get their worst stable partner. Swap the proposing side and the advantage flips.

Impossibility for both sides. A matching that is simultaneously best for students and best for programs cannot exist in general. Stability is the right compromise, but picking whose stable matching to use is a design choice with real stakes.

When ties appear. If preferences contain ties — "I'm equally happy with either" — then weak stability, super-stability and strong stability diverge, and computing the right variant can become NP-hard. The clean $O(n^2)$ world ends at strict preferences.

For the classic case of strict preferences and equal-sized sides, the problem is solved: Gale–Shapley is optimal and efficient. The hard questions begin the moment you allow ties, incomplete lists, or three-way matchings — echoing the same complexity barriers you find in P vs NP.

Stable matching is not a theoretical curiosity — it runs critical markets that touch millions of lives:

• Medical residencies: the US National Resident Matching Program (NRMP) has used a variant of Gale–Shapley since 1952, and adopted the student-optimal version formally in 1998. Over 40,000 positions are filled this way each year.
• School choice: New York City and Boston reformed their high-school and elementary-school assignment systems using deferred acceptance, replacing mechanisms that were manipulable and produced unstable outcomes.
• Kidney exchange: Alvin Roth extended matching theory to three-way and chain exchanges for incompatible donor–recipient pairs, helping thousands of patients receive transplants they could not obtain bilaterally.
• College admissions: many countries use centralized clearing-house algorithms directly derived from Gale–Shapley for university placement.
• Job markets: academic job markets in economics and other fields use match systems where the stability guarantee makes the result broadly accepted.

The unifying theme: whenever two sides have preferences over each other and a central authority must allocate, deferred acceptance gives a stable, strategy-proof-for-proposers result that markets without structure cannot guarantee. The ideas connect naturally to max matching and to the broader study of assignment problems.

Gale–Shapley deferred acceptance turns a messy social problem — "match these two groups so nobody defects" — into a clean $O(n^2)$ algorithm. Proposals flow, programs hold tentatively, rejections close doors one by one, and the process converges to a stable matching that no pair of participants would jointly choose to break.

The proposing side wins the best possible stable partner; the accepting side gets the worst. That asymmetry is not a flaw — it is an honest statement about what stability guarantees and what it does not. Choosing who proposes is a policy decision as much as a mathematical one.

Sixty years after the paper, the algorithm still runs the match that places doctors in hospitals every March. Simple, fast, stable — and Nobel-worthy.