Stable Matching

by Valkryst

The following post is derived from notes taken while reading through this textbook.

Assumptions and Statements:

Assume that we have two sets with n people in each set.

Men, M = {m1, ... , mn}

Women, W = {w1, ... ,wn}

We want to create n pairs (groups) of men and women where each man and each woman is in exactly one pair.

Before we can create the groups we tell each man to rank each woman from most desirable to least desirable. We also tell each woman to do the same for each man.

The men can only propose to the women one after the other. So the first man proposes to the first woman, then the second woman, etc...

A pair is perfect if, and only if, both the man and woman have each other as their most desired partner.

A pair is stable if, and only if, it is impossible for the proposing partner to propose to a partner who they have ranked more desirable than their current partner.


Example:

Assume that we have two men (m1, m2) and two women (w1, w2) with the following rankings.

m1 prefers w1 to w2

m2 prefers w1 to w2

w1 prefers m1 to m2

w2 prefers m1 to m2

Now I highly suggest that you draw this out on paper if you can't visualize the choices. You will eventually notice that the only two ways to group up the men and women are as follows.

Way #1:

(m1, w1) and (m2, w2)

Way #2:

(m1, w2) and (m2, w1)

You may be thinking that both of these ways don't work. Well, you're somewhat correct.

The second way is incorrect because the first man (m1) is supposed to be grouped first and, if he did go first, he would have picked the most desirable woman (w1) according to his rankings. Therefore it's impossible for the second man (m2) to match with the first woman (w1).

The first way, unlike the second way, is correct even though the second man and second woman don't have each other ranked as their first choice.

You might still be confused at this point, I sure was when I first tried to wrap my mind around the solution.

The reason why the first way works is because the first man is already with his most desired partner, so he won't separate from her for another woman. Because of this, the second man is unable to attain his first choice, so he has to go with the only remaining woman.

Think about this for a while and try to reason it out in your mind. It may take a while, but this does make sense.

The Gale-Shapley Algorithm:

If my written explanation of how our basic stable matching works isn't enough, then here is a pseudocode version of the algorithm.

All credits for this psedudocode example go to the authors of this textbook.

    
        Initially all m and 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 highost-ranked woman in m's preference list to whom 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 froe
                Else w prefers in to m'
                    (m, w) becomsi engaged
                    m' becomes free
                Endif
            Endif
        Endwhile

        Return the set of engaged pairs
    

Algorithm Quirk:

The one quirk with the Gale-Shapley algorithm above is that it favours the proposing gender.

If the men propose to the women, then the men have a higher chance of being matched with a woman that they highly desire, but the women will have a higher chance of being matched with a man that they desire less than another man.

If the women propose to the men, then the women have a higher chance of being matched with a man that they highly desire, but the men will have a higher chance of being matched with a woman that they desire less than another woman.