Chapter 1: Introduction

Stable matching is an algorithm that solves the classic problem of creating pairs from two parties, both with their own preferences, in such a way that no pair would leave their current partners for each other. This problem can apply to applicants applying for positions with a set of companies, the college application process, or groups of men and women. The Gale-Shapely algorithm was developed by David Gale and Lloyd Shapely to solve this problem. The section boiled the overarching problem to its most basic element, which is a set of n men and n women who are set to be engaged. Each man will only be paired to one woman and vice versa. The end goal is to make sure that each man prefers his partner over every other woman and each woman prefers her man over every other man. The section discussed whether or not a there could be multiple stable matches, to which the answer is yes. The section then walked through how to build the algorithm step by step and proved that the algorithm actually solved our problem. It showed that the algorithm terminated, created perfect matches (one man to one woman and no one left out), and stable matches. Finally, the section looked deeper into questions one could ask about the algorithm. It discussed fairness, as in the algorithm the man is allowed to choose his first choice of woman, so often men can get their first choice while women do not. More generalized, the person doing the proposing ends up with the best possible matching, while the people who are getting proposed to end up with the worst possible matching.

This problem was motivated by the need to create a system that could provide matchings that made people and companies happy while at the same time preventing self-interest from interfering.

The algorithm is outlined like this: Initially all men and women are free/unengaged While there is a man m who is free and has not proposed to every woman:

Choose such a man m
Let w be m’s highest ranked woman to who he has not proposed yet
If w is free (m,w) become engaged
Else w is currently engaged to m’
	If w prefers m’ to m then m remains free
	Else w prefers m to m’ and (m,w) becomes engaged and m’ becomes free
Return set of engaged pairs.

The runtime of the algorithm is n2 as the loop will execute at most n2 and the operations within the loop run in constant time. The way the while loop is worded ensures that the algorithm will not terminate until all men and women are matched. In this algorithm a woman’s partner can only “upgrade” while a man can only “downgrade” his partner. The unfairness idea made more sense after reading it. We briefly discussed it in class but the book elaborated upon the subject. I find this problem to be very interesting so the section was a 9. I like the idea that matching people, even based off of their own emotions and preferences can be boiled down to an algorithm.