The Stable Matching Problem arose from a situation in which two economists (Gale and Shapley) posed the question: Could one design a college admissions process, or a job recruiting process, that was self-enforcing? What they meant was, is it possible to match employers and applicants in such a way that neither the employer nor an applicant would benefit from trading with another employer/applicant. For example, If person 1 is working for job A but would rather have job B and job B employed person 2 but would prefer person 1, they could just switch and be happy. That is an unstable match. However, this problem is really complicated because you have to take into account how many applicants there are, what their preference is, how many job slots there are, and what each employer’s preference is. To simplify this, we can look at a pool of males and females and match them together. Each male and female comes up with their preference list, and at the end of the matching, each member is paired with exactly one individual of the opposite gender.

Initially everyone is single. An unmarried man, m, chooses the woman, w, who ranks highest on his preference list that he hasn’t proposed to and proposes to her If the woman, w, is single, she accepts. If not, she looks at her own preference list and

• (a) If the man, m, ranks higher than her current partner, m', then she leaves him and becomes engaged to m, leaving m' single
• (b) Otherwise, she rejects m’s proposal and m remains single

The algorithm terminates when no one is single and every woman has been proposed to This algorithm returns a perfect matching—one in which no one is single and every individual is paired with exactly one individual of the opposite gender. It also terminates after at most n2 iterations (worst case: every man proposes to every woman—n x n = n2). We can prove that the G-S algorithm returns a perfect, stable matching by contradiction. Suppose the matching isn’t perfect; i.e. there is a man, m, who is single at the end of the algorithm. However, m would have had to propose to every woman in order for the algorithm to terminate, so there must be a woman, w, who is still single, a contradiction. Now suppose the matching isn’t stable. So there are pairs (m,w) and (m’,w’) such that m prefers w’ to w, w’ prefers m to m’. So either m proposed to w first, leading to their engagement, which means that m does not prefer w’ to w, or w’ broke off her engagement for m’, which means that w’ does not prefer m to m’, a contradiction. So the G-S algorithm does provide a perfect, stable matching. It is also important to note that all executions of this algorithm yield the same matching. Although this algorithm does provide a clean solution, it does not take fairness into account. Throughout the algorithm, men start out with their top choice woman and, as the algorithm proceeds, he can bounce between being engaged or singe, and his prospects worsen. Women, on the other hand, are engaged the entire time (after their first proposal) and their prospects improve as the algorithm proceeds. However, in the end, men are paired with their best valid partner and women are paired with their worst valid partner. So, in general, the side that does the proposing in the G-S algorithm ends up with the best possible stable matching (from their perspective) and the other side ends up with the worst possible stable matching.

I found this section pretty redundant. We covered all of this in class (very thoroughly) so I had a pretty good grasp of the problem and what the algorithm looks like. Had I been confused at all, this definitely would have cleared things up. It was very easy to understand, so I’d rate it a 10.