---
title: Stable Matching (Gale–Shapley)
module: Greedy Algorithms
moduleNumber: 7
lessonNumber: 5
order: 705
summary: |
  Two sides each rank the other; we want a matching with no **blocking pair** — no
  two participants who both prefer each other to their assigned partners. The
  **Gale–Shapley deferred-acceptance** algorithm has proposers propose in
  preference order while receivers tentatively hold the best offer so far. We prove
  it terminates in $\O(n^2)$ proposals, returns a **perfect** matching, and that
  the matching is **stable**. A sharper asymmetry follows: deferred acceptance is
  **proposer-optimal** and **receiver-pessimal**, the structural fact behind the
  residency match and school-choice systems.
topics: [Greedy]
sources:
  - book: Erickson
    ref: "Ch. — Stable Matching"
  - book: Skiena
    ref: "§ — Combinatorial Search & Heuristics"
  - book: CLRS
    ref: "Problem 16 — Greedy / Exchange Arguments"
practice:
  - title: 'Maximum Number of Accepted Invitations'
    slug: maximum-number-of-accepted-invitations
    difficulty: Medium
  - title: 'Process Tasks Using Servers'
    slug: process-tasks-using-servers
    difficulty: Medium
  - title: 'Campus Bikes'
    slug: campus-bikes
    difficulty: Medium
---

Every problem so far in this module optimized a number — the most jobs, the fewest
machines, the cheapest tree. Stable matching optimizes a relationship instead.
Given two groups, each member of one ranking the members of the other, we want to
pair them up so that the pairing _holds_: no two people, looking at their assigned
partners, would both rather abandon them for each other. A pairing with such a
defecting couple is unstable, and the couple is the proof of its instability.
Gale and Shapley proved that a stable pairing always exists
and that a simple greedy procedure — everyone proposes in order of
preference, and each recipient keeps only the best proposal seen so far — always
finds one. The procedure is greedy in spirit (each proposer tries its top
remaining choice; each receiver locally improves), and like the rest of the
module its correctness rests on an exchange-style argument. It is also deployed
at national scale: the medical residency match and many school-assignment
systems are this algorithm.

## The stable marriage problem

Fix two disjoint sets of equal size $n$, traditionally called the **proposers**
and the **receivers** (the older literature says "men" and "women"; we keep the
neutral roles). Each proposer ranks all $n$ receivers in a strict **preference
list**, and each receiver ranks all $n$ proposers. A **matching** $M$ is a
one-to-one pairing; it is **perfect** when everyone is matched.

> **Definition (Blocking pair).** Given a matching $M$, a pair $(p, r)$ of a
> proposer $p$ and receiver $r$ who are **not** matched to each other is a
> **blocking pair** if both prefer each other to their current partners:
> $p$ ranks $r$ above its partner $M(p)$, and $r$ ranks $p$ above its partner
> $M(r)$. Such a pair would defect, so $M$ does not hold together.

> **Definition (Stable matching).** A perfect matching $M$ is **stable** if it has
> no blocking pair. Every proposer-receiver pair that is _not_ matched has at
> least one member who prefers the partner $M$ already assigned them.

The definition forbids exactly this instability: two people who each outrank
the other's partner and would both defect. The algorithm must leave no such
pair.

$$
% caption: A blocking pair. $p$ prefers $r$ over its partner $M(p)$ and $r$ prefers $p$
%          over its partner $M(r)$, so $(p,r)$ would both defect — the matching $M$ (gray)
%          is unstable.
\begin{tikzpicture}[font=\small, >=stealth,
  per/.style={circle, draw, thick, minimum size=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[per] (p) at (0,2) {$p$};
  \node[per] (pp) at (0,0) {$p${'}};
  \node[per] (r) at (4,2) {$r$};
  \node[per] (rr) at (4,0) {$r${'}};
  % current matching M (gray): p--r', p'--r
  \draw[black, line width=2pt] (p) -- (rr);
  \draw[black, line width=2pt] (pp) -- (r);
  % blocking pair (red dashed): p and r prefer each other
  \draw[red!75!black, very thick, dashed] (p) -- (r);
  \node[font=\footnotesize, black, anchor=south] at (2,-1.15) {matching $M$};
  \node[red!75!black, font=\footnotesize, anchor=south] at (2,2.15) {blocking pair};
  \node[anchor=east, font=\footnotesize] at (-0.4,2) {\texttt{proposer}};
  \node[anchor=west, font=\footnotesize] at (4.4,2) {\texttt{receiver}};
\end{tikzpicture}
$$

Here $p$ is matched to $r'$ but prefers $r$, and $r$ is matched to $p'$ but
prefers $p$; the dashed pair $(p,r)$ blocks. Stability is a weak
requirement in one sense — it asks nothing about social welfare or total
happiness — and a strong one in another: a single blocking pair condemns the whole
matching. It is not obvious a stable matching always exists; for the closely
related _stable roommates_ problem (one set, everyone ranks everyone) it sometimes
does not. The two-sided structure is what guarantees existence.

::impl{algo="blocking_pair"}

## The Gale–Shapley algorithm

The algorithm is **deferred acceptance**. Proposers propose, but receivers never
finally commit: a receiver holds onto its best proposal so far and stays free to
trade up. Time runs in rounds; in each round some free proposer proposes to the
most-preferred receiver it has not yet proposed to. That receiver, comparing the
new offer to whatever it currently holds, keeps the better of the two and rejects
the other. A rejected proposer becomes free again and will later propose further
down its list. The deferral — receivers tentatively hold rather than accept — is
the entire idea; it is what lets an early, hasty pairing dissolve when a better
proposer arrives.

```algorithm
caption: $\textsc{Gale-Shapley}(P, R)$ — a stable matching from preference lists
number: 1
initialize every proposer and receiver as free
while some proposer $p$ is free and has not proposed to every receiver do
  $r \gets$ first receiver on $p$'s list to whom $p$ has not yet proposed
  if $r$ is free then
    match $p$ and $r$           // tentative: $r$ may still trade up
  else if $r$ prefers $p$ to its current partner $p'$ then
    free $p'$                    // $r$ trades up to $p$
    match $p$ and $r$
  else
    $r$ rejects $p$             // $p$ stays free, proposes lower next time
return the set of matched pairs
```

Two invariants make the whole proof go, and both are visible in the loop. First,
proposers descend their lists: a proposer only ever proposes to receivers strictly
worse (for it) than ones it has already been rejected by, so over its life a
proposer's offers move monotonically down. Second, receivers improve: once a
receiver is matched it stays matched forever, and the partner it holds only ever
gets better (for it), since it trades up and never down.

> **Invariant (Monotone in both directions).** Throughout the algorithm: (i) each
> proposer proposes in nonincreasing order of its own preference, never to the same
> receiver twice; and (ii) once matched, a receiver stays matched, and the sequence
> of partners it holds is strictly increasing in its own preference. A free
> proposer always has at least one un-proposed receiver remaining, or it would have
> been matched.

$$
% caption: Deferred acceptance, the trade-up step. Receiver $r$ tentatively holds $p'$ (left).
%          A better proposer $p$ arrives; since $r$ prefers $p$, it drops $p'$ (red, now free
%          again) and holds $p$ (green). A held partner only ever improves for $r$.
\begin{tikzpicture}[font=\small, >=stealth,
  per/.style={circle, draw, thick, minimum size=8mm, inner sep=1pt},
  hd/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % before
  \node[hd] at (0.75,2.5) {before};
  \node[per] (ap) at (0,2.0) {$p$};
  \node[per] (app) at (0,0.4) {$p${'}};
  \node[per] (ar) at (1.5,1.2) {$r$};
  \draw[acc, very thick] (app) -- (ar);
  \node[hd, anchor=north] at (0.75,0.1) {$r$ holds $p${'}};
  % arrow
  \node[hd] at (3.3,1.4) {$p$ proposes,};
  \node[hd] at (3.3,1.05) {$r$ prefers $p$};
  \draw[->, >=Stealth, acc] (2.45,0.7) -- (4.15,0.7);
  % after
  \node[hd] at (5.85,2.5) {after};
  \node[per] (bp) at (5.1,2.0) {$p$};
  \node[per] (bpp) at (5.1,0.4) {$p${'}};
  \node[per] (br) at (6.6,1.2) {$r$};
  \draw[grn, very thick] (bp) -- (br);
  \draw[red!75!black, thick, dashed] (bpp) -- (br);
  \node[hd, anchor=west, text=grn] at (7.0,1.7) {$r$ trades up to $p$};
  \node[hd, anchor=west, text=red!75!black] at (7.0,0.5) {$p${'} freed};
\end{tikzpicture}
$$

We run a small instance to see deferred acceptance trade up.

$$
% caption: An instance. Proposers $p_1,p_2,p_3$ and receivers $r_1,r_2,r_3$ with the
%          preference lists shown (left = top choice). Deferred acceptance produces the
%          stable matching $p_1{-}r_2,\ p_2{-}r_1,\ p_3{-}r_3$ (blue).
\begin{tikzpicture}[font=\small, >=stealth,
  per/.style={circle, draw, thick, minimum size=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  % proposers (left) with preference lists to the left
  \node[per] (p1) at (0,2.4) {$p_1$};
  \node[per] (p2) at (0,0.8) {$p_2$};
  \node[per] (p3) at (0,-0.8) {$p_3$};
  \node[anchor=east, font=\scriptsize, black] at (-0.6,2.4) {prefers $r_2$ then $r_1$ then $r_3$};
  \node[anchor=east, font=\scriptsize, black] at (-0.6,0.8) {prefers $r_1$ then $r_2$ then $r_3$};
  \node[anchor=east, font=\scriptsize, black] at (-0.6,-0.8) {prefers $r_2$ then $r_3$ then $r_1$};
  % receivers (right) with preference lists to the right
  \node[per] (r1) at (4,2.4) {$r_1$};
  \node[per] (r2) at (4,0.8) {$r_2$};
  \node[per] (r3) at (4,-0.8) {$r_3$};
  \node[anchor=west, font=\scriptsize, black] at (4.6,2.4) {prefers $p_2$ then $p_1$ then $p_3$};
  \node[anchor=west, font=\scriptsize, black] at (4.6,0.8) {prefers $p_1$ then $p_3$ then $p_2$};
  \node[anchor=west, font=\scriptsize, black] at (4.6,-0.8) {prefers $p_3$ then $p_1$ then $p_2$};
  % final stable matching (blue)
  \draw[acc, very thick] (p1) -- (r2);
  \draw[acc, very thick] (p2) -- (r1);
  \draw[acc, very thick] (p3) -- (r3);
\end{tikzpicture}
$$

A trace on this instance, one proposal per row:

| Proposal | $p$ proposes to | $r$ currently holds | $r$'s decision | Held pairs after |
| --- | --- | --- | --- | --- |
| 1 | $p_1 \to r_2$ | (free) | accept | $p_1r_2$ |
| 2 | $p_2 \to r_1$ | (free) | accept | $p_1r_2,\ p_2r_1$ |
| 3 | $p_3 \to r_2$ | $p_1$ | reject ($r_2$ prefers $p_1$) | $p_1r_2,\ p_2r_1$ |
| 4 | $p_3 \to r_3$ | (free) | accept | $p_1r_2,\ p_2r_1,\ p_3r_3$ |

$p_3$ leads with its top choice $r_2$, but $r_2$ already holds $p_1$ and ranks
$p_1$ above $p_3$, so $p_3$ is turned away and descends to $r_3$, which is free.
Everyone is now matched; no proposer was displaced, so the algorithm stops with
$p_1{-}r_2$, $p_2{-}r_1$, $p_3{-}r_3$. We will verify shortly that it is stable.

$$
% caption: The proposal trace, one column per step. Solid blue edges are tentative holds; the
%          red dashed edge in step~3 is $p_3$ proposing to $r_2$ and being rejected (it holds
%          $p_1$). Step~4 settles $p_3$ with $r_3$; the final holds are stable (green).
\begin{tikzpicture}[font=\scriptsize, >=stealth,
  per/.style={circle, draw, minimum size=5.5mm, inner sep=0pt, font=\scriptsize},
  hd/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  \foreach \col/\dx/\ttl in {1/0/{step 1}, 2/3.2/{step 2}, 3/6.4/{step 3}, 4/9.6/{step 4}} {
    \node[hd, anchor=south] at (\dx+0.75,2.55) {\ttl};
    \node[per] (P\col 1) at (\dx,2.0) {$p_1$};
    \node[per] (P\col 2) at (\dx,1.0) {$p_2$};
    \node[per] (P\col 3) at (\dx,0.0) {$p_3$};
    \node[per] (R\col 1) at (\dx+1.5,2.0) {$r_1$};
    \node[per] (R\col 2) at (\dx+1.5,1.0) {$r_2$};
    \node[per] (R\col 3) at (\dx+1.5,0.0) {$r_3$};
  }
  % step 1: p1-r2 held
  \draw[acc, very thick] (P11) -- (R12);
  % step 2: p1-r2, p2-r1 held
  \draw[acc, very thick] (P21) -- (R22);
  \draw[acc, very thick] (P22) -- (R21);
  % step 3: p3 proposes r2, rejected
  \draw[acc, very thick] (P31) -- (R32);
  \draw[acc, very thick] (P32) -- (R31);
  \draw[red!75!black, thick, dashed] (P33) -- (R32);
  % step 4: final, all green held
  \draw[grn, very thick] (P41) -- (R42);
  \draw[grn, very thick] (P42) -- (R41);
  \draw[grn, very thick] (P43) -- (R43);
  \node[hd, anchor=north, text=grn] at (10.35,-0.5) {stable};
\end{tikzpicture}
$$

::impl{algo="gale_shapley"}

## Termination and the $\O(n^2)$ bound

> **Theorem (Termination).** $\textsc{Gale-Shapley}$ halts after at most $n^2$
> proposals.

> **Proof.** Each iteration of the loop is one proposal, by some free proposer to a
> receiver it has not proposed to before (invariant (i): no proposer proposes to
> the same receiver twice). There are $n$ proposers and $n$ receivers, so the total
> number of distinct (proposer, receiver) proposals is at most $n \cdot n = n^2$.
> Each loop iteration consumes one of these once and for all, so the loop runs at
> most $n^2$ times and halts. $\qed$

The bound is tight up to the leading constant: an adversarial instance can force
about $n^2 - n + 1$ proposals. With the right data structures every step is $\O(1)$
— each proposer keeps a pointer to its next un-proposed receiver, and each
receiver answers "do I prefer $p$ to my current partner?" by a precomputed
rank table indexed in constant time — so the whole algorithm runs in $\O(n^2)$,
linear in the size of the input, since the preference lists themselves already
have $2n^2$ entries.

## Perfection: everyone gets matched

Termination alone could leave some proposer free. It does not.

> **Theorem (Perfect matching).** When $\textsc{Gale-Shapley}$ halts, every
> proposer and every receiver is matched.

> **Proof.** Suppose, for contradiction, that on termination some proposer $p$ is
> free. The loop ended, so $p$ must have proposed to **every** receiver (that is
> the only other way the loop exits with $p$ free). Take any receiver $r$. By
> invariant (ii), once a receiver receives its first proposal it is matched from
> then on, and $p$ proposed to $r$ at some point, so $r$ is matched at the end. As
> $r$ was arbitrary, **all** $n$ receivers are matched. But the matching is
> one-to-one, so $n$ matched receivers means $n$ matched proposers — every proposer
> is matched, contradicting that $p$ is free. Hence no proposer is left free, and
> since $|P| = |R| = n$ the matching is perfect. $\qed$

The key is invariant (ii): a receiver, once approached, never goes back to being
free. A free-at-the-end proposer must have approached everyone, which would have
matched everyone, leaving no room for it to be unmatched — a contradiction.

## Stability: no blocking pair survives

The central theorem. Termination and perfection only say we _have_ a perfect
matching; this says the one we have holds together.

> **Theorem (Stability).** The matching $M$ returned by $\textsc{Gale-Shapley}$ has
> no blocking pair, so it is stable.

> **Proof.** Take any pair $(p, r)$ not matched in $M$; we show it does not block.
> There are two cases by whether $p$ ever proposed to $r$.
>
> **Case 1: $p$ never proposed to $r$.** Proposers descend their lists (invariant
> (i)), and $p$ is matched in $M$ to whichever receiver it last proposed to. Since
> $p$ stopped before reaching $r$, the receiver $M(p)$ sits at or above $r$ on
> $p$'s list, i.e. $p$ prefers $M(p)$ to $r$ (or they coincide, excluded). So $p$
> is content; $(p,r)$ does not block.
>
> **Case 2: $p$ did propose to $r$ at some point.** Since $p$ and $r$ are not
> matched in $M$, $r$ must have rejected $p$ — either turning $p$ down on arrival
> for a partner it preferred, or later trading up away from $p$. Either way, by
> invariant (ii) the partner $r$ holds only improves over time, so $r$'s final
> partner $M(r)$ is at least as good (for $r$) as the proposer it preferred over
> $p$, hence strictly better than $p$. So $r$ prefers $M(r)$ to $p$; $(p,r)$ does
> not block.
>
> In both cases at least one of $p, r$ prefers its assigned partner, so $(p,r)$ is
> not a blocking pair. As $(p,r)$ was an arbitrary unmatched pair, $M$ has none and
> is stable. $\qed$

The two cases are exhaustive and complementary, and they split exactly along which
side is "satisfied." If $p$ never asked $r$, then $p$ is already with someone it
likes at least as much as $r$. If $p$ did ask and is not with $r$, then $r$
upgraded to someone it likes more than $p$. The figure below traces Case 2, the
subtler one: a rejection only ever moves a receiver up its list, so once it has
rejected $p$ it can never again prefer $p$ to what it holds.

$$
% caption: Stability, Case 2. After $r$ rejects $p$ for $p'$ (or trades up to $p'$), $r$'s
%          held partner only improves, so $r$ ends with $M(r)$ that it prefers to $p$. The
%          pair $(p,r)$ cannot block.
\begin{tikzpicture}[font=\small, >=stealth,
  per/.style={circle, draw, thick, minimum size=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[per] (p) at (0,1.4) {$p$};
  \node[per] (pp) at (0,-0.2) {$p${'}};
  \node[per] (r) at (4.2,0.6) {$r$};
  % p proposes, gets rejected (red dashed crossed)
  \draw[red!75!black, thick, dashed] (p) -- node[above, font=\scriptsize, pos=0.55] {rejected} (r);
  % r holds p' (and later only better)
  \draw[acc, very thick] (pp) -- (r);
  \node[acc, font=\scriptsize] at (1.9,-0.55) {held, then better};
  \node[anchor=west, font=\scriptsize, black, align=left] at (5.0,0.6)
    {$r$ prefers $p${'} to $p$,\\and only trades up,\\so $M(r)$ beats $p$.};
\end{tikzpicture}
$$

Together the three theorems show: deferred acceptance always
terminates, always returns a perfect matching, and that matching is always stable.
A stable matching exists for every instance, constructively.

## The asymmetry: proposer-optimal, receiver-pessimal

An instance can have many stable matchings, and the algorithm always lands on a
very specific one — the best possible for the proposing side, simultaneously the
worst possible for the receiving side. To state it, call a receiver $r$ a
**valid partner** of a proposer $p$ if some stable matching pairs them.

> **Definition (Valid partner).** $r$ is a **valid partner** of $p$ if there exists
> at least one stable matching in which $p$ is matched to $r$. The proposers'
> ranking restricted to their valid partners is what the next theorem optimizes.

::impl{algo="valid_partners"}

> **Theorem (Proposer-optimality).** $\textsc{Gale-Shapley}$ matches every proposer
> $p$ to its **best valid partner** — the highest receiver on $p$'s list among all
> receivers it is paired with in _any_ stable matching. This holds no matter which
> order free proposers are chosen.

$$
% caption: Valid-partner ladders. Each proposer's preference list runs top to bottom; the boxed
%          receivers are its valid partners (paired in some stable matching). Deferred acceptance
%          hands each proposer the topmost of its boxed entries (green) — its best valid partner.
\begin{tikzpicture}[font=\small,
  cell/.style={draw, minimum width=8mm, minimum height=6mm, font=\scriptsize, inner sep=0pt},
  vp/.style={draw=acc, thick, fill=acc!12, minimum width=8mm, minimum height=6mm, font=\scriptsize, inner sep=0pt},
  best/.style={draw=grn, thick, fill=grn!20, minimum width=8mm, minimum height=6mm, font=\scriptsize, inner sep=0pt},
  hd/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{grn}{HTML}{1A8A3B}
  % p1 list: best valid r1, then r2 valid, then r3 invalid
  \node[hd] at (0,2.7) {$p_1$ list};
  \node[best] at (0,2.0) {$r_1$};
  \node[vp]   at (0,1.3) {$r_2$};
  \node[cell] at (0,0.6) {$r_3$};
  % p2 list: r2 invalid top, r1 best valid, r3 valid
  \node[hd] at (2.0,2.7) {$p_2$ list};
  \node[cell] at (2.0,2.0) {$r_2$};
  \node[best] at (2.0,1.3) {$r_1$};
  \node[vp]   at (2.0,0.6) {$r_3$};
  % p3 list: best valid r3, then r1, then r2
  \node[hd] at (4.0,2.7) {$p_3$ list};
  \node[best] at (4.0,2.0) {$r_3$};
  \node[vp]   at (4.0,1.3) {$r_1$};
  \node[vp]   at (4.0,0.6) {$r_2$};
  % legend
  \node[best, anchor=west] at (5.6,2.0) {};
  \node[hd, anchor=west] at (6.2,2.0) {best valid partner (chosen)};
  \node[vp, anchor=west] at (5.6,1.3) {};
  \node[hd, anchor=west] at (6.2,1.3) {other valid partner};
  \node[cell, anchor=west] at (5.6,0.6) {};
  \node[hd, anchor=west] at (6.2,0.6) {never in a stable match};
\end{tikzpicture}
$$

> **Proof.** Suppose not. Among all runs, consider the first moment some proposer
> is rejected by a valid partner; say $r$ rejects $p$, and $r$ is a valid partner
> of $p$. The rejection means $r$ holds (or trades up to) some $p'$ it prefers to
> $p$. Because this is the _first_ rejection by a valid partner, $p'$ has not yet
> been rejected by any valid partner of its own, so $r$ is at least as good for
> $p'$ as $p'$'s best valid partner — in particular $p'$ prefers $r$ to any partner
> it could have in a stable matching where it is not with $r$.
>
> Now let $M'$ be a stable matching pairing $p$ with $r$ (one exists, as $r$ is
> valid for $p$). In $M'$, $p'$ is matched to someone other than $r$, and $p'$
> prefers $r$ to that partner (previous paragraph), while $r$ prefers $p'$ to $p$
> (the rejection). Then $(p', r)$ is a blocking pair in $M'$, contradicting that
> $M'$ is stable. So no proposer is ever rejected by a valid partner, and each
> ends with the best valid partner it could reach. $\qed$

The mirror statement is immediate.

> **Corollary (Receiver-pessimality).** In the matching $\textsc{Gale-Shapley}$
> returns, every receiver $r$ is matched to its **worst valid partner** — the
> lowest proposer on $r$'s list among all proposers it is paired with in any stable
> matching.

> **Proof.** Let $M$ be the proposer-optimal matching, and suppose some receiver
> $r$ has a stable matching $M'$ giving it a partner $p'$ it likes _less_ than its
> $M$-partner $p = M(r)$. By proposer-optimality, $p$'s best valid partner is $r$,
> so in $M'$ the proposer $p$ is matched to someone it likes no more than $r$,
> meaning $p$ prefers $r$ to its $M'$-partner. And $r$ prefers $p$ (its $M$-partner)
> to $p'$ (its $M'$-partner) by assumption. Then $(p, r)$ blocks $M'$, contradicting
> stability. So no receiver does better than its $M$-partner in any stable matching;
> $M$ gives each receiver its worst valid partner. $\qed$

So the side that does the proposing wins. The figure shows the gap: the same
instance admits two stable matchings, and proposer-optimal picks the one where the
proposers get their better valid partners and the receivers their worse.

$$
% caption: Two stable matchings of one instance. The proposer-optimal one (blue, returned
%          by deferred acceptance) gives each proposer its better valid partner; the
%          receiver-optimal one (gray) is what the receivers would get if they proposed.
\begin{tikzpicture}[font=\small, >=stealth,
  per/.style={circle, draw, thick, minimum size=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[per] (p1) at (0,1.4) {$p_1$};
  \node[per] (p2) at (0,-0.4) {$p_2$};
  \node[per] (r1) at (4,1.4) {$r_1$};
  \node[per] (r2) at (4,-0.4) {$r_2$};
  % proposer-optimal (blue): p1-r1, p2-r2
  \draw[acc, very thick] (p1) -- (r1);
  \draw[acc, very thick] (p2) -- (r2);
  % receiver-optimal (gray dashed): p1-r2, p2-r1
  \draw[black, line width=1.6pt, dashed] (p1) to[bend right=18] (r2);
  \draw[black, line width=1.6pt, dashed] (p2) to[bend left=18] (r1);
  \node[acc, font=\scriptsize, anchor=south] at (2,1.55) {proposer-optimal};
  \node[black, font=\scriptsize, anchor=north] at (2,-1.5) {receiver-optimal};
\end{tikzpicture}
$$

The asymmetry carries a design lesson: in deploying such a system you choose which
side proposes, and that choice is not neutral. It also has a strategic
consequence — a proposer can never gain by misreporting its
list, but a receiver sometimes can, a fact that shaped how the real matches were
engineered.

## Applications

A near-identical procedure assigns tens of
thousands of people every year.

**The residency match (NRMP).** Graduating medical students and residency programs
each rank the other, and the National Resident Matching Program computes a stable
assignment by deferred acceptance — historically program-proposing, later changed
to **applicant-proposing** precisely because of the optimality asymmetry above: the
side that proposes gets its best stable outcome, and reformers wanted that to be
the students. Programs admit several residents, so the real system is the
**hospitals/residents** generalization (receivers have capacity $> 1$), but the
mechanism, proofs, and stability guarantee carry over almost verbatim.

**School choice.** Many cities assign students to public schools with a
deferred-acceptance mechanism: students (or families) submit ranked lists, schools
have priorities and capacities, and the algorithm produces a stable, and under the
student-proposing version **strategy-proof for students**, assignment. The
practical appeal is the theory itself: stability means no student-school pair is
left mutually preferring each other over their assignments, so no family can
credibly complain that a swap was available and denied.

These deployments use every theorem above: existence (a stable
matching always exists, so the system can always output something), the $\O(n^2)$
bound scaled up (it runs fast at national size), and proposer-optimality (the
chosen proposing side provably gets its best stable outcome, which is why _who
proposes_ became a policy decision).

## Market design and the Nobel-winning legacy

Stable matching launched a whole field.

**A Nobel Prize in market design.** Gale and Shapley's 1962 paper "College
Admissions and the Stability of Marriage" was pure combinatorics, but its impact
came decades later.[^gs] Alvin Roth showed the National Resident Matching Program
had, since 1952, been running essentially the deferred-acceptance algorithm, and
that it was stability that kept the market from unraveling; he then
_redesigned_ the residency match and, with Elliott Peranson, the mechanisms behind
school-choice systems in New York and Boston. Roth and Shapley shared the 2012
Nobel Memorial Prize in Economics "for the theory of stable allocations and the
practice of market design."[^roth] The basis is this lesson's three theorems:
a stable matching always exists (so the system can always output one), it is
computable fast, and it is proposer-optimal (so _who proposes_ is a policy choice).

**Hospitals/residents and the rural-hospitals theorem.** Real matches are
_many-to-one_: each hospital admits several residents. The **hospitals/residents**
generalization keeps deferred acceptance almost verbatim (a hospital holds its best
$q$ applicants so far), and a structural fact emerges — the **rural
hospitals theorem** (Roth, 1986): the set of residents left unmatched, and the
number of positions each hospital fills, is _identical across every_ stable
matching.[^roth-rural] An under-subscribed rural hospital cannot improve its intake
by gaming which stable matching is chosen; if it is short-staffed in one, it is
short-staffed in all. This is why the policy fights are over _who proposes_ (the
optimality asymmetry) rather than over which stable matching to pick.

**Strategy-proofness and its limits.** Proposer-optimal deferred acceptance is
**strategy-proof for the proposing side** (Dubins & Freedman, 1981; Roth, 1982):
no proposer can gain by misreporting its list.[^dubins] But the receiving side
_can_ sometimes gain by lying, and no stable mechanism is strategy-proof for
_everyone_ at once — a limit that shapes every real deployment. A greedy
algorithm from a 1962 math paper became, essentially verbatim, national
infrastructure.

## Takeaways

- A **stable matching** is a perfect pairing of two equal-size sides with **no
  blocking pair** — no proposer and receiver who each prefer the other to their
  assigned partner.
- **Gale–Shapley deferred acceptance**: free proposers propose down their lists;
  each receiver tentatively holds its best offer so far and trades up, rejecting
  the rest. Two invariants drive everything — proposers' offers descend, receivers'
  held partners improve.
- It **terminates** in at most $n^2$ proposals (no proposer asks the same receiver
  twice), returns a **perfect** matching (an unmatched proposer would have asked
  everyone, matching everyone), and that matching is **stable** (any unmatched pair
  has a satisfied side).
- The output is **proposer-optimal** and **receiver-pessimal**: every proposer gets
  its best valid partner and every receiver its worst, independent of the order
  proposals are made.
- The mechanism runs the **residency match** and many **school-choice** systems;
  whichever side proposes provably gets its best stable outcome, making _who
  proposes_ a deliberate policy lever.

[^gs]: **Gale, D. & Shapley, L. S.** (1962), "College admissions and the stability of marriage," _American Mathematical Monthly_ 69(1), 9–15 — introduces the stable-marriage problem and the deferred-acceptance algorithm, proving a stable matching always exists.
[^roth]: **Roth, A. E.** (2002), "The economist as engineer: game theory, experimentation, and computation as tools for design economics," _Econometrica_ 70(4), 1341–1378; and the 2012 Sveriges Riksbank Prize in Economic Sciences awarded to Roth and Shapley for the theory of stable allocations and market design.
[^roth-rural]: **Roth, A. E.** (1986), "On the allocation of residents to rural hospitals: a general property of two-sided matching markets," _Econometrica_ 54(2), 425–427 — the rural-hospitals theorem: the set of matched agents is invariant across all stable matchings.
[^dubins]: **Dubins, L. E. & Freedman, D. A.** (1981), "Machiavelli and the Gale–Shapley algorithm," _American Mathematical Monthly_ 88(7), 485–494; and **Roth, A. E.** (1982), "The economics of matching: stability and incentives," _Mathematics of Operations Research_ 7(4), 617–628 — strategy-proofness of deferred acceptance for the proposing side, and the impossibility of full strategy-proofness for both sides.