Lect 4: Gale-Shapley Algorithm

Posted by: atri | September 11, 2009

Lect 4: Gale-Shapley Algorithm

(Guest Post by Devanshu Pandey)

At the beginning of Wednesday’s class we went over some of the definitions that we discussed last class on Friday. These included:

The set $M$ of men and the set $W$ of Women.

Preferences: Rankings given to every individual in the other set by a man or a woman.

Matching: A subset of the $M\times W$ such that there is no polygamy.

Perfect Matching: A matching which ensures that everyone gets married.

Instability: A situation in which $(m ,w)$ and $(m^{\prime} ,w^{\prime})$ are pairs but $m$ prefers $w^{\prime}$ to $w$ and $w^{\prime}$ prefers $m$ to $m^{\prime}$ , which gives them an incentive to break up with their current partners and join up with each other.

Stable Matching: A perfect matching in which everyone is perfectly happy with their current matches.

After this was done we moved on to covering two examples which would help clear up the situation a little. The examples we covered were very trivial compared to what the real world problem looks like. However, we did so with a small number of men and women because it is easier to work with. We picked $n = 2$ i.e. the number of men (which is also the number of women) is equal to $2$ . We noted that the two perfect matching possible were $\{ (m, w), (m^{\prime}, w^{\prime})\}$ and $\{ (m, w^{\prime}), (m^{\prime}, w)\}$ . I will call these $P_1$ and $P_2$ respectively:

Example 1: Both men prefer $w$ over $w^{\prime}$ and both women prefer $m$ over $m^{\prime}$ . When asked which of the two matchings were stable, the class shouted out all the possible answers except the correct one which was $P_1$ is stable and $P_2$ is not. This is because in $P_1$ neither $m$ nor $w$ have any intention of leaving each other (since they rank highest on each other’s preference lists) and hence there is no instability. Where as in $P_2$ , $(m, w)$ would be an instability. This led us to a new and a more intuitive way of predicting when an instability occurs. That was: “An instability occurs only if there is someone in both the parties ( $M$ and $W$ ) who wants to switch”. To make this clearer and more specific if w wants to switch to m then for there to be an instability, $m$ should also want to switch to $w$ (i.e. the will to switch should be on both sides). This Dr. Rudra pointed out was similar to saying that “You cannot force someone to get married unless they really want to get married”. I’d like to make an addition, the same is true about forcing someone to break up.
In the second example, the preference lists were: $L_m =\{w, w^{\prime}\}, L_{m^{\prime}} =\{w^{\prime}, w\}, L_w =\{m^{\prime}, m\}$ and $L_{w^{\prime}} =\{m, m^{\prime}\}$ . Here both the perfect matchings were stable because in either case there was a pair which had no incentive whatsoever to break up.

Then we tried picking a very informal and “naïve” algorithm to solve the generalization of this problem (i.e. with an arbitrary number of men and women). Andrew suggested Guess and Check. However we analyzed that this would be very inefficient because there were $n!$ perfect matchings possible when $|M| =|W| = n$ . This meant that the algorithm would have a best case running time of $n!\cdot n^3$ ( i.e. $\Omega(n!\cdot n^3 )$ ). The $n^3$ factor is added because we also have to verify if these perfect matchings are actually stable. Also it isn’t necessary that a stable matching would be the output in every case. This also resulted in the question: “Does a stable matching always exist?”

Hence, we turned to the Gale-Shapely algorithm developed in 1962 by David Gale and Lloyd Shapely. Following is the algorithm in my own words:

In the beginning all men and women are free (single).
As long as there is a woman (say ) who is allowed to propose (i.e. she is single and has someone on her list that she hasn’t proposed to already):
- $w$ proposes to the man highest on her preference list that she hasn’t proposed to (say $m$ ).
- if $m$ is free then $w$ and $m$ enter an engagement which like in real life is an intermediate (and possibly temporary) stage. On the other hand if he isn’t free then he checks his preference list. If $w$ is higher up on his preference list that his partner, $(m, w)$ is formed and $m$ breaks up with his current partner. If $w$ isn’t higher on the preference list then she stays free and $m$ remains engaged.
This algorithm runs till there are no women left who can propose.

In the next class we plan to check that the algorithm runs in $O(n^2)$ and that it always outputs a stable matching.

Like this:

Be the first to like this post.

Posted in Lectures, Student post

Responses

Hello everyone. This was written by me and I’d appreciate any comments that anyone has to make here. Thank You.
By: Devanshu Pandey on September 11, 2009
at 2:03 am

Reply
That was a good summary. The thing that makes the Gale-Shapley so effective is the fact that there are checks and balances. The woman is allowed to assert her preference while the man is allowed the option to change the woman he eventually marries based on his preference. I suspect this algorithm always results in a stable matching because of this balance.
By: John Barker on September 11, 2009
at 4:30 pm

Reply
- John,
  
  Yes the check and balance you mention works in the algorithm’s favor. Also the fact that every woman proposes in one direction (and never “goes back”) is crucial for the GS algorithm to work.
  By: atri on September 11, 2009
  at 6:06 pm
  
  Reply
[...] of exactly what we’re trying to do with tokens! So, the solution to this problem is called the Gale-Shapley algorithm, and get this, it’s only worst case O(M*W) where M is the number of men tokens and W is the [...]
By: Record Linkage in F# – Token Matching, Stable Marriages and the Gale-Shapley algorithm « Inviting Epiphany on September 13, 2011
at 1:03 pm

Reply

	atri on Online Office Hour #4
	dan on Online Office Hour #4
	atri on Homework 2
	Tim Hemingway on Homework 2
	Record Linkage in F#… on Lect 4: Gale-Shapley Algo…

Introduction to Algorithm Analysis and Design