Eric Siegel, Columbia University

The Stable Marriage Algorithm

Watch an on-line demo of the algorithm written by TA Ivan Leichtling:

• Town with 4 women and 4 men (as shown in class)
• Town with 15 women and 15 men
• Java source code -- If you're taking W1001 or W1007, this is probably going to look very mysterious to you! Don't sweat it.

Here is the official write up on the Stable Marriage Problem and Algorithm. Written by Brandeis' Harry Mairson, it is informative and entertaining.

The problem: Each person has a preference list of the folks of the opposite gender. A pair of people of opposite genders that like each other better than their respective spouses is an instability. How can we pair up all the folks so there are no such instabilities?

The algorithm: Basically, everyone does what they want to do. Note that both the demo (above) and the writeup (above) are sexist in the favor of men, while in class we gave women the advantage by having them do the proposing.