Chapter 1

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.