And preferably one that doesn’t leave you
Already back in the early 60’s, David Gale and Lloyd Shapley constructed a matching algorithm which has become one of the crucial tools of modern market design. In particular, using examples of college admissions and stability of marriage, they presented a method how a market where money cannot serve as an allocation rule may reach a stable and pareto-optimal equilibrium. Other examples of such markets include organ donations, allocation of children to schools or assigning dorm rooms to college students.
Suppose the following example. There are women and men taking dancing lessons and before each lesson begins, they need to form dancing couples. Naturally, all participants will think about and compare the potential counterparts; they may even consider a list based on their preferences. As the authors prove mathematically, employing the Gale-Shapley (also called “deferred-acceptance”) procedure ensures that the solution to the problem, i.e. the couples that have formed, will be stable. By stable in this example we understand an allocation in which no two people of opposite sex would both rather have each other than their current partners, and thus will not switch partners given that their preferences do not change. After explaining the algorithm and its characteristics, the authors examine the optimality issue, which, however, is a more complex task and depends on a particular set-up of the problem.
The figure below shows an example of a stable outcome of the Gale-Shapley procedure based on the preferences of all 8 participants. The number for each pair represent the ranking of the counterpart among the four potential mates. As an example, the first cell – (1, 3) – tells us that A would be the first choice for alpha and alpha would be the third choice for A. Running the procedure yields the stable pairs whose preferences for each other are circled in the table. An interesting aspect of this particular outcome is that no participant was matched with his or her first choice. Nevertheless, the stability ensures that no participant could improve his situation while not leaving at least one other participant worse off. The results reached in this paper have had an enormously important impact on the future development of market design theory. Lloyd Shapley received a Nobel Prize in Economics in 2012 for this work and passed away in March this year; David Gale, who passed away in 2008, has not received the prize because it can only be awarded to living scientists.
Reference: Gale, D., & Shapley, L. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9-15. Available here.