Eric Siegel, Columbia University

The Stable Marriage Algorithm

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

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.