Chapter 1

Gale and Shapely asked, “Given a set of preferences among employers and applicants, can we assign applicants to employers so that for every employer E and every applicant A who is not scheduled to work for E, at least one of the following two things is the case?

• E prefers everyone of its accepted applicants to A;
• A prefers her current situation over working for employer E

If this holds, the outcome is stable - individual self-interest will prevent anything from changing. Interestingly, Gale and Shapely were not the first people to work on this algorithm. A decade earlier, there had been similar work dealing with matching residents to hospitals.

*There is a stable matching for every set of preference lists.

To simplify the problem, we do things such as ignore the facts that companies are most likely looking for multiple applicants, that there are most likely more applicants than open jobs and that not every applicant will apply to every company. A simpler problem to face is: each of n applicants applies to each of n companies and every company will only accept one applicant. G&S then use a set of men and a set of women getting engaged as their example. A perfect matching set is a matching set with the property that each man and each woman appear in exactly one pair. Each man and each woman creates a preference list of the members of the opposite gender and these preference lists are used to ensure the matching set is stable. If a pair (m, w') does not belong to S, but both m and w' prefer the other to their current partner, the set is unstable.

Description of the algorithm:

   Initially all //m ∈ M// and //w ∈ 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