Chapter 1: Intro

The Stable Matching Problem is presented in a variety of motivational contexts, ranging from summer internships to medical school residencies. In 1962, mathematical economists Gale and Shapley approached it in the hopes of a self-enforcing process, or one that, by its own nature, guarantees stable matches. These are matches in which there are no two parties which would prefer being matched with one another than their current matching.

In formulating the problem, simplification becomes extremely helpful. This is done through re-defining it in terms of marriages between men from a set, M, and women from set W, each with equal numbers (nominally, n men and n women). Further defining the problem mathematically, we define a perfect matching as a set S' of ordered pairs (m, w), where each m in M and w in W appear in exactly one ordered pair. (The more general term matching is also defined as a set where each m and n appear at most once, but this will only be relevant in later problems).

Each man and woman rank all members of the opposing group in a preference list, with no tied rankings. Then, we define a stable matching to be a perfect matching in which every couple meets the above definition of being stable.