Stable Marriage algorithm

Previous: Greedy algorithm Up: The pairing step Next: Brute force

Stable Marriage algorithm

This algorithm has a long history. It actually predates computer uses, and was originally invented to match interns to hospitals during the post-WWII boom years. There were more positions available than interns, yet every hospital wanted the best interns they could get. Interns, also, wanted the best deal they could find, subject to other constraints, such as living in a city they liked.

The problem is described in [7] in terms of matching men and women for marriage. Given an equal number of men and women, and a set of preferences for each individual, the stable marriage algorithm forms a unique assignment. The resulting assignment has the property that exchanges of any two partners will result in an overall decrease in happiness.

This algorithm has been implemented, and it works as advertised. Unfortunately, it does not solve the right problem. The Stable Marriage problem is based on the idea of minimizing unhappiness. The unhappiness, however, is only relative; i.e. one pairing is either better or worse than another. No measurement of how much better or worse is done. There is an information loss here.

stable3Failing case for stable marriage algorithm

The source of the loss is because the preference lists must be built by taking the matrix of distances, and sorting each row. This gives a preference list.

An example can be given of two distance matrixes, that have the same real solution, yet have different stable marriage solutions. This is shown in figure . Note that there are really only two possible arrangements (modulo reflections) of two pairs in one dimension: and .

mcr@ccs.carleton.ca