Wiki for Chapter 1

Note: I accidentally read this section before class, rather than after. As such, my “second time around” response means after talking about it in class, not after reading it. All Wiki's following this one, though, should be based on reading that I did after the material was first presented in class.

• Summary: Section 1.1 is A First Problem: Stable Matching. The section begins by describing the problem's origins, citing David Gale and Lloyd Shapley as partial sources. The authors quickly shift to presenting the problem in a way that the readers, presumably college students, should understand: CS juniors applying for summer internships. After the example, the authors reveal that 10 years before Gale and Shapley the National Resident Matching Program was using a similar approach to match residents to hospitals, which helps them to establish the significant of the Stable Matching Problem. After this introduction to the problem, the authors move on to simplifying the problem, claiming that the streamlined version can be extended to the general case. Since the streamlined version has a 1:1 relationship, the authors now frame it as men and women getting married. From here, the text starts to establish specifics about the algorithm for the Stable Matching Problem and finally touches on analyzing and extending the algorithm.
• Motivations: This section's given problem is the Stable Matching Problem. This problem was motivated (“in part”) by David Gale and Lloyd Shapley asking if the process by which students are admitted to college, job applicants are offered the positions, etc can be self-enforcing. Their definition of self-enforcing is that entities cannot act “in their self-interest.” They wanted to see if there was a way to design this matching system such that the matches are stable: “there are no further outside deals that can be made.”
• About the Algorithm: In brief, the algorithm to solve the Stable Matching Problem goes as follows. The people are all initially single, and the men propose to the women. While there are any men free and there are women to whom he has not yet proposed, he proposes to the women highest on his preferences to whom he has not yet proposed. If the woman is single, they become engaged. If the woman is already engaged but she prefers this man to her fiancé, she dumps her fiancé and becomes engaged to this new man. If the woman is already engaged and does not prefer this new man, the stays with her fiancé and the man in question remains single. The algorithm terminates with a perfect, stable matching (which the authors prove in the analysis section). The intuitions associated with this algorithm are that a once a woman becomes engaged, she stays engaged; a man may go back and forth between engaged and single; for any man, his woman's ranking can only go down; and for any woman, her man's ranking can only go up. The runtime of the algorithm is O(n^2), where n is the number of men (or women), because n^2 is the maximum number of proposals that can occur.
• My Questions: Not a question, but rather a thought: I had already anticipated that the outcome would be reversed if women were the ones proposing. You'd simply by switching the places of men and women.
• Second Time Around: “Thus, we find that our simple example above, in which the men’s preferences clashed with the women’s, hinted at a very general phenomenon: for any input, the side that does the proposing in the G-S algorithm ends up with the best possible stable matching (from their perspective), while the side that does not do the proposing correspondingly ends up with the worst possible stable matching.” P 12 –> is this the reverse of what we said in class?
• Note To Self: “PROOF: A useful strategy for upper-bounding the running time of an algorithm…is to find a measure of progress. Namely, we seek some precise way of saying that each step taken by the algorithm brings it closer to termination.” p 7 “it’s possible for an instance to have more than one stable matching” p 5
• Readability: Proposition 1.4 and its following proof required multiple reads. It’s not obvious that the returned set is a perfect matching.