Chapter 1: Introduction

The Stable Matching Problem is based on a question posed by David Gale and Lloyd Shapley which involved a self-enforcing admissions or recruiting process. In a more technical sense, this question is phrased as follows:

• “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…[either] E prefers every one of its accepted applicants to A; or A prefers her current situation over working for employer E.”

In order to simplify the problem, we can assume there is a 1:1 ratio of applicants to companies, so each applicant will only be matched at one company. Two terms are important in this problem and in the study of algorithms as a whole. Consider two sets, M and W:

• matching: a set of ordered pairs, composed from M and W, where each item of M and each item of W occurs at most once
• perfect matching: a matching such that each item in M and each item in W occurs exactly once

A stable matching occurs when a matching is both perfect and contains no instability. It is important to note that an instance can have multiple stable matchings. The Gale-Shapley algorithm can be roughly sketched as follows:

  Start all m ∈ M and w ∈ W are available for proposal
  While man m not proposed to every woman:
      Choose m
      Let w be highest-ranked woman for m that m has not 
          proposed to
      If w available:
          (m, w) engaged
      Else w engaged to m':
          If w prefers m' to m:
              m remain available
          Else w prefers m to m':
              (m, w) become engaged
              m' become available
  Return S (set of engaged pairs)
  

The runtime of this algorithm is at most n² iterations. Another interesting fact of the Gale-Shapley algorithm is that all executions return the same matching, one in which each m ∈ M is paired with its ideal w (provided no overlapping preferences). However, for all w ∈ W, their pairings are the worst possible m.

I am interested by the claims being proved in this section; I do not always see the relevance in their arguments. I would assume the purpose is to illustrate the trends and facts of this algorithm. I found this section to provide a strong introduction to algorithms in a simple manner using an understandable example.