Wiki for Chapter 1

Note: I accidentally read this section before class, rather than after. My “second time around” response should still be interpreted as after class, though, because I reread the section after class in order to write this Wiki. All Wiki's following this one, though, should be based on reading that I did strictly 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 the authors to establish the significance 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” (p2). 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” (p2).
• 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, she 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 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 be switching the places of men and women. I do have a question about analysis, though. The book says: “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” (p12). Isn't this the reverse of what we said in class and what was said on page 7, that women get better men as time goes on and men get worse women as time goes on?
• Second Time Around: I definitely think the proofs in the analysis section make more sense the second (or third) time around. I'm not the best at proofs - I usually understand the intuition, but I often don't know when you've said enough to conclude that you've proven something. Hence, I liked that the proofs were spelled out so I could follow the logic that yields a valid proof. In particular, the proof about stability made more sense after reading because the book says the instability would involve two pairs, whereas in lecture we framed it as one pair. I was confused about the question in class, and it now makes more sense.
• Note To Self: I want to remember that “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” (p7). I already knew this, but I like the way that it's phrased here.
• Readability: I think everything leading up to the subsection about extensions should get an 8 or 9 in readability. It's fairly straightforward and most of the algorithm was addressed in layman's terms rather than as complicated math. The extensions subsection, though, had a good bit of math notation and that's sometimes hard to read for understanding if you're not a math major (or maybe even if you are). I do appreciate, though, that the authors level with the reader and acknowledge when things aren't obvious. For example, after proposition 1.7, that every execution of the G-S algorithm results in the set of pairs where each man is matched with his “best possible partner,” they say “why couldn't it happen that two men have the same best valid partner?” (p10).