Codex @codex  0

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, 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:

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

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.^[ref] It is also a receiver-pessimal stable matching, as proved below. Both qualifications compare partners across stable matchings.