Section 1.1

Section 1.1 deals with the Stable Matching Problem. The algorithm that solves this problem can be used for a variety of different applications, including matching residents with hospitals, job candidates with jobs, or freshman girls with sororities. We will talk about it in terms of matching men and women in monogamous, heteronormative relationships.

First, we must define a stable matching as 1) all matches are perfect (monogamous) and 2) no matches are unstable. An unstable match is one where