'Bipartite matching' is the classic mathematical exercise of making pairs in messy bunches of things, such as matching job seekers to jobs, buyers to online ads, or online daters to each other. This method is at the heart of better market design. It's also increasing the odds of medical miracles. At LIDS and MIT's Operations Research Center (MIT-ORC), post-doc Vahideh Manshadi solves matching problems for a very specialized marketplace—one that ultimately enables more people to access life-saving kidney transplants.
More than 102,500 people are currently waiting for kidney transplants in the U.S. Only about 17,000 people receive kidney transplants each year, and about 4,500 don't get their transplant in time. In the face of kidney shortages, people often offer to donate an organ to a friend or family member in dire need. Unfortunately, about a third of the time, the donor and recipient are incompatible in either blood type or immune profile, resulting in a never-ending flow of hard-to-match patients. Yet, the methods designed by applied economic researchers like Vahideh provide the elegant solution of finding viable transplant matches between complete strangers.
"It's an opportunity that might not be case for other organs," says Vahideh, referring to the revolutionary practice called 'kidney exchange' in which a living donor gives one of her two healthy kidneys to a stranger in order to secure another kidney for her loved one. More specifically, the simplest exchanges involve two or three patient/donor pairs, for all of whom the intended transplant is impossible, but for whom the patient in each pair could safely receive a kidney from a donor in another couple. These "pay-it-forward" surgeries enable two or three recipients to receive healthy kidneys.
The first exchange was performed in Korea in 1991, but it was almost a decade until they were successful in the United States, initially here in New England. Over the past eight or so years, hospitals such as Johns Hopkins and Mass General have performed increasing numbers of them.
Vahideh, a native of Iran, recent graduate of Stanford University, and happy new Bostonian, discovered her ability to optimize these life-saving exchanges in the space of three hours at a 2011 workshop held by the Association for Computing Machinery (ACM) in San Jose. There, she met two of her future influences: Itai Ashlagi of the MIT Sloan School of Management and Harvard economist Alvin Roth (now at Stanford). The two researchers had planned the workshop to get the computer science community interested in improving the logic behind organizing kidney transplants.
Kidney exchanges that involve more than a simple two-pair swap require complicated matching algorithms, which have proven very effective in practice. Around the time of the San Jose meeting, the algorithm used by the National Kidney Registry was making news. In fact, it led to 175 successful transplants in 2011, including the 30-person chain of exchanges known as 'Chain 124,' the biggest exchange performed to date and featured in the New York Times: "60 Lives, 30 Kidneys, All Linked."
Thanks to her work in the Stanford Operations Research group, Vahideh was used to thinking about matching problems with dynamic features, i.e. problems in which the settings change over time. Obviously, kidney exchanges are dynamic: incompatible pairs arrive and enroll in exchange centers gradually over time, and these centers need to make matches in a time-sensitive manner. The insight came easily to her. "I realized the core problem they were trying to solve was basically a dynamic matching problem," she says.
When forming a closed loop of matches, all of the transplants have to be performed simultaneously, and this limits the number of pairs that can be in a cyclic exchange to 2 or 3. Now, real-life examples of kidney exchanges such as Chain 124 are proving the power of using a novel exchange method called a 'chain.' A chain kicks off with an altruistic donor (an extra kidney not part of a pair), allowing the donations to continue on longer as the National Kidney Registry's algorithm finds matches in the constantly growing pool of pairs. "However," says Vahideh, "there have not been rigorous studies of how to design exchanges in dynamic settings." With that in mind, Vahideh visited Itai Ashlagi at MIT and told him her ideas about optimizing matches. It wasn't long before she, Itai, and Patrick Jaillet, her current advisor at LIDS, formed a team uniting LIDS and MIT-ORC.
Arranging a kidney exchange involves a tricky trade-off. "You want to have as many transplants as possible, but you also want to keep people happy, meaning they don't wait too long and get acceptable kidneys," says Vahideh. Theoretically, the longer a center waits, the more data the algorithm can work with to produce matches. But waiting exacts a huge cost because people are on dialysis, and there's more time for donors to renege on their offers. For Vahideh, Itai Ashlagi, and Patrick Jaillet, their central question is the same question that all kidney exchange centers have: how long should we wait before arranging the exchange? One week? One month?
Recently, Vahideh and her colleagues took a hard look at the waiting problem to figure out when longer waiting periods to facilitate a kidney exchange would be worth the risk. The group analyzed an algorithm close to those used in practice today, running computer simulations with two years worth of confidential data from kidney exchange centers. This approach allowed them to consider antibody profiles and look at how the chances of finding compatible matches change as pairs join over time. They were able to confirm that certain policies are a good idea, and some are not.
For example, Vahideh found that if a center is limited to arranging 2-way exchanges and cannot afford to wait long enough, then an immediate (online) arrangement is a good solution. "If you need to match using only two-pair loops in an exchange, waiting one week won't buy you much," she says. "Even moderate waiting isn't helpful for simple two-way matches." Of course, if a center can afford to wait a couple months, then it would arrange significantly more transplants. But Vahideh's group found that no exchange comes close to the benefit of dynamic 'chains' similar to 'Chain 124.' Even when the center cannot wait, these chains are extremely effective choices.
According to Vahideh's work, the harder option is the best choice. While dynamic chains are difficult to initiate because the hospital must procure an extra kidney and operating rooms must coordinate surgery timings across the country, the transformative medical practice is worth it. "Complex structures have a huge benefit," says Vahideh. "You have more freedom and finding matches is easier."
The rare mix of theory and practice at LIDS has given Vahideh the chance to do something she never did at Stanford—working with real data in her optimization models. It's possible for an optimization researcher to focus entirely on theoretical models that only simulate reality. But there's something about incorporating real-word data that compels Vahideh. "What I find fascinating," she says, "is that you can do deeply mathematical probabilistic work, test it on real data, and see that it can be of use in real problems. Any recommendations we can make for kidney exchange programs matter."
Indeed, improving the logistics of kidney exchange means perhaps endless solutions. Exchanges involve kidneys from living instead of deceased donors, which dramatically decreases the chances of organ rejection or early organ failure. It's good for government finances, too. Medicare saves around $500,000 to $1 million each time a patient is able to stop dialysis after a live donor transplant.
For Vahideh, a certain spirit of freedom enables her work at LIDS. "My advisor, Patrick Jaillet, let me find something I really wanted to do," she says. "It motivates me that you can go out and find something you care about." The academic freedom, open and welcoming attitude among LIDS' faculty, and endlessly available resources at surrounding institutions such as Harvard and Microsoft, are the keys to Vahideh's productivity and success. It could also be that here in the home of the very first national kidney exchange, her theoretical work has never come this close to reality.