Theorem 1. (*Stable Marriage*)
Let and be two sets with an equal number of elements.
Suppose that each memeber of has a preference ranking of the elements
of and each member of has a preference ranking of the elements of
. (All of these rankings are linear orderings.) Then there is a
bijective map which is *stable* in the sense that there is
no and such that prefers to and
prefers to .

Proof. (*Gale-Shapley Algorithm*)
The theorem is proved by applying the following algorithm which runs iteratively
until each member of is matched with a member of . In the first round,
each member of "proposes" to their most-preferred member of and then
each member of which has received a proposal "accepts" their most-preferred
proposal. This results in a partially-defined one-to-one mapping
. Subsequently, with defined, each member of
outside the domain of "proposes" to the most preferred member of
which they have not already proposed to. Then each member of who received a
proposal accepts the proposal if either they were not in the range of
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 is matched.

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

To see that the algorithm is stable...