= Gale-Shapley algorithm
{c}
= Deferred acceptance algorithm
{synonym}
The <Gale-Shapley algorithm> constructs a <stable matching> by letting one side propose and the other hold its best offer so far. The word "deferred" is essential: a held proposal is tentative and can be replaced. <David Gale> and <Lloyd Shapley> presented this construction in their 1962 paper, https://iqua.ece.toronto.edu/baochun/ece1771f/papers/Gale-Shapley-1962.pdf[College Admissions and the Stability of Marriage], §3, printed pp. 12–13; §4 extends it to college quotas and unacceptable pairs.
For the one-partner <bipartite graph> model, designate $L$ as proposers and $R$ as receivers:
* Start with the empty <matching in a graph>. Each proposer keeps a pointer to its first untried acceptable partner.
* Choose an <unmatched vertex in a matching> $\ell\in L$ whose list is not exhausted. It proposes to its highest-ranked untried <neighbour of a vertex> $r$ and advances its pointer permanently.
* If $r$ holds nobody, it holds $\ell$. Otherwise $r$ compares $\ell$ with its currently held proposer, keeps the one it prefers, and rejects the other. A displaced proposer becomes unmatched and may propose again later.
* Stop when every unmatched proposer has exhausted its list. The held pairs are the output <matching in a graph>.
Held proposers wait; only unmatched proposers act. A receiver can replace its held partner, whereas a proposer never tries the same <edge> twice. Isolated <vertices> simply remain unmatched. These rules also describe incomplete acceptable lists and unequal sides without adding fictitious acceptable partners.
For the preference lists under <stable matching>, choose available proposers in <queue data structure> order, initially $A,B,C$, adding rejected proposers at the end. The proposals are $A\to X$, $B\to X$, $C\to Y$, $B\to Y$, $C\to Z$. At the fourth proposal, $Y$ replaces its held $C$ by $B$ because $B\succ_Y C$. This frees $C$ to try $Z$, producing $M_L$.
\Image[/stable-matching-deferred-acceptance-trace.png]
{title=Five proposals in the <Gale-Shapley algorithm>: Y replaces a tentative partner before the final <stable matching>}
Reverse the proposing side. Starting in the order $X,Y,Z$, the proposals are $X\to C$, $Y\to A$, $Z\to A$, $Z\to B$. Now $A$ rejects $Z$ because it already holds $Y$. The result is $M_R$. Thus the choice of proposing side can change the output even with <strict preferences> and complete lists.
Why does the procedure work? Each <edge> receives at most one proposal, so at most $|E|$ proposals occur. At all times, the held <edges> form a <matching in a graph>, and each receiver holds its favourite proposer among all proposals received. A receiver's held partner can only improve according to its <strict preference>. If a proposer prefers $r$ to its final partner, or ends unmatched while $r$ is acceptable, it must already have proposed to $r$. A rejection means $r$ then held someone better, and its final partner is at least as good. Such an <edge> cannot be a <blocking pair in stable matching>. This covers every possible <blocking pair in stable matching>, proving stability at termination.
With a <queue data structure> of unmatched proposers, a next-choice pointer for each list, and constant-time receiver-rank lookups, each proposal takes constant work. Using <Big O notation>, the <time complexity> is $O(|E|+|V|)$ including initialization, provided list construction and rank preprocessing also take $O(|E|+|V|)$. Edge-indexed ranks with cross-referenced list entries, or expected constant-time hash lookups, allow sparse storage proportional to $|E|+|V|$. Repeatedly scanning a receiver's preference list to compare offers would lose this bound. For complete lists with $n$ <vertices> per side, $|E|=n^2$ and the bound is $O(n^2)$. Initializing full $n\times n$ rank tables itself costs $\Theta(n^2)$ time and space, even when only a sparse <set> of pairs is acceptable.
The <Gale-Shapley algorithm> does more than establish existence: with <strict preferences>, its output is a <proposer-optimal stable matching>.<College Admissions and the Stability of Marriage by David Gale and Lloyd Shapley>[§5, printed p. 14, Theorem 2: applicant optimality and the rejection induction]{ref} It is also a <receiver-pessimal stable matching>, as proved below. Both qualifications compare partners across <stable matchings>.
Back to article page
