Forming Stable Marriages: Gale-Shapley Algorithm

Imagine you work in a marriage-making company where you have to match people together in such a way that they are most compatible with their matched partners and will not switch if given a chance. Here, switching is possible only when both men and women agree to be paired together. (If it’s one-sided, it won’t work). Such a match is called a stable match where partners stick together. Remember, here we are considering a match between man and woman only, same-gender matches are not permitted in this case and there are equal number of man and woman.

You will probably ask all the men and women to choose a partner of their choice. But their choices will collide and multiple inconsistencies can arise. What if a man ‘m’ wants to marry a woman ‘w’ who is in turn interested in some other man ‘m`’. Here ‘m`’ is interested in some other women and not ‘w’. Whereas that woman can be interested in some other man. How will you make sure that everyone is happy and a stable matching is formed?

Maybe it is not possible in all the cases that all the men and women are paired up with the partner of their highest preference. It is better if they all create a list of preferences where they add partners in non-increasing order of preference. Suppose ‘m’ does not gets paired with ‘w’ then now he can choose other women ‘p’ who is next in his preference.

If we ask both men and women to create such a list, the next question is who will propose first? Gale-Shapley came up with an algorithm where either men or women will propose first. Using this algorithm, we can find one or more stable matches.

Gale-Shapley Algorithm

According to the Gale-shapely Algorithm, each man and woman create a list of their preference containing their desirable partners in non-increasing order. And for each instance of finding the stable match, we decide if we want the men or the women to propose first. If the men propose to women, the women can either accept or reject the proposal. She will accept the proposal if she is single and free but rejects it if she is engaged with a man who is higher in her preference list. We give every single man a chance to propose to a woman next on his list until all the men get engaged. The women can reject partners multiple times, break the engagement and move on with the next desirable partner. This algorithm gives us a stable match where both men and women are satisfied with their match and there is no instability.

Let us now slowly go through the algorithm using an example of two men m1, m2, and two women w1, and w2.

The preferences list of these men and women is listed below:

m1 = {w1, w2}

m2 = {w1, w2}

w1 = {m2, m1}

w2 = {m2, m1}

First of all, m1 will propose to w1. w1 will agree as no one has yet proposed to her and she is free. Next, m2 will propose to w1. Now, w1 has two choices: either she stays with her current partner or leaves her current partner. She will make the decision by comparing the position of m1 and m2 in her preference list. As she prefers m2 over m1, she breaks off her engagement with m1 and gets engaged to m2. Hence m1 is now a free man. He will again propose the woman next on his list which is w2. w2 is also free and she accepts the proposal. As there is no free man left in the list, the algorithm will now stop giving as the stable matching pair of {m1,w2} and {m2,w1}.

Remember that stable matching is not always unique. We made the men propose first and formed the pairs, but what if we make the women propose first? It is possible that we then come up with a different stable matching. So, let us pick a random woman from the list of women and make her propose to the man of her choice. (To prove that the order in which men and women are proposing doesn’t matter, you can try forming different combinations. As long as the same gender starts, the result will be the same. ) Let us now begin with w2 and she proposes to m1. m1 now has the authority to accept or reject. m1 is currently single and he gladly accepts. We now ask w1 to propose and she proposes m2. w2 will also propose to m2 and he will choose w1 over w2 and will stay with his current partner. Hence, w2 will now propose to the next man in her list, i.e m1 and they get paired together. As all the women are now engaged the algorithm will stop and give us the pairs {m1, w2} and {m2,w1}. In this case, the stable matching is the same when the women propose or when men propose. This is possible to happen but does not happen always. Most of the time, when the preferences of men and women differ, there are different stable matching possible.

Stable Matching: Now that we have gone through the Algorithm and formed a stable matching pair, you must be thinking — w2 prefers m2 over m1. Won’t she try to move out of this engagement and be with m2? Well, Yes. She will want that but m2 will not want that because he is already engaged to a woman of higher preference. As the feeling is not mutual, the engagements remain in place. This is called stable matching.

Instabilities: Now, let us try to prove our algorithm by contradiction. Say, there exists an instability where m1 and w1 prefer each other over their current partners.

But w1 prefers m2 according to her preference list so this means she was either not proposed by m2 yet, or she rejected m2 to be with m1. As w1 is currently engaged with m2, this is a CONTRADICTION! She will not reject m2 for m1 and she is already engaged to m2 so she is also not free. Hence, she cannot be engaged with m1 and this instability is invalid. This proved that our Algorithm is valid and is giving us stable matches. So marriage-making company can definitely use it.

One thing to keep in mind is that when men propose they end up with their best valid partners and when women propose they end up with their best valid partners. Whereas, when men propose the women will end up with their worst valid partners, and vice versa for the men.

Do you have a question — What are valid partners?

Valid partners: According to the Gale-Shapley algorithm, there can be multiple stable matches for a single set. For example, when men propose then the stable matching pairs can be different than when women propose. Hence in such cases, a single man or woman can be paired with different people in both matchings. Both of these partners are valid partners. Whereas, a partner which is the highest preferred by them in their list of valid partners, is their best valid partner.

This brings us to the proof that if men propose and women get to choose, then why do men end up with their best valid partners and not the women?

Men get paired with best valid partners: To prove this claim, we try to contradict it. Suppose there exists a stable match S where m and w are paired together. Here, w is the best valid partner of m. But can there exist a stable match S’ where m is not paired with his best valid match w? Consider that in S’, m was the first man to get rejected by his valid partner w. Let us assume that it is possible and try to prove it wrong.

If m is not paired with w, in the case S’ then it means that w has rejected m for some other man m’. And w is paired with m’. But with whom is m’ paired within the initial match S? Let’s call the women w’. If m was the first man getting rejected in S’, then it means that m’ was not rejected and w prefers m’ over m. Also, that m’ proposed w before w’ and he prefers w over w’. But if m is paired with w, in the match S, then it means that w prefers m over m’, which is a contradiction. Hence, S’ is not a stable match. This proves that men get paired with their best valid partners.

Women get paired with worst valid partners: To prove this claim, we assume that there exists a matching S where m and w are paired together and a matching S’ where w is paired with m’, where m’ is higher in the preference list of w, as compared to m. Hence, here S is the match where w is paired with her worst valid partner. If we assume that S’ is also a valid match, then S will not be valid as w will prefer m’ over m and m can never be paired with w. Hence we prove by contradiction that women will always be paired with their worst valid partners when the men propose.

We can use this algorithm in several other areas where we want an “n to n” mapping, feel free to come up with new examples and challenges and post them in the comments!

Fight On!