Posted by: adam soom | September 14, 2010

Lect 6: Gale-Shapley Algorithm

Lecture Overview

In Monday’s lecture we continued our discussion of the Stable Marriage Problem. We completed our formulation of the problem, and stepped through the design of an algorithm to solve it. Group discussions were tailored to illustrate the sorts of questions and cases one must ponder during the algorithm design process. Finally, we were presented with a formal definition of the Gale-Shapley algorithm, followed by an example run. We have already been told that this algorithm incorporates all of the intuition necessary to solve the problem, and will prove this in subsequent lectures.

Formulation

Our formulation of the Stable Marriage Problem concluded with a quick review of instability. Questions had arisen regarding how a matching can be considered stable if it contains a pair in which a person is matched with someone low down on, or for that matter, at the bottom of their preference list. The explanation for this comes from a combination of two previously-discussed assumptions:

• All $m\in M$ and all $w\in W$ must get married
• All proposals are by one of the genders. The textbook uses men, our in-class examples use women.

These two assumptions result in the phenomenon described on page 12 of the textbook:

“for any input, the side that does the proposing…ends up with the best possible stable matching (from their perspective), while the side that does not do the proposing correspondingly ends up with the worst possible stable matching.”

Note the use of the word stable. It should be clear that the one-sided nature of the proposal system does not affect the stability of the final matching $S$, yet serves to greatly simplify our comprehension of the problem.

Designing an algorithm

Last time we briefly outlined a ‘naive’ algorithm for solving the Stable Marriage Problem. It involved examining all perfect matchings one by one, and terminating if and when one of them turns out to be stable. A brute-force algorithm such as this will indeed find a stable matching if one exists, but will not do so in any sort of reasonable time as $n$ becomes sufficiently large. We need to design an algorithm that incorporates a higher level of intuition.

We considered some of the main ideas behind G-S as a way to begin our thought process for the design of our algorithm. Each subsequent design step was preceded by a group discussion, which allowed us to better define the different “situations” (cases) one is likely to encounter throughout a given run, and what sorts of decisions will need to be made.

Initially, we assume that no men or women are paired; all are free. The ultimate goal is to convert all $n$ men and $n$ women to matched pairs.

GROUP DISCUSSION
: Keeping in mind that it is the women who are doing the proposing, we were asked to consider a woman $w$, who is the first woman to propose to anyone. Who should she propose to?

The most sensible answer comes from the fact that we know all of the women have ranked all the men, and that we know no proposals have been made. We therefore know that the man most preferred by $w$ (call him $m$) must be free, and she should propose to him.

GROUP DISCUSSION: We were asked to consider $m$, the man who just received the proposal from $w$. What should he do?

Three options were discussed. $m$ could say:

• Yes – but must consider what would happen should someone more preferable come along in the future
• No – but must consider what would happen should no one else propose
• Maybe – at which point $m$ and $w$ would become engaged

I personally find having three options to be somewhat confusing and ultimately unnecessary. It is much easier to understand this particular decision if I consider $m$ as having only two options, ‘yes’ and ‘no’. I must simply remember that the engagement, like those in real life, can be broken off in favor of engagement to another, and that no two people should be considered married until the output of the final matching $S$.

Even though we know $m$ has a preference list ranking all of the women, he actually has no options to weigh, since this is the first proposal that has been made. He should say ‘yes’.

GROUP DISCUSSION: We were asked to consider the middle of a given run, at which point:

• Some pairs are engaged
• Remaining $m$ and $w$ are free
• As before, only free women can propose

If a woman $w'$ is free at this point, who should she propose to?

To say $w'$ should propose to the man at the top of her preference list (as $w$ did at the start of the run) is not entirely correct. She may have already proposed to him earlier in the run.

Two cases arise:

• If he said ‘no’ earlier, this means he was engaged to someone more preferable. Now, he is either still engaged to that person, or is engaged to someone even more preferable. He will therefore say ‘no’ now.
• If he said ‘yes’ earlier, this means they were engaged but he must have since broken off the engagement in favor of another, and will therefore say ‘no’ this time.

The idea of “re-proposing” to someone is clearly pointless. $w'$ should propose to the highest-ranked man to whom she has not already proposed. Call him $m'$.

GROUP DISCUSSION
: We were asked to consider $m'$, who just received a proposal from $w'$ in the middle of a run. What should $m'$ do?

Three cases arise:

• If $m'$ is free, he has no options to weigh, and should simply say ‘yes’, as $m$ did earlier.
• If $m'$ is currently engaged to someone else (call her $w''$) but would prefer to be with $w'$, he should say ‘yes’, at which point $m'$ and $w'$ become engaged, and $w''$ becomes free.
• If $m'$ is currently engaged to $w''$ and prefers her over $w'$, he should say ‘no’. He will remain engaged to $w''$ and $w'$ will remain free.

We were presented with a formal definition of G-S, which I won’t bother reproducing here. It encapsulates the decision-making process I described above, repeating steps as necessary until everyone is engaged, at which point the algorithm outputs the matching $S$ and terminates.

A sample run was examined, illustrating examples of the proposal-answer process, showing engagements being formed and broken and, as expected, terminating with everyone being engaged. It was also noted how as engagements are formed and broken, a woman may go back and forth between being engaged and being free, but any given man, once engaged, remains engaged until the end of the run, though his partner may change.

• Will the final matching $S$ always be a perfect matching? More importantly, will it always be a stable matching?