Posted by: andrewglowacki | September 14, 2010

## Lect 6: Gale-Shapley Algorithm

(Guest post by Andrew Glowacki)

In class today, we continued on with the Stable Marriage Problem by introducing the Gale-Shapley Algorithm.  First, and for the majority of the time, we brainstormed as a class and with our groups what the algorithm needed to solve the problem. Then at the end of class, we were shown the exact wording and specification of the Gale-Shapley Algorithm itself.

In the beginning of class, it was noted that we brainstormed a brute force algorithm that runs in n! * * latex n^3\$ * time from last class.  We were told that the Gale-Shapley Algorithm on the other hand runs in n^3 time which is much more efficient and practical.  Although our brute force algorithm finds all the possible stable matchings, a smart algorithm is better than a dumb algorithm.

It was decided that we would be introduced to the Gale-Shapley Algorithm by building our way up to it. The main idea, and problem we were solving with this is we needed to find a way to match men and women in a stable fashion.  This objective was used as our catalyst for the algorithm development, however it was strictly noted that mathematical algorithms such as this remain relevant without specific group types such as men and women.

The following is what we came up with for our algorithm brainstorming.
-Initially all men and women are free.
-All proposals will be made by women.
We started with the base case:
Let w be a free woman.
w proposes first ->…
From here, we discussed who she should propose to in our groups. The class came up with the man highest in her preference list.
… -> to the man highest in her preference list.
From here, in the base case, it was noted that the man, m is free, and he had 2 options: to say yes or no.  The problems with these that  we solved were: if he says yes, what if someone better comes later, and if he says no, what if nobody comes later.  The 3rd option that we decided on, and used is that they become engaged.

After this formulation, we were told that we had to imagine the algorithm went on for a while.  Some pairs are now engaged, some pairs are free, and women who are free can still propose. This was the start of our recursive/general case.
We determined, w’ will propose because w’ is free.  We discussed in our groups who she would propose to, deciding it would be the highest preferred man m’ in her list that she hasn’t yet proposed to.
We now had to decided what m’ had to do in 2 cases.
(1) The first being: m’ is free, which we decided w’ and m’ would become engaged (m’, w’).
(2) The second being: m’ is engaged to another woman w.  We found there were 2 sub cases with this case.
(2-1) The first sub case was that m’ prefers w over w’ in his preference list, so m’ and w stay engaged, while w’ remains free.
(2-2) The second sub case was the opposite, that m’ prefers w’ over w. Now, m’ gets engaged to w’, and w becomes free again.

This recursive form would be repeated until everyone was engaged.

After all of this brainstorming we were shown the exact wording of the Gale-Shapley as follows.

Initailly all men and women are free.
While there exists a free women who can propose:
Let w be such a woman and m be the best man she has not proposed to.
w proposes to m
If m is free
(m, w) get engaged.
Else (m, w’) are engaged
if m prefers w’ to w
w remains free
Else
(m, w) get engaged and w’ is free
End While
Output engaged pairs as final output.

We concluded class by applying this new algorithm to the Firefly cast.

One question left from this class and one which will be answered next class is ‘how do we know this algorithm works?,’ or that it even ends.  Next class we will be proving this algorithm’s operation.