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*