John Lindsay Orr

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