Stanford engineers develop algorithm to aid kidney transplant exchanges
A historic and complex kidney exchange between Israel and Abu Dhabi put a spotlight on the Stanford algorithm that made it all possible.
A historic kidney transplant exchange recently took place in the Middle East, but it might never have transpired without an algorithm developed at Stanford by Itai Ashlagi, a Stanford associate professor of management science and engineering, and his graduate student Sukolsak Sakshuwong. In all, three ailing recipients received life-sustaining transplants while three healthy donors gave kidneys. In kidney transplant lingo, such complex transactions are known as a cyclic exchange.
In this particular cycle, an Israeli woman donated one of her healthy kidneys to an ailing recipient in Abu Dhabi. Meanwhile, the daughter of the Emirati recipient donated one of her healthy kidneys to a different Israeli woman in need of a transplant whose healthy husband proved to be a match for the first Israeli donor’s mother, who also needed a transplant.
This exchange was historic not for its complexity, but for transcending what is perhaps the most complex challenge of all – politics. This was the first such exchange between Israel and an Arab nation, a transaction that was only made possible by the Abraham Accords, the historic peace agreement signed in August 2020.
Without the peace treaty and Ashlagi’s collaboration with the Alliance for Paired Kidney Donation and Israel Transplant, the Israelis and the Emiratis likely would never have known about each other and the complex matching would have been a longshot, at best.
Ashlagi works in a field of engineering focused on optimization. It is common, if not expected, that much of an engineer’s effort goes into optimizing systems and processes – a kilogram shaved here, an extra volt eked out there, a millisecond trimmed over here. As optimization challenges go, however, none may be so weighty as that of matching kidney transplant donors and recipients. The consequences are, literally, life-altering.
“In the U.S. there are some 100,000 patients awaiting kidney transplants and recipients can wait years for a donation,” said Ashlagi, who is an expert in marketplace design and game theory.
Many patients on the waiting lists have a healthy friend or a relative who is willing to be a living kidney donor, but the donor and would-be recipient are often biologically incompatible. But such a pair can potentially be part of an exchange with other incompatible pairs so that each of the patients receives a live donor kidney.
Ashlagi helps bring these people together with an algorithm that helps doctors and hospitals make these complex exchanges. Often, in the past, they had to be done by hand, on paper. It’s no easy thing. In addition to the complex biology of blood typing and tissue matching, which includes factors like blood type, antibodies and even the patient’s age and proximity to one another, the team must also wrestle with data-related challenges to permit the various hospitals in an exchange to share information easily and with confidence.
At the most basic level, Ashlagi and others in his field view kidney exchanges as a marketplace. Not in the crude monetary sense, like an auction or stock exchange. Ashlagi, in fact, offers his algorithm for free and receives no royalties or other compensation for its use. But it is a market nonetheless in the sense that it matches supply and demand. The currency in Ashlagi’s market, however, is measured not in dollars and cents but in years of life restored to people with serious illnesses.
“One of the nice things in the software we developed is the user interface. We collect all the relevant patient data, but then we let the user play with the various thresholds that determine successful matches to see what works for them,” Ashlagi said as he explained the team’s game-like approach to matching. The software acts as a platform and allows different organizations to easily collaborate and create more possibilities for exchanges. “Just a few days ago, I was looking for matches and found an unexpected exchange between pairs from Israel and other European countries. Hopefully, this will lead to new collaborations.”
“I rewrote the application from the ground up making the user interface intuitive and consistent so hospitals can use it without assistance from us,” said Sakshuwong, who worked with Ashlagi on the program’s unique interface and made it extremely simple to use. Ashlagi acknowledged Sakshuwong’s important role: “I was fortunate to meet him, and he took the work to a new level I hadn’t anticipated.”
Sakshuwong also added key features like tools to help visualize the networks of patients and donors and the inclusion of brief explanations why certain matches might be more compatible than others.
“Research has shown that this work results not only in more matches but also better matches,” Sakshuwong said.
Finding a set of optimal chains is computationally challenging.
“Limiting exchanges to include just three or four pairs can actually be computationally harder than imposing no limit at all. Our algorithms can find optimal combinations within seconds,” Ashlagi explained.
“Itai’s software was used on both sides of that historic exchange between Abu Dhabi and Israel,” said Alvin Roth, Nobel Laureate and Ashlagi’s mentor and frequent collaborator, who was in Abu Dhabi in connection with the exchange.
Roth says Ashlagi exemplifies the concept of scientist-engineer and is now a driving force in contemporary kidney exchange through both his deep understanding of the immunological issues of matching kidneys to patients and his intimate appreciation of the needs of transplant centers.
“He’s turned those practical theoretical insights into widely deployed digital tools with the power to change lives,” Roth added. “Having the chance to collaborate with him has been among the best experiences of my intellectual career.”
The software and algorithms are now used in numerous leading exchange programs in several countries, including the Methodist Hospital in San Antonio, the largest single-center program (which has facilitated more than 500 transplants), and the Alliance for Paired Kidney Donation, a national program with about 30 hospitals.
Roth is the Craig and Susan McCaw Professor at Stanford and senior fellow at the Stanford Institute for Economic Policy and Research.
To read all stories about Stanford science, subscribe to the biweekly Stanford Science Digest.