The Cooperative Theory of Two Sided Matching Problems: A Re-examination of Some Results

We show that, given two matchings of which say the second is stable, if (a) no firm prefers the first matching to the second, and (b) no firm and the worker it is paired with under the second matching prefer each other to their respective assignments in the first matching, then no worker prefers the second matching to the first. This result is a strengthening of a result originally due to Knuth (1976). A theorem due to Roth and Sotomayor (1990), says that if the number of workers increases, then there is a non-empty subset of firms and the set of workers they are assigned to under the F - optimal stable matching, such that given any stable matching for the old two-sided matching problem and any stable matching for the new one, every firm in the set prefers the new matching to the old one and every worker in the set prefers the old matching to the new one. We provide a new proof of this result using mathematical induction. This result requires the use of a theorem due to Gale and Sotomayor (1985 a,b), which says that with more workers around, firms prefer the new optimal stable matchings to the corresponding ones of the old two-sided matching problem, while the opposite is true for workers. We provide an alternative proof of the Gale and Sotomayor theorem, based directly on the deferred acceptance procedure.