Chapter 1: Introduction

The motivation for the Gale-Shapley Stable Matching Problem was to design a college admission process/job recruiting process that was self-enforcing. By self-enforcing, they looked to find a stable matching in which individual self-interest prevented any changing/switching behind the scenes from happening. This meant that everyone was happy/satisfied with their current position, and there did not exist a pair that both preferred the same separate situation to their current situation. In designing the algorithm, we can first consider a situation in which two sets of n entities each want to be matched with exactly one entity in the opposite set. In the book they used the idea of 'n' men and 'n' women looking to get married. A matching 'S' between these two sets is a set of ordered pairs that each have a man and a woman, with the property that each member of the set of men and each member of the set of women appears in at most one pair in S. A perfect matching S' is a matching with the property that each member of M and each member of W appears in exactly one pair in S'. The goal of this algorithm is to find a Stable matching, which is a perfect matching that contains no instabilities. An instability exists when a pair (m,w') of a man and a woman does not exist in the perfect matching S', but both m and w' prefer each other to their current partners. The design of the algorithm to obtain a stable matching of men and women consists of a very simple process. To begin with, you must start with a list of size n of men, and a list of size n of women, and a list of preferences of the opposite sex for each man/woman. Each man and woman starts off the algorithm free with no match. Then, you randomly pick a free man that has not proposed to every woman on his list, if he exists, and look at his top preference that he has yet to propose to. If his top preference is free, then they become engaged. Else, if his top preference is engaged, you look at her preferences. If the woman prefers her new proposer to her current fiance, she will swap and become engaged to the new man and her current fiance will become free, otherwise she will reject the proposer. This algorithm then repeats until no free men exist, which results in every man and woman being matched. We know that this algorithm must terminate since once every man has proposed to every woman on his list, the algorithm must terminate after at most n^2 iterations, since there are n men each with n women to propose to. The set S returned by the algorithm is a perfect matching since after every iteration of the algorithm, and man and woman are matched, since the algorithm terminates, that means that there is no man who hasn't proposed to every woman, which means that there cannot be a free woman. From this algorithm, we are also able to conclude that the set that does the proposing (men) always ends up with the best possible stable matching according to their preferences, while the set that is proposed to(women) ends up with the worst possible stable matching according to their preferences. The explanation of this algorithm in the book was very descriptive and clear, which provided a very understandable idea of the purpose of the problem. The solution obtained is a very logical and well explained conclusion. This section was very readable and easy to understand, a 10/10.