- "Absolute Music," Ralf Gawlick and the Hugo Wolf Quartet rehearse Imagined Memories–with additional audio and links (pg.8)
View upcoming events at Boston College
Books by alumni, faculty, and staff
Alumni in the news
Order books noted in Boston College Magazine
Join the online community of alumni
View the current BCM in original format
Using theories of competition, two economists deliver children to schools, employees to their offices, and undergraduates to dormitories
Tayfun Sönmez introduces his class on game theory with Charles Schulz’s classic Peanuts cartoon sequence in which Lucy snatches the football away just as Charlie Brown tries to kick it.
The first choice belongs to Charlie Brown, explains Sönmez, a Boston College professor of economics who is a leader of efforts to put game theory to practical use on real-world problems, such as how to assign students to public schools equitably and arrange kidney transplants for more people who need them.
Charlie can either engage with Lucy—who’s done this to him before, after all—or not. If he chooses not to engage, the game is over. When he does engage, the choice is then Lucy’s. She can either hold the football and let Charlie kick it, or pull it away at the last moment and send him sprawling. If she lets him kick it, the game is over. If not. . . .
Game theory, simply put, is the consideration of outcomes in competitive situations where one person’s decisions both affect and are affected by the choices of the other participants. From Peanuts, Sönmez proceeds briskly to the slightly more complicated contest of rock-paper-scissors, then plunges into a thicket of factors that must be pondered to “solve” games: Look at the game first from the perspective of the final decider, understand what each player receives and risks for each potential outcome, watch out for lies that may arise from players’ attempts to strategize.
Such factors feature prominently in a hot new area of practical economic research that is rising on the highly abstract foundations of game theory. From exploring the “games” that take place for resources within markets, economists have proceeded to designing markets, coming up with rules that facilitate the matching of resources with participants in fair, efficient ways, leaving all parties as satisfied as possible.
Sönmez, his frequent Boston College collaborator Utku Ünver, and colleagues at MIT, Stanford, and a select few other schools have applied principles of market design in particular to markets where the resources—public school slots, kidneys—are not for sale; they continue to work on a broad array of new possible applications, from helping the military assign graduates of its academies and ROTC programs, to organizing job rotations in global corporations.
While their efforts are based on game theory, this is the farthest thing from a game for Sönmez, 46, an intense man who is very clear on his overriding goal: “When I write my papers, I want to understand the math behind these problems,” he says. “I find it elegant, beautiful. But my intention has always been to change the world.” The most important early papers on game theory “were very abstract studies,” he says, but now “we are saving . . . lives.
“I try to formulate problems which have social importance, solve them theoretically, and then approach policymakers,” Sönmez says. That’s what he did when he proposed improving the college admissions process in his native Turkey, where in the not-distant past students were funneled to private and public institutions alike on the basis of a required national exam. The authorities’ disinterest in reform contributed, in a backhanded way, to his being where he is today.
Like many of Turkey’s best students, Tayfun Sönmez and—five years later—Utku Ünver were assigned to Bilkent University in Ankara, widely regarded as the best in the country. And like many others before and after them, both majored in electrical engineering, not because they wanted to be electrical engineers but because that’s the direction in which the national system pushed top students.
Electrical engineering was of no particular interest to either of them—”I hated electrical engineering!” Ünver exclaims—so when they graduated each had to figure out what to do with himself. Both wanted careers that involved mathematics, and both were attracted to the broad range of opportunities for graduate study and research in the United States.
Sönmez landed in the early 1990s at the University of Rochester, where he earned his master’s and Ph.D. in economics under resource-allocation specialist William Thomson. No one was using game theory in practical applications at the time, but the ingredients for making something new were present in Thomson’s work and in studies being done at the University of Pittsburgh by Professor Alvin Roth. “It was very abstract, but I loved [Thomson’s] research program and it interested me tremendously,” Sönmez recalls in an interview in his Maloney Hall office. At the same time, “Al Roth was working on matching problems, which I find very elegant as well. I liked the practicality offered by matching markets. I tried to make my work a synthesis.”
Sönmez would become a major collaborator with Roth, who would later move to Harvard and Stanford and win a Nobel Prize in economics in 2012. Roth shared the prize with UCLA mathematician Lloyd Shapley, who, with the late David Gale, was instrumental in developing cooperative game theory, which considers incentives and rules to satisfy competitors within a closed group. (In a 1962 paper, for instance, Shapley and Gale presented an algorithm for creating stable assigned marriages in a “community consist[ing] of n men and n women.”)
The Nobel committee, in a document explaining the background and significance of Roth’s contributions, gave abundant recognition to work by Sönmez and Ünver, who have researched and written, sometimes with Roth and sometimes with others, on a range of topics important to developing the field of market design.
Game theory and market design have their roots in the 1940s, when the marketplace in which hospitals shopped for medical residents, who form an essential component of hospital workforces, broke down.
Competition for residents had become intense, and some hospitals were offering contracts as far out as two years before medical school graduation, well before they could be sure of the candidates’ abilities. To further secure their staffing needs, they were setting early deadlines for students’ decisions. Medical students were being forced to accept offers before they knew what kind of medicine they wanted to practice and where, feeling they could not risk waiting.
In response, the National Resident Matching Program (NRMP) was created in 1952 to standardize the selection process and establish a uniform date of appointment. The program used a mathematical algorithm based on the rank-ordered preferences of applicants and hospitals; wages were fixed. (The system worked smoothly for several decades—until women began entering the field in growing numbers and students started applying for residencies as two-career couples. At the NRMP’s request, Roth would tweak the algorithm in 1997, largely to address this development.)
In 1984, in work that would be cited by the Nobel committee, Roth observed how the early mechanism that produced the NRMP’s stable residency market in the 1950s served to prove the algorithm theorized 10 years later by Gale and Shapley. The latter formula was “considerably simpler,” Roth observed, but the end results were “equivalent”—even though Gale and Shapley, he wrote, were “unaware” of the NRMP’s practices. It was a case of proof preceding theory, and the connection, the Nobel judges wrote, “led to the emergence of a new and vigorous branch of economics known as market design.”
“Market design is an ancient human activity,” Roth said in a recent telephone interview from Palo Alto. “What’s new is for economists to be able to say something useful about it. As we studied the design of markets, we began to be more confident that we could help when markets weren’t working very well. Tayfun and Utku are wonderful proponents of this.”
In 1995, not long after completing his Ph.D., Sönmez became involved in research that would lead him to reform of the Boston school assignment process. In effect, he was setting sail into a new area of market design called one-sided matching. Much of the work in the field was still abstract at that time, and what was not was almost all two-sided matching, in which both sides of a market—hospitals and residents, for example—had important interests in the outcome. With Boston school assignments it was different. The students receiving the placements had welfare interests that surpassed the schools’ preferences.
From Rochester, Sönmez had moved to an assistant professorship in the economics department of the University of Michigan, where he and a Ph.D. candidate at Rochester, Atila Abdulkadiroglu (now a professor at Duke University), had begun a study of the mechanisms used by public education systems to assign students to schools in Boston, Columbus, Minneapolis, and Seattle.
He continued the work after he returned to Turkey in 2000 to join the economics department at Koç University, a new (est. 1993) and ambitious private institution in Istanbul. There, at Abdulkadiroglu’s strong urging, he recruited Ünver, whom he did not know, and the two men undertook a new study, this one of housing allocations, that later would have an unexpected impact.
When Sönmez sought to extend his school-placement study to the Turkish college admissions system, Turkish officials did not take readily to the assertion that their system was functioning poorly and should be overhauled. But he found willing listeners in Boston.
Over several decades, beginning in the late 1980s, Boston’s method for assigning pupils to schools had become widely accepted in the United States and in Europe. Boston officials boasted that their data showed 90 percent of students were being assigned to one of their top choices. It didn’t feel that way to students and their parents, however, who by the early 2000s were expressing growing frustration and calling for change.
“The Boston mechanism was very broken,” says Sönmez. He and Abdulkadiroglu discovered that Boston’s method, by giving inflexible, absolute priority to students’ stated preferences, actually encouraged students and their parents to lie about those preferences in order to get into the best possible school. For example, a student’s top three choices might be schools X, Y, and Z. If those were all extremely popular schools and the slots were filled by the time the student’s name came up, the student might miss out on all of them. So, she and her parents might decide to say that her fourth-choice school, D, was her top choice, knowing she could get in there.
Not only were many students not attending the schools they truly preferred, the researchers found, but school officials were ignorant of that fact, because the data on students’ preferences of which Boston’s leaders were so proud “had nothing to do with their real preferences,” Sönmez says. “Boston and the other cities were making real decisions based on partially fake data.”
Soon after Sönmez and Abdulkadiroglu’s findings were published in the June 2003 issue of the American Economic Review, they got a call from Boston Globe reporter Gareth Cook. When Cook’s report was published in the Globe, Sönmez, sensing an opportunity to make practical, real-world change, sent copies of the news story and the study to Boston’s superintendent of schools, Thomas W. Payzant, who had members of his staff contact the researchers.
Sönmez offered to work pro bono on the Boston system, using research funding provided by his Turkish university to cover his expenses. In October 2003, he proposed a solution to school department staff that would increase the flexibility of the assignment process, eliminate lying to “game” the system, and produce an increased level of satisfaction.
Sönmez invited Roth to the presentation, and Roth brought one of his students, Parag Pathak, who is now a cutting-edge market designer and professor at MIT. Roth and Pathak joined Sönmez and Abdulkadiroglu in further studies requested by the school department prior to the new system being publicly accepted by the department in 2005.
In their “applicant proposing, deferred acceptance” system, students’ top choices for schools and the school system’s policies for placing students (e.g., granting siblings priority to attend the same school) are fed into a computer program that simulates the matching process.
In the computer, each student “offers” to come to his top choice. Each school “considers” all such offers. If there are more offers than openings, the school “holds” top applicants up to its capacity and rejects the rest. The rejections are final, but the “holds” are not acceptances.
Then, all students rejected in the first round make an offer to attend their second-choice school. Each school considers all the new applicants together with the ones it has been holding. Some of these second-round applicants may have higher claims, based on school-system policies, than those held in the first round, in which case some who were held in the first round will be rejected in favor of second-rounders.
The process continues until no student submits a new offer. At that point, all the assignments are finalized.
In 2003, a similar approach, proposed by Abdulkadiroglu, Pathak, and Roth and tied to somewhat different, homegrown circumstances, was enacted in New York City. Since 2005, U.S. cities including Boston, Denver, and Newark, New Jersey, and every school district in England, have implemented the student assignment mechanism initially proposed by Sönmez.
As is often the way with new ideas, Sönmez and Ünver’s contributions to organizing and broadening the distribution of kidneys offered for transplant started with a wholly different focus—the allocation of faculty offices and student housing.
Generally, kidney exchanges were only made in two situations: In one, there were two patients, each with a willing but incompatible donor (usually a relative or close friend) who was a match for the other patient. Patient A’s donor would give a kidney to patient B while patient B’s donor would give a kidney to patient A. Often the transplants took place simultaneously, to ensure that both donors went through with the bargain.
In the other example, called an indirect (or list) exchange, a patient with an incompatible donor would receive a cadaveric kidney and the donor’s kidney would go to someone high on the waiting list for a cadaveric kidney. (This might seem an uneven exchange, as kidneys from live donors are generally of better quality. But in fact, for some people such an exchange gets them out of a nearly hopeless situation. For example, a person with type O blood might have a willing donor who is type A, and therefore incompatible. Before exchanges, type O patients faced extremely long waits for even a cadaveric compatible kidney.)
“Utku was visiting with Al Roth at Harvard at the time”—this was during the academic year 2002–03—”and Al made the observation that kidney exchange was just starting in the United States, and there were no organized methods or algorithms,” Sönmez says. Sönmez, Roth, and Ünver all observed that the factors involved in creating an efficient program for kidney exchange were strikingly parallel to those they had studied allotting campus offices and housing to faculty and students. On campuses, “every year, people leave, there are newcomers without ownership, stayers with ownership but looking to upgrade, and vacant offices and houses,” Sönmez says. He extended an algorithm contributed by David Gale to a housing-allocation paper published by Shapley and Yale’s Herbert Scarf in 1974 “and that’s how kidney exchange started.”
Sönmez was excited about working in a new area in which elegant mathematical algorithms could be applied to a serious problem and quite literally change the world for people who were suffering. He read everything he could about kidney exchange and transplantation, and understood that increasing the number of indirect exchanges would expand the potential of a system in which direct trades between two pairs had been the rule, extending it to three- and four-way swaps and possibly beyond.
Only a handful of exchanges had been done in the United States when Sönmez, Ünver, and Roth published an article in the May 2004 issue of the Quarterly Journal of Economics exploring the theoretical benefits of organizing and optimizing kidney exchanges through use of a sophisticated resource-allocation algorithm. This was followed in August by a working paper, which they published online through the National Bureau of Economic Research, containing an algorithm for optimizing exchanges.
The three economists joined Francis Delmonico, a Massachusetts General Hospital surgeon and director of the New England Organ Bank, and Susan Saidman, director of the hospital’s histocompatibility laboratory, to found the New England Program for Kidney Exchange in 2004, and sent information about their research to working groups in the Midwest and Mid-Atlantic states.
They also continued to innovate. Their studies convinced medical professionals of the benefits of “chains,” in which an altruistic stranger gives a kidney to the patient of an incompatible pair, and that patient’s paired donor gives to another pair, and so on. If there’s no pair to accept a particular kidney within a suitable time frame, the organ goes to an unpaired patient on the cadaveric waiting list and the chain ends. The longest chain to date stretched from California through the Midwest to New Jersey and involved 60 people and 30 transplants between August 15 and December 20, 2011. The success of chains has convinced researchers and doctors that simultaneous operations are not essential.
As a result, the practice of kidney exchange has taken off. The innovations in this country produced 93 transplants in 2006 that would not otherwise have been performed, 553 in 2010. Sönmez estimates the total could reach 2,000 additional transplants a year. The mechanisms the researchers created are used today not only in the United States, but also in much of Europe and in Hong Kong, Korea, and Australia.
As excitement about his work on school assignments and kidney exchanges spread in the early 2000s, Sönmez decided to return to the United States to live and work. Boston was the logical locale given his involvement with the school system and the medical community.
Boston College learned of his intentions through Hideo Konishi, a graduate-school colleague at the University of Rochester who had joined the Boston College economics faculty in 1999. Sönmez’s autumn 2004 job-market seminar—the presentation a candidate for a professorship gives to his would-be department—left some saying it was the best they had ever attended.
“It was very different from the typical seminar,” recalls Marvin Kraus, who was chair of the department at the time. “Part of the reason people were so impressed was that, unlike nearly all economists, he managed to get all these ideas across without showing us a single equation. Usually we are shown dozens of equations.
“It was also a remarkable presentation from the standpoint of the exposition,” Kraus says. “Rarely or never before had we heard the exposition of economic theory that had the potential to save human lives. We were really struck by the potential benefits.”
Current economics chair Donald Cox says, “It was the most amazing thing I had ever seen. I was stunned. By the end of the seminar, people were hanging on every word. Anytime someone talks to me about academic economists being removed from reality now, I can just tell them about Tayfun.”
During the courtship, Kraus says, “even before we made him an offer, Tayfun started extolling the virtues of Utku,” who, after earning his B.S. in the Bilkent electrical engineering department, studied under Roth at Pittsburgh before being recruited to Koç. Ünver returned to America via an assistant professorship at the University of Pittsburgh in 2005, the same year Sönmez received his appointment to Boston College. Among other projects, Ünver collaborated with Roth and another economist on a study of the net benefits to college football of the post-season matching system started by the Bowl Championship Series. In 2008, an opening occurred at Boston College and Ünver came to the Heights.
“The obvious complementarity between him and Tayfun played a big role,” Kraus says. “We thought Boston College could really put itself on the map in a very significant way in this exciting new area of matching theory.” As Sönmez puts it, Boston College “is good at hitting target opportunities.”
Since 2008, the two economists have broadened and deepened their explorations of market design. Sönmez has an upcoming publication on how the U.S. military can better match the priorities of its branches with the assignment desires of ROTC and military academy graduates. Ünver is studying the significance of timing in matching markets, exploring, for example, how an algorithm could be designed to create smooth and satisfactory rotations of international assignments within global corporations.
Roth praises Sönmez and Ünver’s desires to tackle real-world problems, and credits the two with insights that have been important to strengthening and refining researchers’ understanding of matching markets and design.
“We think of Boston College as one of the centers of matching and market design because of them,” he says.
Charles A. Radin is a Boston-based freelance writer.