Want to be a Match Maker?
By Fabian Meraz
Your Task:
Suppose that you need to pair up n men and n women in such a way that no one will cheat on their partner. We don’t want anyone going to the Jerry Springer show. Do you think you can do this?
Encouraging words:
Don’t be nervous, you can do this. How do I know? Well, the stable marriage theorem states that you can do this, if you follow the right algorithm.
How?
First you want to make sure to have the men make a list ranking all the n women from their first choice to their last choice. Next, have the women do the same thing.
You will now have the men propose to their first choice. The women will either accept this proposal or deny it. They will accept the proposal from the man they believe is the best option. The men that were rejected then propose to their second choice. Again the women either accept or deny the proposal. This same process will continue until every man has partner.
If you follow these simple steps, you can make sure that none of your couples will cheat.
Proof:
Suppose man i would like to cheat on his mate with woman j. Since man i is more interested in woman j, this means he already proposed to her. But since he is not with her, that means woman j rejected him for someone better. Thus, even though man i is more interested in woman j, woman j is not interested in man i.
Example:
To see an actual example of this, see this video. The example starts at the 8 minute mark.
Exam problem:
Suppose you receive the following list(where (3,1,4,2) means man 1 prefers woman 3, his second choice is woman 1, his third choice is woman 4, and his last choice is woman 2).
Man 1: (3,1,4,2) Woman 1: (3,1,4,2)
Man 2: (1,3,2,4) Woman 2: (3,1,2,4)
Man 3: (4,3,2,1) Woman 3: (1,2,3,4)
Man 4: (3,4,1,2) Woman 4: (4,2,3,1)
Use the stable marriage algorithm to find a stable pairing.
Sources
http://www.youtube.com/watch?v=w1leqkpDaRw