In 1962, David Gale and Lloyd Shapley asked the question: Could one design a college admissions process, or a job recruiting process, that was self-enforcing? Self-enforcing, in this case, means that a system based on self interest prevents offers from being retracted or rejected and thus causes a stable system. The question ended up being: “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 : I. E prefers every one of its accepted applicants to A; or II. A prefers her current situation over working for employer E.

It is implemented as follows:

  Initially all m that are elements of M and w that are elements of 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(prime)
          If w prefers m(prime) to m then
              m remains free
          Else w prefers m to m(prime)
              (m, w) become engaged
              m(prime) becomes free
  return the set S of engaged pairs

This runtime in worst case is O(n^2), because the while loop runs through both all men and all those men's preferences - n * n.

Interestingly enough, every time this algorithm is run, it results in the same set S - that is, everyone is as happy as they could be according to their preferences.

This section was very interesting, giving quite a few new perspectives on problems faced in algorithm design. 8.5/10