The nobel art of matchmaking

I have a Nature news story on the economics Nobel prize. Here’s the pre-edited version.

________________________________________________

Two economists are rewarded for the theory and application of how to design markets for money-free transactions

The theory and practice of matching resources to those who need them, in cases where conventional market forces cannot determine the outcome, has won the Nobel prize in economics for Lloyd Shapley of the University of California at Los Angeles and Alvin Roth of Harvard University.

Their work on matching “has applications everywhere”, says economist Atila Abdulkadiroglu of Duke University in Durham, North Carolina. “Shapley's work laid the groundwork, and Roth's work brought the theory to life.”

“This is terrific prize to a pair of very deserving scholars”, says economist Paul Milgrom of Stanford University in California.

The work of Shapley and Roth shows how to find optimal matches between people or institutions ‘trading’ in commodities that money can’t buy: how to allocate students to schools or universities, say, or to match organ donors to patients.

Universities can’t determine which students enrol simply by setting their fees arbitrarily high, since these are capped. And payments for organ donation are generally prohibited on ethical grounds. In such situations, how can one find matches that are stable, in the sense that no one considers they can do better by seeking a different match?

In the 1960s Shapley and his coworker David Gale analysed the most familiar match-making problem: marriage. They asked how ten men and ten women could be matched such that none would see any benefit in breaking the partnership to make a better match.

The answer was to let one group (men or women) choose their preferred partner, and then let those who were rejected by their first choice make their second-best selection. This process continues until none of the choosers wishes to make another proposal, whereupon the group holding the proposals finally accepts them.

Shapley and Gale (who died in 2008) proved that this process will always lead to stable matching [1]. They also found, however, that it works to the advantage of the choosers – that is, those who make the proposals do better than those receiving them.

“Without the framework Shapley and Gale introduced, we would not be able to think about these problems in sound theoretical terms”, says Abdulkadiroglu.

However, their work was considered little more than a neat academic result until, about 20 years later, Roth saw that it could be applied to situations in the real world. He found that the US National Resident Matching Program, a clearing house for allocating medical graduates to hospitals, used an algorithm similar to Shapley and Gale’s, which prevented problems caused by the fact that hospitals might need to offer students internships before they even knew which area they were going to specialize in [2].

But he discovered that the same problem in the UK was addressed with quite different matching algorithms in different regions, some of which were stable and some not [3]. His work persuaded local health authorities to abandon inefficient, unstable practices.

Roth also helped to tailor such matching strategies to specific market conditions – for example, to adapt the allocation of students to hospitals to the constraint that, as more women graduated, students might often be looking for places as a couple. And he showed how to make these matching schemes immune to manipulation by either party in the transaction.

Roth and his coworkers also applied the Gale-Shapley algorithm to the allocation of pupils among schools. “He directly employs the theory in real-life problems”, says Abdulkadiroglu. “This is not a trivial task. Life brings in complications and institutional constraints that are difficult to imagine or study within the abstract world of theory.”

Shapley extended his analysis to cases where one of the parties in the transaction is passive, expressing no preferences – for example, in the allocation of student rooms. David Gale devised a scheme for finding a stable allocation called ‘top trading’, in which agents are given one object each but can swap them for their preferred choice. Satisfied swappers leave the market, and the others continue the swapping until everything has been allocated. In 1974 Shapley and Herbert Scarf showed that this process always led to stable solutions [4]. Roth has subsequently used this approach to match patients with organ donors.

All of these situations are examples of so-called cooperative game theory, in which the agents seek to align the choices, make matches and coalitions – as opposed to the more familiar non-cooperative game theory that won Nobels for John Nash (1994), Thomas Schelling (2005) and others, in which agents act independently. “In my view, Shapley has made more than one prize-worthy contribution to game theory”, says Milgrom, “but his work on matching has the greatest economic significance.”

With economic theory signally failing to bring order and stability to the world’s financial markets, it’s notable that the Nobel committee has chosen to reward work that offers practical solutions in ‘markets’ in which money is of little consequence. The work of Shapley and Roth shows that there is room for economic theory outside the ruthless cut-and-thrust of money markets – and perhaps, indeed, that in a more cooperative world it can be more effective.

References
1. Gale, D. & Shapley, L. S. American Mathematical Monthly 69, 9-15 (1962).
2. Roth, A. E. Journal of Political Economy 92, 991-1016 (1984).
3. Roth, A. E. American Economic Review 81, 415-40 (1991).
4. Shapley, L.S. & Scarf, H. Journal of Mathematical Economics 1, 23-37 (1974).