This is an old revision of the document!

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