Introduction

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.

Try It

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.

<!-- Deferred-acceptance (Gale-Shapley) demo: students propose, programs hold/reject -->
<p class="hint">Each student (left) has a ranked list of programs (right) shown below their name. Programs rank students too. Press <b>Step</b> to run one proposal, or <b>Run</b> to animate. Dashed lines = tentative holds; solid green = stable match.</p>
<div class="arena">
  <div class="col" id="col-students">
    <div class="col-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">Programs</div>
  </div>
</div>
<div class="status-area" id="status">Press Step or Run to start.</div>
<div class="log-area" id="log"></div>
<div class="btns">
  <button id="btn-step" type="button">Step</button>
  <button id="btn-run" type="button">Run</button>
  <button id="btn-reset" type="button" class="ghost">Reset</button>
</div>

/* Layout for the two-sided matching visualization */
* { 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; }

/* Gale-Shapley deferred-acceptance algorithm, step-by-step visualization */
const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));

/* The two sides of the matching market */
const STUDENTS = ['A','B','C','D'];
const PROGRAMS = ['W','X','Y','Z'];

/* Preference lists — each side ranks the other side strictly */
/* Student preference lists (most to least preferred) */
const SPREF = {
  A: ['X','W','Y','Z'],
  B: ['W','X','Z','Y'],
  C: ['X','Y','W','Z'],
  D: ['W','Z','X','Y']
};
/* Program preference lists (most to least preferred) */
const PPREF = {
  W: ['A','C','B','D'],
  X: ['B','A','D','C'],
  Y: ['C','D','A','B'],
  Z: ['D','B','C','A']
};

/* Algorithm state */
let nextProposal, holding, rejected, finalMatch, done;

function initState() {
  /* Reset all algorithm state to initial values */
  nextProposal = { A:0, B:0, C:0, D:0 };
  holding = { W:null, X:null, Y:null, Z:null };
  rejected = { A:[], B:[], C:[], D:[] };
  finalMatch = {};
  done = false;
}

/* DOM references */
const colStudents = document.getElementById('col-students');
const colPrograms = document.getElementById('col-programs');
const svg = document.getElementById('lines-svg');
const statusEl = document.getElementById('status');
const logEl = document.getElementById('log');

const nodeEls = {};

function buildNodes() {
  /* Build student and program node elements */
  colStudents.innerHTML = '<div class="col-label">Students</div>';
  colPrograms.innerHTML = '<div class="col-label">Programs</div>';

  STUDENTS.forEach(s => {
    const d = document.createElement('div');
    d.className = 'node student';
    d.id = 'node-' + s;
    d.textContent = s;
    const p = document.createElement('div');
    p.className = 'pref-list';
    p.textContent = SPREF[s].join(' > ');
    colStudents.appendChild(d);
    colStudents.appendChild(p);
    nodeEls[s] = d;
  });

  PROGRAMS.forEach(p => {
    const d = document.createElement('div');
    d.className = 'node program';
    d.id = 'node-' + p;
    d.textContent = p;
    const pl = document.createElement('div');
    pl.className = 'pref-list';
    pl.textContent = PPREF[p].join(' > ');
    colPrograms.appendChild(d);
    colPrograms.appendChild(pl);
    nodeEls[p] = d;
  });
}

function getY(id) {
  /* Get the vertical centre of a node relative to the SVG */
  const el = document.getElementById('node-' + id);
  const svgRect = svg.getBoundingClientRect();
  const elRect = el.getBoundingClientRect();
  return (elRect.top + elRect.height / 2) - svgRect.top;
}

function drawLines() {
  /* Redraw all connecting lines */
  svg.innerHTML = '';
  const svgRect = svg.getBoundingClientRect();
  const x1 = 0, x2 = svgRect.width || 160;

  /* Dashed lines for tentative holds */
  Object.entries(holding).forEach(([prog, stu]) => {
    if (!stu) return;
    const y1 = getY(stu), y2 = getY(prog);
    const line = document.createElementNS('http://www.w3.org/2000/svg','line');
    line.setAttribute('x1', x1); line.setAttribute('y1', y1);
    line.setAttribute('x2', x2); line.setAttribute('y2', y2);
    line.setAttribute('stroke', '#2563eb');
    line.setAttribute('stroke-width', '2');
    line.setAttribute('stroke-dasharray', '6 4');
    svg.appendChild(line);
  });

  /* Solid lines for the final stable matching */
  if (done) {
    Object.entries(finalMatch).forEach(([stu, prog]) => {
      const y1 = getY(stu), y2 = getY(prog);
      const line = document.createElementNS('http://www.w3.org/2000/svg','line');
      line.setAttribute('x1', x1); line.setAttribute('y1', y1);
      line.setAttribute('x2', x2); line.setAttribute('y2', y2);
      line.setAttribute('stroke', '#16a34a');
      line.setAttribute('stroke-width', '2.5');
      svg.appendChild(line);
    });
  }
}

function setStatus(msg, cls) {
  statusEl.textContent = msg;
  statusEl.className = 'status-area ' + (cls || '');
}

function setLog(msg) {
  logEl.textContent = msg;
}

/* Return the rank index of item in list (lower = more preferred) */
function rank(list, item) { return list.indexOf(item); }

function stepAlgorithm() {
  /* Advance one proposal in the Gale-Shapley algorithm */
  if (done) return;

  /* Find a student who still has proposals to make and is not held */
  const free = STUDENTS.filter(s => !Object.values(holding).includes(s) && nextProposal[s] < PROGRAMS.length);
  if (free.length === 0) {
    /* No free student with remaining proposals: algorithm has converged */
    done = true;
    STUDENTS.forEach(s => {
      const match = Object.entries(holding).find(([,v]) => v === s);
      if (match) finalMatch[s] = match[0];
    });
    Object.values(nodeEls).forEach(el => el.classList.remove('matched'));
    STUDENTS.forEach(s => { if (finalMatch[s]) { nodeEls[s].classList.add('matched'); nodeEls[finalMatch[s]].classList.add('matched'); } });
    setStatus('Stable matching found!', 'ok');
    setLog(i18nFmt('Final pairs: %pairs%', {
      pairs: STUDENTS.map(s => s + '→' + (finalMatch[s] || '?')).join(', ')
    }));
    document.getElementById('btn-step').disabled = true;
    document.getElementById('btn-run').disabled = true;
    drawLines();
    return;
  }

  const s = free[0];
  const p = SPREF[s][nextProposal[s]];
  nextProposal[s]++;

  const current = holding[p];
  let logMsg;

  if (current === null) {
    /* Program has no current hold: tentatively accept */
    holding[p] = s;
    logMsg = i18nFmt('%p% tentatively holds %s%.', { s, p });
  } else if (rank(PPREF[p], s) < rank(PPREF[p], current)) {
    /* New proposer is preferred: upgrade hold, reject previous */
    holding[p] = s;
    logMsg = i18nFmt('%p% upgrades: accepts %s%, rejects %old%.', { p, s, old: current });
    rejected[current].push(p);
  } else {
    /* Current hold is preferred: reject new proposer */
    rejected[s].push(p);
    logMsg = i18nFmt('%p% rejects %s% (keeps current hold).', { p, s });
  }

  setStatus(i18nFmt('Round %n%: %s% proposes to %p%.', {
    s,
    p,
    n: STUDENTS.reduce((acc, st) => acc + nextProposal[st], 0)
  }), 'info');
  setLog(logMsg);
  drawLines();
}

let running = false;

document.getElementById('btn-step').addEventListener('click', () => {
  if (!done) stepAlgorithm();
});

document.getElementById('btn-run').addEventListener('click', () => {
  if (running || done) return;
  running = true;
  document.getElementById('btn-run').disabled = true;
  const iv = setInterval(() => {
    stepAlgorithm();
    if (done) { clearInterval(iv); running = false; }
  }, 700);
});

document.getElementById('btn-reset').addEventListener('click', () => {
  running = false;
  initState();
  buildNodes();
  svg.innerHTML = '';
  setStatus('Press Step or Run to start.', '');
  setLog('');
  document.getElementById('btn-step').disabled = false;
  document.getElementById('btn-run').disabled = false;
});

initState();
buildNodes();
setStatus('Press Step or Run to start.', '');
Result
Console

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.

The Real Complexity

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 n2n^2. The algorithm always terminates in O(n2)O(n^2) steps — polynomial, fast, no exponential search required.

Stability. The output is always stable: if student ss prefers program pp over their assigned match, then pp must have rejected ss at some round in favor of a better candidate — so pp does not prefer ss 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(n2)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.

Where It Matters

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.

Conclusion

Gale–Shapley deferred acceptance turns a messy social problem — "match these two groups so nobody defects" — into a clean O(n2)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.

Share this article

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

Comments

Loading comments...

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