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. It is necessary to note here that an unstable match is one where m prefers w to his current match and w prefers m to her current match. So in order to devise a method to match each man and women in a stable way, we need a set of men of size n, a set of women of size n and a preference list for each man and woman.