Chapter 1 – Introduction: Some Representative Problems

My notes on the assigned sections of Chapter 1 of Algorithm Design by Jon Kleinberg and Éva Tardos.

This section details the stable matching problem. The motivation for this problem was originally to create a stable matching algorithm for a college admission process or a job recruiting process that was self-enforcing. The algorithm needs to avoid instabilities: when a man and a woman each prefer each other to their current partners. The Gale-Shapley algorithm addresses this need. The algorithm terminates after at most n^2 iterations. The sequence of partners that the woman gets engaged to gets better and better, while the sequence of women that the men propose to gets worse and worse. There is some unfairness in the G-S algorithm favoring men, and all executions of the G-S algorithm yield the same matching.

Basic Sketch of the Gale-Shapley algorithm for stable matching: while some man is free and hasn't proposed to every woman Choose such a man m w = 1st woman on m's list to whom m has not yet proposed if w is free assign m and w to be engaged else if w prefers m to her fiancé m' assign m and w to be engaged and m' to be free else w rejects m After reading the section, all the proofs make much more sense now. The only one that still is a little confusing to me is (1.8) that each woman in a stable matching is paired with her worst valid partner. It makes some sense, but I have to read over it a few times to make it make sense in my head. I'm sure it will make more sense over time. This section is a 8/10 in terms of readability and being interesting to me.