How an Algorithm for Finding the Perfect Husband Won a Nobel Prize

Commentary about business and finance.
Oct. 15 2012 1:51 PM

Marriage as an Economic Problem

Lloyd Shapley and Alvin Roth win the Nobel Prize for showing the best way to match people with what they really want.

Alvin E. Roth and Lloyd S. Shapley.
The Nobel Prize in economics went to Alvin E. Roth and Lloyd S. Shapley "for the theory of stable allocations and the practice of market design"

Economics is closely associated with the idea of money, but economic life extends beyond what can be or is monetized, as shown by the winners of this year’s economics Nobel Prize, Lloyd Shapley of UCLA and Alvin Roth of Stanford, “for the theory of stable allocations and the practice of market design.” What makes their work in these fields stand out is that it primarily describes markets without any money at all.

When you have money, the question of “stable” allocations isn’t all that interesting. If I prefer your coffee table to my coffee table, but you prefer my coffee table to your coffee table then we ought to switch tables. But the world is a big place, full of many people, many coffee tables, and many possible desires. Achieving stable allocations of goods through this kind of direct swapping poses huge logistical problems. So in advanced market economies we generally trade things for money, which is appealingly flexible and convenient to transport. For just this reason, economists are often frustrated by rules that try to block transactions or limit the scope of markets, leaving people saddled with poor allocations of goods.

Yet in practice, there are many aspects of life where (for better or for worse) the settled view is that monetary exchange would be inappropriate. And here is where Shapely and Roth come in.

Shapley’s first work came in a somewhat whimsical 1962 paper co-authored with David Gale on the subject of “College Admissions and the Stability of Marriage.”

A college that takes its reputation seriously can’t just sell slots to the highest bidder. Nor can it simply say it has 1,000 slots in its freshman class so it’ll accept only the 1,000 best applicants. After all, if those applicants are so good many of them will have competing offers and end up going elsewhere. But a college doesn’t want to find itself deliberately refusing to admit the strongest applicants out of fear that they’ll go elsewhere. Shapley and Gale show that the college admissions market is similar to the market for marriage, in which men propose to women, and each individual has views about the potential partners but those opinions don’t perfectly match couples up in an obvious way. Assuming that all proposals come from men, Shapely and Gale showed that to obtain a stable result—one that cannot be improved upon by swapping—the women need to employ a process of “deferred acceptance.”

121015_$BOX_NobelPrize
Is matching up in love a problem of "stable allocation"?

Photo by Joe Raedle/Getty Images.

At first, each man proposes to his favorite woman. Some women will have multiple suitors and some will have none. Rather than accept their favorite proposal, the women need to reject their nonfavorite proposals and just pocket the strongest one without accepting it. Then the rejects can make a second proposal, and if any women find themselves liking their new offer better than the previously pocketed one they can switch their hold. Repeat the process enough times, and, Shapley and Gale proved, the algorithm will lead to a stable match.

Obviously, in the real world this isn’t how marriage works. And extending the simple model to encompass a world that includes gay couples, bisexuality, preference for single life, and the rest of reality is quite challenging. But in school admissions, this kind of algorithm is relatively easy to apply.

It is Roth who showed that the algorithm can be of enormous practical interest. A key element of doctors’ training is the residency in a teaching hospital at the end of medical school. By the 1940s, the residency-matching system had become totally dysfunctional. Desperately seeking the best candidates, hospitals were extending offers earlier and earlier, forcing decision-making to be made on the basis of increasingly weak evidence. Medical schools began to push back by refusing to release relevant information early, but that merely caused hospitals to start making high-pressure offers that required students to make snap decisions without informing themselves about other alternatives. In the early 1950s, the National Resident Matching Program clearinghouse was developed to centralize the process and brought an end to the chaos. In a 1984 paper, Roth showed that the NRMP was working because it had essentially hit on a version of the Shapley-Gale algorithm.

The residency matching program eventually began to unravel, which prompted yet another innovation from Roth. As more women entered the medical profession, a substantial share of residency applicants were members of couples who wanted to be placed in relatively nearby hospitals. The existing pairwise matching algorithm couldn’t process this and the system began to destabilize, with more people opting out. In 1995, Roth was brought in to design an improved system. He and Elliott Peranson developed a revised algorithm that accommodates couples and has been used stably since 1997.

Similar issues have arisen in large urban school districts that have sought to create systems of public school choice, in which family preference rather than accidents of geography determines which schools students attend. In 2003, Roth helped New York City redesign its high-school assignment system and was able to achieve a 90 percent reduction in the number of students who ended up administratively assigned to a school that wasn’t on their preference list. Last but by no means least, these ideas have been applied to the complicated market for kidney donations. You might have a willing donor who isn’t biologically compatible, while a biologically compatible and in principle willing donor may not be willing to donate to you. In the absence of a market for buying and selling kidneys, this means many lives can be saved if multilateral swaps can be arranged. Over time, application of Shapley-style matching algorithms, often with Roth’s involvement, has extended states’ ability to create matches and helped save lives.

Overall, it’s a great Nobel Prize for the reputation of economics. Usually when economists are in the news, it involves high-profile disagreements about political issues related to taxes, the budget, macroeconomic stabilization, and long-term economic growth. Unfortunately, these ideologically charged issues are precisely where consensus tends to be weak and economics often looks like politics plus fancy math. Alternatively, economics is often seen as too abstract and unrealistic or too focused on trivia. But there’s nothing trivial about matching patients with willing kidney donors, or making sure we don’t wastefully assign students to schools they don’t want to attend. These are important policy questions and also real technical problems that can be difficult for people of good will to solve even if they share the same goals and values. The application of powerful mathematics and seemingly abstract models to these problems yields meaningful improvements in people’s lives by ensuring that available resources aren’t wasted. And with or without money changing hands, that’s really what economics is supposed to be about.

Matthew Yglesias is the executive editor of Vox and author of The Rent Is Too Damn High.