The Visible Hand

On the first day of classes in September, most of the 18 people gathered for Al Roth's course in market design were doctoral students in economics or business. One was studying computer science. A visiting scholar from Beijing thought the class might help her understand problems in the nascent Chinese market for fine art. Roth, shirtsleeves rolled up and chalk in hand, took them through the algorithm he's deployed to redesign the processes by which medical students get matched with residency programs and children in large cities get assigned to public schools.

At its essence, the algorithm systematizes courtship. Roth demonstrated how it processes mate preference lists from men and women given names like m1 and w3 to determine when pairs can do no better and should get hitched. "Romantic," one student deadpanned. Roth smiled broadly, thought for a moment, and said, "Yes, romantic. This class will take the romance out of a lot of things," adding a quip about the academic job sector for new economists, another sector he's worked to re-engineer.

Nonetheless, it seemed clear that Roth, MS '73, PhD '74, is nobody's caricature of a coldly calculating economist. A month later he would win the Nobel Prize in Economic Sciences for analyzing and designing marketplaces in which money alone can't solve the problem of allocating scarce resources efficiently and fairly. The allocation of donated kidneys, which are illegal to buy and sell, is the most dramatic example. But even when money is involved, prices don't always determine who gets what. Universities like Stanford can't just auction off their freshman slots to the highest bidders, Roth likes to say. Both sides in these "matching markets" care whom they pair up with. As in marriage, you can't simply choose your mate—you also have to be chosen.

The idea that markets need designing seems at odds with the widespread belief that markets develop best organically, without central planning. But, as Roth once wrote, "markets don't always grow like weeds—some of them are hothouse orchids." Stock markets, for example, have rules against insider trading. And even farmers' markets designate operating hours. People created these rules because they make marketplaces work better.

Even so, it's extraordinary to see an economist go beyond building elegant models, or studying how theories play out in a messy, complex world, to implementing real solutions. Through his collaborations with people outside academia, Roth is the rare scholar whose work is as much at home in the New England Journal of Medicine as in Econometrica, and he belies preconceptions about economists as equation-scribbling eggheads. Neil Dorosin, a former New York City school official with whom Roth continues to work on school-choice systems, puts it this way: "Al has published papers that have some wonky math in them, but what he does that is so wonderful is that he's always asking, 'In what ways can I apply this work?'"

As a teenager in Queens, Roth entered a science honors program at Columbia University, soon enrolling in college there without finishing high school. For grad school, he came to Stanford to study operations research, which at the time seemed like the right move if you had a head for math and wanted to make things work better. But he grew disenchanted with queuing and inventory theory. Game theory—which deals with situations in which the best decision depends partly on the decisions of other people—sounded more fun. Back then, Robert Wilson, now a professor emeritus at the Graduate School of Business, was the only game theorist on campus, so he became Roth's adviser.

In his dissertation, which Roth now sees as a dead end in his research, he dealt only with the theory in game theory. But as a young professor at the University of Illinois, he put theory to the test, working with social psychologist Keith Murnighan. Roth says he was far from the first economist to do experiments—which, though true, understates his pioneering work, particularly his investigations of bargaining and fairness. "Al has been doing experiments almost since the beginning of his academic career," says Muriel Niederle, one of several of Roth's students now teaching at Stanford, noting that such studies were uncommon at the time.

In the 1980s at the University of Pittsburgh, Roth came to study matching markets such as the one for medical residencies. In the first half of the 20th century, hospitals would select medical students for residencies (then called internships) earlier and earlier—as soon as two years before graduation from medical school. Nobody particularly liked this timing—neither the hospitals, which knew less about the candidates than they would if they waited longer, nor the students, who at this early stage may not yet know, say, whether they have the stomach for surgery. Hospitals were forced to make increasingly early offers just to keep up with their competition, in much the way retailers start pre-Christmas sales as early as October. Students had to play along or lose their chance for a match. As Roth would later describe this type of market failure, the market for residencies was gradually "unraveling."

Hospitals eventually created a centralized matching system to coordinate hires around a single date. This system, the National Residency Matching Program (NRMP, or "the Match"), fixed the unraveling problem. In studying why the Match worked so well, Roth made a remarkable discovery. Although introduced in 1951, it used a matching process equivalent to an algorithm developed a decade later by prominent game theorists David Gale and Lloyd Shapley. Shapley would share the Nobel with Roth; Gale died in 2008.

Gale and Shapley proved that given two separate sets of players ("two-sided matching"), this algorithm always achieves a stable matching. That is to say, no two players would prefer each other over their assigned partner. Put another way: You may not be thrilled with your match, but whether you're most people's first choice or everyone's last, you couldn't have done any better by going around the system. To achieve this stability, the Gale-Shapely algorithm uses a process of "deferred acceptance" which lets both sides weigh all their options before committing.

Photo: Linda A. Cicero/Stanford News Service

While stability is an important property, Roth explored a different question: how to get honest information about who wants what. "And what I showed is that you can't have a system that will always make everyone want to tell you the truth, but you can have one side of the market do so." In a system where students make the proposals while hospitals accept or reject them, students have an incentive to reveal their true preferences. The Match, however, was doing the opposite: It used a hospital-proposing system. Its matches were stable, but not necessarily in the best interests of the students.

Several years later, after Roth and a postdoc named Marilda Sotomayor published a book with theorem after theorem about two-sided matching, Roth got a phone call from the NRMP. The matching design that had worked so well was showing signs of trouble, and the administrators wanted Roth to study the problem. "I still remember the phone call and the visceral feeling I had," Roth recalls, "which was 'Why are they calling me?'" The theorems of Roth and Sotomayor made many simplifying assumptions, so the only parts of the book that directly applied to redesigning the Match were actually counterexamples.

Near the top of the NRMP's list of problems: As more women went into medicine, couples increasingly were applying for residencies together. And because the Match wasn't doing a good job of meeting their needs, many were sidestepping the process and finding jobs on their own. The Match was also fraught with political problems, including suspicions that the process enabled hospitals to exploit medical students.

Roth spent a lot of time trying to convince student organizations that he was a technocrat rather than a hack in the pocket of a corporate conspiracy. You cannot succeed in design projects, he says, without a champion on the inside. Projects in which economists swoop down and impose their own rules are bound to fail. His simulations—one of many tools he uses to hone his designs—showed that switching from a hospital-proposing system would help students without hurting hospitals. So student-proposing deferred acceptance became part of the new Match design. He also successfully tweaked the Match to enable couples to express joint preferences and showed that, although stability wasn't guaranteed in all cases, in practice the process worked just fine, as couples comprised a small subset of the applicant pool.

In 2003, by which time Roth had moved to Harvard, he got his second call for design help—this time from the New York City Department of Education. Mayor Michael Bloomberg had wrested control of the city's hundreds of schools away from community school boards, and his staffers sought to bring order to the chaotic process of applying to public high schools.

At the time, an eighth grader would send in a single application, which the district copied and forwarded to multiple schools. But the admissions process itself was decentralized: Each principal decided which students to invite. As a result, thousands of students would receive multiple offers, while many more would get none, sitting on several waiting lists until their peers had made their decisions and freed up spots. Because all this back-and-forth was gumming up the pipeline, by August of each year some 30,000 students still hadn't gotten a single offer, and come September, tens of thousands were being assigned without any regard for where they wanted to go.

The person in charge of the process, an administrator named Jeremy Lack, didn't see a way out, but he recognized that his problem resembled the one Roth had solved in the medical Match. Roth enlisted the help of economists Parag Pathak, Atila Abdulkadiroglu and Tayfun Sönmez; one of the cleverest things they did in their redesign was to switch to a single best-offer system. "If you don't give 17,000 kids multiple offers, you can give everybody an offer," Roth says.

As sensible as that sounds, parents resisted, says Neil Dorosin, who took over after Lack left. "If you stand in front of a group of parents and say we're going to use a single best-offer system, the most common criticism is 'You're taking away choice from us.'" Because the whole point of preference lists is to enable families to express their choices at the outset, the parents' concern seemed unwarranted, but Roth and his team took it seriously. "You wouldn't want to be the guy who drove the last middle-class family out of the city's public schools," Roth says. "So we looked at the data and asked: What happens to those kids who got multiple offers? And overwhelmingly they were taking the place they'd ranked the highest."

For the new scheme to work well, though, the clearinghouse needed to know each school's true capacity, and under the old system it didn't. "Because the system was so clunky and wasn't producing stable matchings," Roth explains, "if you were a principal, you'd say to yourself, 'Why should I tell them how many places I have? Because in the end they'll slam 30,000 kids into schools and I'll get some of those kids, instead of kids I chose.'"

New York's school matching process is still imperfect. About 10 percent of students remain unmatched after the main round, leaving many eighth graders in tears at being rejected by every school on their list. But in the very first year after the redesign, the number of students who were unmatched in August fell by 90 percent. Roth and colleagues have since redesigned school-choice systems across the country, including Boston, New Orleans and Denver, and continue to tackle systems in other cities.

Roth sees market design problems everywhere, and uses his daily blog (whose entries are usually time-stamped around 5 a.m.) to catalog them. The blog's tone is remarkably neutral for someone who knows as much about market design as Roth does, offering neither snark nor solutions. Roth says this is because designs that work require studying a problem in all its real-world detail, and he says it takes him a decade to believe he knows the answer.

His failed attempt to stem the unraveling in the market for judicial clerkships is a case in point. "The problem facing judges and clerks looks a lot like the problem that faced doctors and residents, but the culture of the market is very different," Roth says. Law students and judges alike often believe a student can't say no to a judge, and for good reason: The federal courts system is a small world, so for law students applying for clerkships the shadow of the future looms much larger than for med students facing the Match. "If you practice medicine in Massachusetts, and you had disappointed an important doctor who lived in San Francisco, sometimes you'd see him at your national conference, but you wouldn't be pleading cases before him."

Though his closest colleagues say Roth is one of a kind, he acts as if he's anything but special. He'll have you believe he skipped years of school because he was "too impatient," that his students are smarter than he is, and that his wife, Emilie, a cognitive psychologist who helps design command centers and control rooms, is the one with the really interesting job. When you point out this pattern of deflecting attention, he'll respond with yet another self-effacing remark, saying you've hit upon one of his personality flaws.

Many people with willing donors languish on kidney transplant waiting lists because of incompatible blood type and various immune factors. So it was exciting news when, in 2000, two women in Rhode Island, neither of whom could receive a kidney from her own children, were each able to get a kidney from the other's son. (The two-way exchange used four surgical teams operating in concert.) Inspired by this triumph, other transplant surgeons started to orchestrate such swaps among their own patients.

But finding these reciprocally compatible donor-recipient pairs was hard. "I just had a bunch of pieces of paper on my desk, trying to match up patients, and that's how we were all doing it," says Jeffrey Veale, the surgeon who directs UCLA's transplant exchange program. This method wasn't just cumbersome; it was yielding results that were far from optimal. Surgeons were "picking the low-hanging fruit," Veale says—going with the first matches they could find, rather than those that would create the most transplants overall.

Computers would be much better at finding the best set of matches from a vast number of possible combinations, but designing the software to do that is not a routine programming task. It requires creating the right incentives for patients, donors and doctors. Roth and economists Tayfun Sönmez and Utku Unver undertook the design challenge and ultimately helped form the first kidney exchange, a small network of transplant centers in New England. "Thanks to guys like Al Roth and powerful software," Veale says, "we were able to put all our incompatible pairs in there and just hit a button and the computer would spit out the answer."

Transplant surgeons laud Roth these days, but in 2004, when he and other economists first started talking to doctors, persuading them to listen was an uphill battle. "They'd never met an economist and couldn't imagine that someone who didn't even know how to take out a kidney, let alone install one, could have anything interesting to tell them on the subject," Roth says. He did come to work closely with transplant surgeons, especially Michael Rees of the University of Toledo, who was instrumental in the development of NEAD chains, a pay-it-forward system of kidney donations set off by a single non-directed donor. (See sidebar.)

As kidney exchanges expanded, a new challenge arose, though it came as no surprise to economists: Hospitals would send their hardest-to-match patients to the exchange while keeping easy matches for themselves. (Game theorists know it as the free-rider problem.) The temptation to do so is one of many factors complicating the market for kidneys, and the waiting list for a kidney transplant has actually grown over the years. "We've won many victories, but we're losing the war," Roth says. So he's trying to fight it on other fronts, including figuring out ways to increase donations from both living and deceased donors. He's begun working with Stanford Medical Center transplant surgeon Marc Melcher to study the data coming out of the nation's largest kidney exchange, the National Kidney Registry, of which Melcher is head of research.

One of Roth's most intriguing ideas concerns what he calls "repugnant" transactions: those that some people might like to engage in but that others don't want to allow. One of his favorite examples is the French ban on dwarf-tossing, which one dwarf unsuccessfully argued was infringing on his human rights by restricting his employment. Roth argues that repugnance constrains markets in much the way that concern about perceived price-gouging constrains sellers from setting prices high enough to prevent shortages.

Interestingly, some otherwise acceptable or even admirable activities—such as kidney donation—have a way of becoming repugnant when money is introduced. People who find kidney sales repugnant don't just think it's a bad idea, Roth likes to say, but think it's the kind of bad idea that only bad people have. Roth has no moral objection to people selling one of their kidneys, but he's not convinced it's a good idea either. Open to experiments that would gauge the relative magnitudes of good and bad effects from such sales, he takes a consequentialist stance. "I'm a practical guy," he says.

Roth often ends his public lectures with a discussion of repugnance, asking those who believe people should be allowed to sell a kidney whether the sale of other body parts should be allowed. Should a person be able to sell an eye? What about a heart? For his first lecture of the market design class, though, he ends on a lighter note, sharing a line from one of his favorite stories in the Talmud. A Roman matron asks a rabbi what God has been doing since Creation, to which the rabbi replies, "Matching up couples."

On his blog, Roth retells the full story, which one of his doctoral students had professionally calligraphed for him as a parting present. The matron scoffs that the matching task is trivial and sets out to prove it. She calls up a thousand male slaves and a thousand female ones and arranges them in two rows. Thus arbitrarily matched, the pairs are sent away for one night. By morning, the discontented couples beg to be unhitched.

It's a cautionary tale of overconfidence—yet coming from Roth, who sees economics as a field in its infancy, the story also carries an optimistic message: If there's an infinite expanse between utter ignorance and divine omniscience, that's a whole lot of room for exploration, for discovery and for ever better design.

Marina Krakovsky, '92, is co-author of Secrets of the Moneylab: How Behavioral Economics Can Improve Your Business.