This section focuses on the algorithm developed by David Gale and Lloyd Shapley in 1962. The algorithm, called the Stable matching problem, is meant to answer the question: “Could one design a college admissions process, or a job recruiting process, that was self-enforcing?” This algorithm can also be illustrated by matching groups of people into “couples” so that they all are matched with the best possible individual to lead to a stable relationship environment. The remainder of the section goes on to discuss implementation and results of the algorithm and related proofs which will be discussed after this summary.

As aforementioned, the motivation for the problem is to develop a college admissions/job recruitment process that self-enforced and avoided people “jumping ship” to other opportunities.

  Here is a sketch of the algorithm as given by the text:
  Initially all m E M and w E 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 runs in n squared.

I found the discussion in class much more enlightening than the reading, and as such, I give this reading a 2/10.