Joan Lindsay Orr

\( \newcommand{\CC}{\mathbb{C}} \newcommand{\NN}{\mathbb{N}} \newcommand{\RR}{\mathbb{R}} \newcommand{\TT}{\mathbb{T}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\H}{\mathcal{H}} \newcommand{\e}{\epsilon} \newcommand{\x}{\mathbf{x}} \newcommand{\y}{\mathbf{y}} \)

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