Matching markets: Theory and practice
It has been almost a half-century since David Gale and Lloyd Shapley (1962) published their pathbreaking paper, “College Admissions and the Stability of Marriage,” in American Mathematical Monthly. It is difficult to know whether Gale and Shapley expected the literature they initiated to be used to improve the lives of masses of people all around the world. We are fortunate to see that this is happening today. The model that Gale and Shapley presented is very simple. A number of boys and girls have preferences for one another and would like to be matched. The question Gale and Shapley were interested in especially was whether there is a “stable” way to match each boy with a girl so that no unmatched pair can find out later that they can both do better by matching each other. Gale and Shapley found that indeed there is such a stable matching, and they presented a deferred-acceptance algorithm that achieves this objective. Versions of the algorithm are used today to match hospitals with medical residents and students with public schools in New York City and Boston. In 1974, Lloyd Shapley and Herbert Scarf published a related paper, “On Cores and Indivisibility,” in the first issue of the Journal of Mathematical Economics. Arguably, their model was the simplest exchange economy we could imagine. Each agent comes to the market with one indivisible good and seeks to trade it for more preferred goods that might be brought by other agents.
