2012 Nobel Memorial Prize in Economics – Lloyd Shapley, Al Roth

For a popular article, see http://www.nature.com/news/a-nobel-for-the-art-of-matchmaking-1.11607#/ .

The goal of this post is to overview the basic problem of matching and give some examples of current/popular applications.

For some cool and more technical slides on market design, see Itai Ashlagi’s slides from the CMU Summer School on Algorithmic Economics, linked here: http://www.cs.cmu.edu/~arielpro/summer/schedule.html#itai .

Stable Matching

In the basic setting, our goal is to arrange marriages between a group of n heterosexual women and n heterosexual men. Each woman has a preference ordering on the men: for example, she might prefer A > B > C > …. Each man has a preference ordering on the woman.

matching is an assignment of marriage partners: each woman to exactly one man and vice versa. A matching is stable if there is no pair (woman,man) who are not matched to each other, for whom the following holds: The woman prefers the man to the guy she’s matched to, and the man prefers the woman to the gal he’s matched to.

So a stable matching just means one where no pair will want to deviate from the assigned matching and elope together.

You can read more on the stable marriage problem at Wikipedia. In 1962, David Gale and Lloyd Shapley provided an algorithm to find a stable matching given each person’s preference ordering. The algorithm is computationally efficient, and it works like this.

In round one, each woman “proposes” to her top-ranked man. Each guy who has received more than one proposal rejects all the proposals except the one he likes best (from the woman highest in his preference ordering). He holds onto this one for now. In round two, each woman who was just rejected proposes to her second-ranked man. Again, all men with more than one proposal, including the one from the previous round, reject all except their favorite.

We repeat this process until everyone is matched to someone. You may convince yourself that the resulting matching must be stable.

(We can also check that it will be woman-optimal — that is, since the women proposed, it will be the “best” matching out of all possible stable matchings from their point of view. If the men proposed, we’d get a man-optimal stable matching.)

If you like graphs, you may think of the above problem as finding a matching in a bipartite weighted graph, with the property that for each unmatched edge, at least one of its vertices is an endpoint of a matched edge with higher weight.

Applications and Extensions

Residency Matching

In the United States, future doctors enter residency programs after completing medical school. The matching of med school grads to residency programs is done by an algorithm based on extensions of the matching theory above.

Students apply and get interviews at various programs. Then, students and schools both send in their preference orders over interviewers/ees to the centralized match, which computes a stable matching. Students all receive their school assignments on the same day.

Of course, making this actually work on a national scale isn’t quite so easy. One particularly thorny problem is the extension of the matching process to deal with couples, who have joint preferences (e.g. preferring to both go to the same city, but having preferences over residency programs within each city). Solving such problems, and understanding how they affect the possibility of stable matchings, is an ongoing research question.

It’s also worth noting how this problem came up in the first place, and why this solution was first instituted. The problem was that residency programs were accepting students earlier and earlier in an effort to beat each other out in getting the best med students. There seemed to be no good way to incentivize residency programs to all wait together for some fixed deadline. Thus the centralized match was used as a solution.

Kidney Exchange

In the U.S., buying and selling of organs is illegal (this brings up the issue of repugnance — human/cultural aversion to making markets for certain things). It is difficult for people who need organ donations to get them.

Kidney exchange helps solve the following problem. Suppose you’re sick and need a kidney. There is a person who is willing to donate a kidney for you, but unfortunately the two of you are not compatible. However, somewhere else in the state, in the country, or in the world there is a pair of people with the opposite problem. By swapping kidneys, both of you can get a lifesaving treatment.

Of course, there are a whole lot of details to work out from there for making each donation have the most positive impact that it can. There are many blood types and levels of compatibility and issues of time and distance. An interesting research question is how one should use altruistic donors (or kidneys from dead people) to start a “chain” in which each person receiving a kidney has a friend who donates the next one.

Public School Choice

Another case where matching theory has been applied is in assigning students to schools in New York.

There are probably many more examples out there, but these are some of the most prominent. Congrats to Shapley and Roth on their accomplishments!