Chapter 1

Chapter one was very easy to read, as it reinforced up what we had learned in class. In chapter 1.1, the authors discussed the Stable Matching Problem, which has many applications beyond those discussed in the textbook. When learning about the process behind the Stable Matching Problem in class, it made a lot of sense. Reading it in the textbook helped to reinforce my understanding.

The Stable Matching Problem originated in 1962 when David Gale and Lloyd Shapely asked if one could design a self-enforcing college admissions process. The Gale-Shapely algorithm in this instance was applied to matching men and women based on their preferences. In a set M = (m1, m2, … , mn) of n men and set W = (w1, w2, … , wn) of n women, M x W denotes the set of all possible ordered pairs of the form (m, w). A match is denoted by S, a set of ordered pairs where each member of M and W are in at most one pair of S, and a perfect matching S' is a set where each member of M and W appears in exactly a single pair in S'.

While I question the use of the example involving matching preferences between men and women, it does nicely demonstrate the algorithm. Essentially, the algorithm tries to match any man who is 'free' and hasn't proposed to every woman. He will be matched o the highest preference woman. If she is free or she prefers the new man to her current one, she will accept and a new man becomes free. Otherwise, she will decline. This is a tedious method, however, it only has n^2 possible pairs in total, meaning there are at most n^2 iterations.