Finance & Development, December 2014, Vol. 51, No. 4

Maureen Burke

PDF version

Tour Roth's lab
Roth on repugnant markets

Maureen Burke profiles Nobel laureate Alvin E. Roth, who uses game theory to make people’s lives better

Alvin Roth still recalls his visceral reaction in 1995 when he got the call from Bob Beran of the National Resident Matching Program. The “Match”—a clearinghouse that annually pairs thousands of newly minted U.S. physicians with jobs—was looking for someone to direct its redesign.­

“Why me?” Roth remembers thinking, with an uneasy feeling. He knew, of course, why Beran had sought him out. Roth had written a book on matching and studied many market failures that preclude demand and supply from working accurately, including in the medical labor market. His investigation of clearinghouses and optimal matchups—such as between brides and grooms or doctors and hospitals—had earned him prominence in his field.­

But as a theorist, he had not needed to worry about the details of implementing a mechanism to ensure a stable match, as optimal pairing is called. It had been enough to identify problems in the process. If he agreed to redesign the Match, though, he would have to find solutions.­

This project marked Roth’s first venture into the real-world practice of market design, for which he would win the Nobel Prize in economics with Lloyd Shapley in 2012.­

Physician, heal thy market

Roth had studied the market for new doctors. He knew that in the 1940s, competition for scarce medical students compelled hospitals to offer residencies to students increasingly early in their schooling, sometimes more than a year before graduation.­

Clearly broken, the system was revised a few years later when medical schools agreed not to release information about their students until a certain date—but then, new issues emerged. Students on the waiting list for their first-choice hospital balked at accepting offers for their second choice, holding out as long as possible. As a result, waiting lists remained static until the very end of the selection period, when decisions were often made in haste. And when an offer was ultimately rejected, it was often too late for the hospital to make offers to other desirable candidates.­

The process of matching new doctors and hospitals had become a messy process that displeased both medical students and their potential employers. To better align the preferences of medical students and hospitals, the Match—which paired students with hospitals using rank-order preference lists from both sides—was introduced in the early 1950s.­

But there were new problems. The number of female medical students had grown dramatically, and many couples who met in medical school requested residencies in the same city. The Match could not accommodate these requests, so many people simply circumvented it, which signaled a breakdown in the system.­

Roth agreed to refine and modernize the program and, together with Elliott Peranson, developed the mathematical procedure, or algorithm, that is still used today to match up new doctors and employers. The algorithm has been adopted by over three dozen labor market clearinghouses.­

Matching markets

Economists traditionally study markets where prices adjust so that supply equals demand. But Roth is a game theorist who specializes in “matching markets”—markets in which changes in price alone do not clear the market. Participants can’t just choose what they want, even if they can afford it; they also must be chosen. Think college admissions or the dating market.­

A pioneer of a new branch of economics called market design, Roth uses the mathematical tools of game theory to fix systems whose market mechanism has failed. Market designers have a clear-cut task in markets without prices, because if price is not playing a signaling role, there has to be another mechanism for clearing the market. Economists like Roth help design these mechanisms.­

Market designers try to understand “the rules and procedures that make various kinds of markets work well or badly,” Roth explained in a 2007 article in the Harvard Business Review. “Their aim is to know the workings and requirements of particular markets well enough to fix them when they’re broken or to build markets from scratch when they’re missing.”

Much of Roth’s work builds on theory initiated by Shapley. In awarding the Nobel, the Royal Swedish Academy of Sciences cited the pair for “the theory of stable allocations and the practice of market design.” Shapley is generally credited for his theoretical contribution and Roth for putting the theory to practical use.­

The deferred acceptance algorithm—proposed by Shapley and David Gale in their 1962 paper “College Admissions and the Stability of Marriage” published in The American Mathematical Monthly—underpins this work.­

This algorithm looks at how 10 women and 10 men can be paired up, based on the individual preferences of each. Women can propose to men, or men can propose to women. In the more traditional scenario, the process begins with each man proposing to the woman he likes the most. Each woman then looks at the different proposals she has received (if any), retains what she regards as the best proposal (without yet accepting it), and rejects the others.­

The men who were rejected in the first round then propose to their second choices, while the women again keep their most attractive offer and reject the others. This continues until no men want to make any further proposals. Each of the women accepts the proposal she holds, and no further iterations are needed. Gale and Shapley proved mathematically that this algorithm always leads to a stable matching—that is, one in which no couples would break up and form new matches that would make them better off.­

Roth has used variations of the algorithm to match students to schools, law clerks to judges, and more. “Markets help people live their lives better,” Roth says simply. “We should improve them when we can.”

Problem child

Alvin Roth was born in 1951 in the New York City borough of Queens. His parents, first-generation Americans, taught typing and stenography in the public high school system. Roth was always “a bit of a problem child,” he claims. Unhappy in school, he dropped out at age 16.­

At the time, he was enrolled in Columbia University’s Science Honors Program, which held math and science classes on Saturday mornings for gifted youth from the New York City area. With the help of people associated with the honors program, he was admitted to Columbia’s undergraduate engineering program without a high school diploma. He graduated in three years with a bachelor’s degree in operations research.­

“Who knew that I didn’t mind taking classes and learning? But I didn’t like high school very much,” Roth says. “We weren’t a good match.”

Roth moved to Stanford University in 1971 to pursue a PhD in operations research, sometimes described as a scientific approach to managing complex systems. There, he gravitated toward game theory, his interest sparked by a class with visiting professor Michael Maschler from the Hebrew University of Jerusalem. Roth also connected with Bob Wilson, a game theorist who taught at the Stanford Business School and became an important mentor.­

Roth’s dissertation solved a problem that had been raised 30 years earlier in mathematician John von Neumann and economist Oskar Morgenstern’s seminal Theory of Games and Economic Behavior, the book that started the field of game theory. Roth downplays this accomplishment, saying the whole topic turned out to be a dead end. But dead ends are not necessarily bad, he adds. “The field has made a lot of progress by exploring dead ends.”

Before leaving California to take up a teaching position at the University of Illinois at Champaign-Urbana, he made a pilgrimage of sorts to visit Shapley, then an eminent game theorist at the RAND Corporation, a think tank in Santa Monica. The young Roth didn’t know Shapley, but because the field was so small in those days, seeking out its leaders somehow made sense. “It wasn’t hard to get the idea that, if you proved a new theorem in game theory, then you should go tell Shapley about it.”

The boundaries of the discipline, meanwhile, were shifting. “Shortly after I got my PhD in 1974, it looked like game theory was going to thrive as a part of operations research. But it didn’t—it thrived in economics,” Roth says.­

At Illinois, where Roth was appointed at the age of 22 as assistant professor in the departments of Economics and Business Administration, he began doing experiments in game theory with psychologist colleagues, among them J. Keith Murnighan.­

Murnighan, now a professor at Northwestern University’s Kellogg School of Business, remembers Roth as brilliant. “For a while he worried that he wouldn’t have any great ideas after he turned 25,” given the tendency of mathematicians to peak young, Murnighan says.­

Roth found, after a time, that the two professions had divergent views on how to test game theoretic predictions in a laboratory. But his interest in experimental economics has endured, and he continues to view laboratory work as an important way of testing assumptions about behavior.­

“If you’re a game theorist, rules are data. One of the things I want to know about a market is, what are its rules and what are the newest rules?” Roth explains. “Because when you observe people making rules, you suspect that they’re observing some behavior that they’re trying to moderate.” This, in turn, gives the researcher a window on the market and provides clues as to what the market’s optimal design might be, he says.­

Kidney exchange

In 1982, Roth moved to the Economics Department of the University of Pittsburgh, while his wife Emilie—a cognitive psychologist he’d met at Illinois—started a job at the Westinghouse Corporation’s Research and Development Center in Pittsburgh.­

Their 16-year stay in Pittsburgh overlapped with a couple of notable events. The University of Pittsburgh Transplantation Center—one of the world’s preeminent transplant hospitals—opened in 1985, led by Thomas Starzl (for whom it is now named), often called the father of organ transplantation. A few years later, Boston surgeon Joseph Murray won the Nobel Prize in medicine for performing the first successful kidney transplant.­

It’s not surprising that, around that time, the problem of matching patients needing a kidney transplant with transplantable kidneys caught Roth’s attention.­

By the early 2000s, hospitals had begun to perform a limited number of live kidney exchanges involving two donor-patient pairs, In these exchanges, the patient in each of two incompatible patient-donor pairs was compatible with the donor in the other pair, allowing each patient to receive a kidney from the other’s intended donor.­

Still, there was a considerable shortage of kidneys. In 2002, more than 55,000 patients were on the waiting list in the United States for deceased donor kidneys. About 3,400 patients died while on the waiting list, and another 900 became too sick for transplantation.­

Roth—by then at Harvard University—penned a 2004 paper with Utku Ünver and Tayfun SÖnmez in which they argued that the number of transplants could rise substantially if there were an “appropriately designed clearinghouse” that drew from a database of incompatible patient-donor pairs. Their proposal, published in the Quarterly Journal of Economics, involved exchanges with no restrictions on number.­

They sent the paper to several surgeons, but only one—Frank Delmonico, then the Medical Director of the New England Organ Bank—responded. Their work with Delmonico resulted in the formation of the New England Program for Kidney Exchange, which brought together 14 kidney transplant centers across the region.­

But despite the success in organizing kidney exchanges, Roth noticed that the number of surgeries arranged by the New England Program for Kidney Exchange was growing much more slowly than expected. “I worked with a colleague of mine, Itai Ashlagi of the Massachusetts Institute of Technology, to try to figure out what was going on,” Roth says. In the general patient population, more patients are easy to match than hard to match. But when they looked at who was enrolling in the exchange, they saw fewer easy-to-match pairs than expected and far more than expected hard-to-match pairs.­

“What was going on was something game theoretic,” says Roth. “When we started the kidney exchange, we were mostly dealing with patients and their surgeons, but as kidney exchange became a regular part of American transplantation (although still at a small level), the players changed, and the important players became the directors of transplant centers.”

But directors of transplant centers have different strategies than individual surgeons, because they see many more patients and donors, explains Roth. “What they [directors] were starting to do was withhold the easy-to-match pairs and match them internally at their hospital, and only show us the hard-to-match pairs.” This was a problem that could be fixed, but it was a politically tricky one, Roth says.­

“But that’s one of the fun things about market design,” Roth observes. “Not only is the market not exactly the way we conceived of it when we wrote our initial paper, but the fact of having a market has actually changed it.”

Increasingly, Roth says, kidney transplants are organized through what are known as “nonsimultaneous chains,” in which a long chain of transplants can take place over time, initiated by an altruistic donor who is willing to donate a kidney but does not have a particular recipient in mind.­

The chain starts when this donor gives a kidney to a patient whose willing donor is healthy but immunologically incompatible. The would-be donor of the first recipient then donates a kidney to a sick patient in another incompatible pair, and so on, until the chain ends, sometimes with the last donor giving a kidney to a patient on the waiting list. Such chains, which have involved up to 60 people, allow donation programs to reach far more people than the original exchanges.­

Potential for organ sales?

Of course, the kidney shortage might be greatly reduced if these organs could be legally bought and sold, some believe. The human body can function just fine with one kidney. Done correctly, therefore, donation is a low-risk procedure that can save lives. So the widespread reluctance to consider monetary markets for kidneys is something Roth is keen to understand better.­

Buying and selling kidneys is illegal everywhere except in Iran, where there appears to be no shortage of kidneys. “That strikes me as a big data point that we ignore at our peril,” Roth says.­

“It could be that, by explaining carefully how a well-regulated market could bring the benefits of voluntary exchange between consenting adults, we could move in that direction,” he adds. “But when you see something that’s against the law nearly everywhere, you also have to think that maybe there’s some obstacle to it, even if you haven’t completely understood it yet.”

These differing attitudes toward organ sales and other “repugnant transactions”—transactions some people favor but others want banned—have led Roth to study this phenomenon in more depth (see box).­

Roth spent almost as long in Cambridge as in Pittsburgh— 14 years—dividing his time between Harvard’s Department of Economics and the Harvard Business School (HBS).­

“At Harvard, I occupied two offices and crossed the Charles River twice almost every day, as I would walk from HBS to Economics and then back to get on my bike or in my car for the trip home,” Roth wrote in his autobiographical statement on nobelprize.org. “It was a short walk, but it sometimes felt like a big change in perspective. As a market designer I was glad to be able to work on both sides of what sometimes seemed like a wide river, between theory and practice and simple abstraction and messy detail.”

During this period, in addition to the work on kidney exchange, he helped redesign school choice systems for public schools in New York City and Boston, using a modified form of the deferred acceptance algorithm. He also helped fix the U.S. entry-level labor markets for gastroenterologists and PhD economists, among others. Roth has written about each of these cases in detail, revealing the myriad ways markets can unravel.­

And he does so in an amazingly accessible way.­

“Al has remarkable skill at taking economic concepts and explaining them to laymen,” observes Parag Pathak of the Massachusetts Institute of Technology, who studied market design under Roth at Harvard and later worked with him on redesigning the school choice system in New York City. “He was able to translate our ideas into a very digestible piece that the Department of Education could then use to explain to its constituents why it was changing the system.”

“It’s really easy to get lost in the world of science—to create your own world and stay detached from reality,” says Atila Abdulkadiroglu, an economics professor at Duke University who also worked with Roth on school choice. “With Al, he always asks, who is this research going to benefit outside the scientific community?”

In summer 2012, Roth returned to Stanford after nearly 40 years—but this time to the Economics Department, as the Craig and Susan McCaw Professor of Economics. (He remains an emeritus professor at Harvard.)

A few months later, Roth was awarded the Nobel—something he termed “a great honor” but which resulted in an onslaught of email, as well as speaking engagements and other commitments. “After a year of heavy travel, I began to worry that I would be condemned to forever talking about work I had done long ago and not about the work I was doing then,” he joked.­

The prize did help resolve one piece of unfinished business, though. After learning of the Nobel, his high school, Martin Van Buren, in 2014 granted him a high school diploma—albeit an honorary one.­ ■