# Joan Lindsay Orr


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