Last time we encountered the stable marriage problem for the first time: given a set of n “men” and n “women” (where each one has a preference ranking of all the others), is it always possible to specify a matching between the two sides such that every man is paired to exactly one woman, and the matching is stable (in the formal sense defined last lecture)? Initially, we studied the stable roommates problem and found that in that related problem, stable matchings are not guaranteed to exist. Must that negative result carry over to the stable marriage problem? As it turns out, it does not. To understand why and to answer many of our fundamental questions about the stable marriage problem, we turn now to one of the great algorithms of the 20th century.