Matchmaker, matchmaker

bmulaney Blog,

Last week, Philipp Kircher gave the Royal Economics Society’s annual public lecture on the economics of ‘finding the right match’, comparing the labor market to the marriage market. [1]

This topic reminds me of matchmaking as a concept of market design. in 1962, David Gale and Lloyd Shapley published a (readable) paper on the problem of pairwise matching. They showed that in a group of an equal number of “proposers” and “proposees” (“proposers” being those who make the marriage proposal, and “proposees” being those who accept or reject the marriage proposal of the proposer), there always exists a ‘stable’ set of marriages by an iterative process now known as the “deferred acceptance” algorithm.

[The way the deferred acceptance algorithm works, in a nutshell: the proposers start by proposing to their favorite proposees. If the proposee accepts, they get married, and these married couples exit the pool of unmarried people. Now we move to round 2, in which any proposers who were rejected initially propose to their second choice proposees, and so on, until everyone is married (p. 12 of Gale & Shapley)]

Even though the deferred acceptance algorithm leads to a stable outcome—in which no one will divorce his/her/their partner—it is possible this outcome is not optimal for all individuals. In fact, there can be multiple stable outcomes. John Conway (via Donald Knuth, 1976) showed that all of the possible stable outcomes can be ordered according to individuals’ preferences. Further, whichever stable outcome ends up being the outcome obtained by the deferred acceptance algorithm depends on who gets to be the proposer. The deferred acceptance outcome will favor those who are proposers, while being sub-optimal for proposees.

Okay, so perhaps this deferred acceptance algorithm doesn’t make much sense in the context of marriage—after all, in what world would people know and be able to rank their preferences for ALL possible matches (which is what we assume)? (E.g., even if the pool were simply your college classmates—would you be able to rank all several hundred or thousand of them? Chances are you don’t know all of them / don’t know enough information about all of them to do so…)

Alvin Roth applied this theory to a few real-life situations that more closely align with the theory in practice: college admissions, kidney exchange markets, and physician residencies/internships. His most famous example is that of the U.S. National Resident Match Program (NRMP), a centralized system for matching fourth-year medical students with hospitals that offer residency programs. For all you doctors and future doctors out there, the Gale-Stanley deferred acceptance algorithm was the basis for the NRMP! However, there were some key issues with the algorithm, including
(1) hospitals, as the “proposers,” were being favored over doctors (“proposees”)
(2) if multiple people can match to one hospital, what happens if you want to ‘link’ two people entering the lottery so that they always end up matching to the same hospital?

Roth addressed these issues in his work and came up with a revised algorithm that is used to match doctors to hospitals today.

Roth and Shapley won the Nobel prize for their contributions to market design in 2012.

Scott Kominers gives a great overview of all of this in this lecture.

[1] his talk starts at 6:00, and you can click the gear icon to change the speed

Leave a comment