The Stable Marriage Problem and solution

The following post will be short but hopefully fun.

I Heard yesterday about a fun problem called the Stable Marriage Problem, and decided to write about it and about a famous algorithm that solves it. As always I will post some related code for the algorithm.

The Stable Marriage problem is describes in terms of N women and N men that we would like to match for the purpose of marriage. A stable marriage is one in which for every couple (W,M) there exists no other couple (W',M') for which both W would have liked to be married to M' and M' to W as well as W' would have wanted to be married to M and M to her. essentially if there exist two couples like that the marriage is considered unstable. The problem of course is not necessarily bounded to marriage and can be extended to other matching problems. 

A famous algorithm that solves this problem was devised in 60's of the previous century and is named after its creators: "The Gale-Shapely" algorithm.

The algorithm is iterative and works as followed:

Assume that we decide that the men are going to propose marriage to the women (it can obviously be the other way around). all men rank all of the women from most desired to least desired. All the women do the same. At each iteration of the algorithm, all the men propose to the women on the top of their list. if there exist women that received multiple proposals, those women choose among their proposals based on their own ranking list, and reject the others. At that point those women are tentatively engaged to the men (each to her corresponding man) that proposed to them and that they chose (based on their preference). At the next step, all the unmatched men propose to the women that are second in their list. Notice that it is possible that some of these women might be engaged already from the previous step. In such a case if a woman is already engaged and received a proposal from a man that is higher ranked in her list than the one she is engaged to, she cancels her engagement and reengages to the new man who just proposed to her. The man from the canceled engagement returns to the pool of men that are still unmatched. This algorithm will proceed until all men are matched with a women.

Now lets see some code (I chose the Python programming language this time, for the fun of it):

Some interesting insight (that I'm not going to prove here) about this algorithm:

1. The algorithm always terminates.

2. At the end of its execution each proposer (in this case Men) gets the optimal match that he can get in any stable marriage.

3. At the end of its execution each proposed (in this case Women) gets the least optimal match that she can get in any stable marriage. 

If you are further interested in proofs to the statements above I found this link: https://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf 

Now, that was fun and easy.