Stable Marriage Problem

Every instance of the Stable Marriage Problem involves two finite sets of equal size. We can think of one of the sets as containing men and the other as containing women. Each person must rank the members of the opposite gender in their order of preference. The goal is then to create a set of man-woman couples with the following stability property: It is impossible to find a man and a woman who prefer each other over their respective partners in the set of couples. A set of couples having this property is called a stable matching. Such matchings can be found using the Gale-Shapley algorithm. In this thesis, we discuss the history of the Gale-Shapley algorithm. We also state and prove some theorems which establish the most important properties of the algorithm. We provide many examples in order to demonstrate how the algorithm works