# John Lindsay Orr

$\newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\H}{\mathcal{H}} \newcommand{\e}{\epsilon} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}}$

Theorem 1. (Stable Marriage) Let $A$ and $B$ be two sets with an equal number of elements. Suppose that each memeber of $A$ has a preference ranking of the elements of $B$ and each member of $B$ has a preference ranking of the elements of $A$. (All of these rankings are linear orderings.) Then there is a bijective map $A\rightarrow B$ which is stable in the sense that there is no $a\in A$ and $b\in B$ such that $a$ prefers $b$ to $f(a)$ and $b$ prefers $a$ to $f^{-1}(b)$.

Proof. (Gale-Shapley Algorithm) The theorem is proved by applying the following algorithm which runs iteratively until each member of $A$ is matched with a member of $B$. In the first round, each member of $A$ "proposes" to their most-preferred member of $B$ and then each member of $B$ which has received a proposal "accepts" their most-preferred proposal. This results in a partially-defined one-to-one mapping $f_1: A\rightarrow B$. Subsequently, with $f_{n-1}$ defined, each member of $A$ outside the domain of $f_{n-1}$ "proposes" to the most preferred member of $B$ which they have not already proposed to. Then each member of $B$ who received a proposal accepts the proposal if either they were not in the range of $f_{n-1}$ or if they prefer the originator of the proposal to their current matching, in which case their previous matching is discarded. The process continues until every member of $A$ is matched.

To see that that algorithm must terminate, observe first that once an element of $B$ receives a proposal, it is guaranteed that it will subsequently always be matched with some element of $A$. Also, for a fixed $a\in A$ and $b\in B$, eventually either $a$ will be permentantly matched with a member of $B$ which is preferred to $b$, or else $a$ will propose of $b$. Thus eventually at least one of $a$ or $b$ must be permenantly matched. Since the matching is one to one, it follows that all of $A$ and $B$ are eventually matched.

To see that the algorithm is stable...