The Gale-Shapley Matching Model

The Gale-Shapley matching model is an algorithm developed by David Gale and Lloyd Shapley in a paper in the American Mathematical Monthly in 1962 [PDF].  It is an algorithm that can be used for studying marriage markets and a whole host of other matching problems such as college admissions and matching residents to hospitals.

Wikipedia describes the model as:

Given n men and n women, where each person has ranked all members of the opposite sex with a unique number between 1 and n in order of preference, marry the men and women off such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are "stable".

The Gale-Shapley algorithm involves a number of "rounds" (or "iterations") where each unengaged man "proposes" to the most-preferred woman to whom he has not yet proposed. Each woman then considers all her suitors and tells the one she most prefers "Maybe" and all the rest of them "No". She is then provisionally "engaged". In each subsequent round, each unengaged man proposes to one woman to whom he has not yet proposed (the woman may or may not already be engaged), and the women once again reply with one "maybe" and reject the rest. This may mean that already-engaged women can "trade up", and already-engaged men can be "jilted".

This algorithm guarantees that:

• Everyone gets married.
• The marriages are stable.

I’m currently trying to program this algorithm using Python that will accommodate any number of potential matches for an independent study I’m doing this semester.  This task is proving to be simultaneously more simple and more difficult than I thought.  (And it’s a heck of a lot more enjoyable than reading case law.)

Here is an excellent Flash-based tutorial that does a wonderful job teaching how the algorithm works.  This tutorial is also a ton of fun.  Check it out.