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.