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.

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.