Chapter 1

The stable matching problem/algorithm attempts to find a stable matching (pairing) between individuals of two sets of the same size given a ranking of preferences for each individual within the set. A matching is a mapping from the elements of one set to the elements of the other set.

The matching is said to be unstable if:
a) There is an element A of the first matched set which prefers some given element B of the second matched set over the element to which A is already matched, and
b) B also prefers A over the element to which B is already matched

The matching is said to be stable if:
There does not exist any match (A, B) in which both A and/or B would be individually better off than they are with their current match.

The most useful applications of this problem include hospital-resident assignments, roommate assignments, and even in sorority rush processes. Although the stable marriage problem is useful in the field of computer science, it is not all that practical in the real world. It has been proven that whomever (man or woman) proposes will end up with their best possible match, and whomever is proposed to will end up with their worst possible match.

There are several truths regarding the stable marriage problem that can all be verified by proof by contradiction.
Note that w represents a woman and m represents a man.

1.1 w remains engaged from the point at which she receives her first proposal; and the sequence of partners to which she is engaged gets better and better.

1.2  The sequence of women to whom m proposes gets worse and worse.
1.3  The G-S (Gale-Shapley) algorithm terminates after at most n<sup>2</sup> iterations of the While loop.
1.4  If m is free at some point in the execution of the algorithm, then there is a woman to whom he has not yet proposed.
1.5  The set S returned at termination is a perfect matching.
1.6  Consider an execution of the G-S algorithm that returns a set of pairs S. The set S is a stable matching.

A sketch of the Gale-Shapley algorithm follows:

Initially all m in M and w in W are free
While there is a man m who is free and hasn’t proposed to
every woman
    Choose such a man m
    Let w be the highest-ranked woman in m’s preference list
        to whom m has not yet proposed
    If w is free then
        (m, w) become engaged
    Else w is currently engaged to m’
        If w prefers m’ to m then
            m remains free
        Else w prefers m to m’
            (m, w) become engaged
            m' becomes free
        Endif
    Endif
Endwhile
Return the set S of engaged pairs

My main question while reading this section was, how practical is the stable marriage problem in the real world, if at all? This question was answered by the end of the section, but I am still curious about other applications of the stable matching problem. I thought this section was relatively easy to read and understand after the lecture, but I think if I had read it before the lecture I would have been pretty confused. I found this section to be about a 7 in terms of interestingness on a scale of one to ten because of all the possible real world applications. I'm not sure why it was necessary to prove each of the six lemmas separately in order to understand the problem itself, but this process will probably become more helpful as the algorithms and proofs become more complicated.