Chapter 1

The problem stems from the question that could one design a college admissions process, or a job recruiting process, that was self-enforcing, i.e. self-interest would prevent offers from being retracted and redirected, and all the offers would be stable?

This problem can be reduced to a simple problem, the solution to which can be extended to solve the Stable Matching Problem in general: given a set of n men and n women and an order of preference for each man and woman, find a stable matching such that everyone ends up married to somebody and nobody is married to more than one person. This problem is solved–efficiently–by the Gale-Shapley algorithm.

A sketch of the Gale-Shapley algorithm (from Page 6 of the textbook) to this problem is given below:

Initially all m and w are free

While there is a man m who is free and hasn’t proposed to every woman 
   Choose such a man m

   Let w be the highest-ranked woman in m’s preference list to whom m has not yet proposed 
   If w is free then 
      (m, w) become engaged

   Else w is currently engaged to m’ 
      If w prefers m’ to m then 
         m remains free 
      Else w prefers m to m’ 
         (m,w) become engaged
         m’ becomes free 
      Endif 
   Endif 
Endwhile

Return the set S of engaged pairs 

The algorithm terminates after n^2 steps at most, since every man can at most propose to each of n women. Therefore, it is O(n^2). The proof for the algorithm is given on Page 7 of the textbook.