1 - Mathematical Matching

Summary

INTRODUCTION

In 1962 a paper by David Gale and Lloyd S. Shapley appeared at the RAND Corporation, whose title, “College Admissions and the Stability of Marriage, ” raised eyebrows. Actually, the paper dealt with a matter of some urgency.

According to Gale, the paper owes its origin to an article in the New Yorker, dated September 10, 1960, in which the writer describes the difficulties of undergraduate admissions at Yale University. Then as now, students would apply to several universities and admissions officers had no way of telling which applicants were serious about enrolling. The students, who had every reason to manipulate, would create the impression that each university was their top choice, while the universities would enroll too many students, assuming that many of them would not attend. The whole process became a guessing game. Above all, there was a feeling that actual enrollments were far from optimal.

Having read the article, Gale and Shapley collaborated. First, they defined the concept of stable matching, and then proved that stable matching between students and universities always exists. This and further developments will be discussed in this chapter.

For simplicity, Gale and Shapley started with the unrealistic case in which there are exactly n universities and n applicants and each university has exactly one vacancy. A more realistic description of this case is a matching between men and women – hence the title of their paper.