Proofs: Gale-Shapley algorithm

Gale-Shapley runs in O(n + m) time full

This proof shows: time.worst.

Let $n = |P| + |R|$ and let $m$ be the total length of all preference lists. Agents are indices, and each array access, comparison and stack operation costs $O(1)$ on the word RAM.

Preprocessing, line L1. For each entry $r$ at position $i$ on the list of $p$, append the pair $(p, i)$ to a bucket of $r$: $O(n + m)$. Then for each receiver $r$, write $\text{mark}[q] \leftarrow$ the position of $q$ on the list of $r$ for each $q$ on that list, read $\text{mark}[p]$ for each pair $(p, i)$ in the bucket of $r$ and store it at entry $i$ of the list of $p$ (or $-1$ if $p$ is not on the list of $r$), and reset the marks. Each list entry is touched a constant number of times, so this costs $O(n + m)$ and gives $\text{rank}_r(p)$ at the moment of the proposal in $O(1)$.

The main loop. By the termination argument of the correctness proof, there are at most $|P| + m$ passes, and each pass costs $O(1)$: a pop, one test on $\text{next}[p]$, one list access, one rank comparison and at most one push. Line L12 costs $O(n)$. The total time is $O(n + m)$.

Complete lists. Let $|P| = |R| = k$ with complete lists, so $m = 2k^2$ and the bound is $O(k^2)$. The number of proposals is at most $k^2 - k + 1$. Suppose $p$ proposes to the last receiver $r$ on its list. Then $p$ has been rejected by the other $k - 1$ receivers, and each of them holds someone from then on, by Claim 2 of the correctness proof. If $r$ had received a proposal before, all $k$ receivers would hold proposers, so all $k$ proposers would be held, while $p$ is free; so this is the first proposal to $r$. After it all $k$ receivers hold a proposer, so $F$ becomes empty and the run ends. Hence at most one proposer makes $k$ proposals, and the others make at most $k - 1$ each: in total at most $(k - 1)^2 + k = k^2 - k + 1$.

Space. The lists, the rank entries, the buckets, the arrays $\text{next}$, $\text{holder}$ and $\text{mark}$, and a stack of at most $|P|$ entries take $\Theta(n + m)$ space. $\blacksquare$

Gale-Shapley returns the proposer-optimal stable matching full

This proof shows: correctness, termination.

Fix an input: proposers $P$, receivers $R$, and strict lists without repeats. A pair $pr$ is acceptable if $r$ is on the list of $p$ and $p$ is on the list of $r$. Write $r >_p r'$ if $p$ ranks $r$ above $r'$, and $p >_r p'$ similarly. Say that $p$ proposes to $r$ when line L7 runs with these values, and that $r$ rejects $p$ when line L8 or L11 pushes $p$ after its proposal to $r$, or when line L10 pushes $p$ as the old holder of $r$.

Claim 1 (states). At the start of each pass of line L4, every proposer is in exactly one of three states: on the stack $F$ once, held by exactly one receiver, or done, popped in line L6 with its list exhausted. Every holder relation $\text{holder}[r] = p$ is an acceptable pair. Proof. Initially all proposers are on $F$ and nothing is held. A pass pops $p$ from $F$; line L6 makes it done; line L8 or L11 puts it back on $F$; line L9 makes it held by $r$, which held nobody; line L10 makes it held by $r$ and moves the old holder of $r$ from held to $F$. Lines L9 and L10 run only after line L8 has checked that $p$ is on the list of $r$, and $r$ is on the list of $p$ by line L7. $\square$

Claim 2 (receivers trade up). Once $\text{holder}[r] \ne \text{NIL}$, it stays so, and each new value is ranked higher by $r$ than the previous one. Proof. Only lines L9 and L10 change $\text{holder}[r]$; line L9 needs it to be NIL, and line L10 needs $\text{rank}_r(p) < \text{rank}_r(\text{holder}[r])$. $\square$

Claim 3 (proposals are remembered). If $p$ has proposed to $r$ and $pr$ is acceptable, then from that moment on $r$ holds $p$ or a proposer $p'$ with $p' >_r p$. Proof. Right after the proposal, $r$ holds $p$ (lines L9, L10) or a proposer it prefers to $p$ (line L11). By Claim 2, the holder of $r$ only improves later. $\square$

Claim 4 (proposals in order). Each proposer proposes to the receivers on its list in the order of the list, each at most once. Proof. Line L7 takes the entry at position $\text{next}[p]$ and increments it, and nothing else changes $\text{next}[p]$. $\square$

Termination. Each pass of the loop pops one entry of $F$. Entries are pushed once initially for each proposer, and afterwards only in lines L8, L10 and L11, at most once per proposal. By Claim 4 there are at most $m$ proposals, where $m$ is the total length of the lists of $P$. So there are at most $|P| + m$ passes.

The output is a stable matching. At the end $F$ is empty, so by Claim 1 every proposer is held by exactly one receiver or is done, and each receiver holds at most one proposer. So the pairs returned in line L12 form a matching $M$ of acceptable pairs. Let $pr$ be an acceptable pair not in $M$, and suppose $p$ is single in $M$ or $r >_p M(p)$. If $p$ is single, it is done and has proposed to every receiver on its list, including $r$. If $p$ is matched, $M(p)$ is the receiver of its last proposal, which comes after $r$ on its list, so by Claim 4 $p$ proposed to $r$ before. In both cases Claim 3 says that $r$ holds at the end a proposer $p' \ne p$ with $p' >_r p$. So $r$ is not single and prefers its partner, and $pr$ does not block $M$.

Claim 5 (no stable partner rejects). Call $r$ a stable partner of $p$ if $pr$ belongs to some stable matching. In every run, no proposer is rejected by one of its stable partners. Proof. Suppose not, and consider the first rejection in the run of some $p$ by a stable partner $r$; let $S$ be a stable matching with $pr \in S$. The pair is acceptable, so the rejection happens in line L10 or L11, and at that moment $r$ holds or takes a proposer $p'$ with $p' >_r p$, and $p'$ has proposed to $r$. By Claim 4, $p'$ has proposed to, and been rejected by, every receiver it ranks above $r$, and all these rejections happened earlier. By the choice of the first rejection, none of these receivers is a stable partner of $p'$, so $S(p')$ is not one of them. Also $S(p') \ne r$ because $S(r) = p \ne p'$. So in $S$ the proposer $p'$ is single or has a partner it ranks below $r$; and $r$ has partner $p$, which it ranks below $p'$. The pair $p'r$ is acceptable, because $p'$ proposed to $r$ and $r$ preferred $p'$ to an acceptable proposer, so $p'$ is on its list. Hence $p'r$ blocks $S$, a contradiction. $\square$

Proposer-optimality. For each $p$, let $\text{best}(p)$ be the stable partner of $p$ that $p$ ranks highest, if one exists. By Claim 5 and Claim 4, $p$ is never rejected by $\text{best}(p)$, so it never proposes beyond $\text{best}(p)$, and its final partner, if any, is $\text{best}(p)$ or ranked higher. The output $M$ is stable, so $M(p)$, if it exists, is a stable partner of $p$, hence ranked at most as high as $\text{best}(p)$. So $M(p) = \text{best}(p)$. If $p$ has no stable partner, then $M(p)$ cannot exist, and $p$ is single. So $M$ is determined by the input alone, whatever the order of the stack.

Receiver-pessimality. Let $S$ be stable and $r$ a receiver with $M(r) = p$. If $r$ is single in $S$ or $p >_r S(r)$, then since $S(p) \ne r$ and $r = \text{best}(p)$, the proposer $p$ is single in $S$ or ranks $r$ above $S(p)$, so the acceptable pair $pr$ blocks $S$, a contradiction. Hence every receiver matched in $M$ has in $S$ a partner it ranks at least as high as $M(r)$. $\blacksquare$