Chapter 1

Section 1.1 begins with an introduction of the Stable Matching Problem. The motivation behind this problem is to create a self-enforcing matching process, where the self interests of two given parties prevent matched pairs from being retracted and redirected. The authors explain this problem through the context of applicants seeking summer internships with certain employers. Given E employers and A applicants, as well as a list of preferences for each party, the goal of the problems is that either:

• E prefers every one of its accepted applicants A; or
• A prefers his/her current situation over working for employer E.

If these two conditions hold, then the outcome is stable. Later, the authors switch the context of the problem from employers and applicants to men and women, where, given n men and n women, we must create a stable, perfect matching for every set of preference lists among the men and women. To do this, we utilize the Gale-Shapley algorithm:

   set every couple to be unmatched
   while some man is free and has not proposed to every woman:
        choose man m
        w = woman of highest order preference on man m's list and has not been proposed to yet
        if w is free:
             match m and w
        elif w prefers m over currently matched m'
             match m and w and free m'
        else
             w rejects m

Some observations of this algorithm are that womans' partners increase (in terms of their preferences) over time, and that mens' partners decrease over time. Additionally, once a woman has been matched, she can no longer be unmatched, whereas a man can. The runtime of the algorithm is n^2. The readability of this section is 7/10.