Researchers create a mathematical model that helps transplant centers make decisions about when to move forward with a matching donor and when to wait.
Based on research by Süleyman Kerimov
Researchers create a mathematical model that helps transplant centers make decisions about when to move forward with a matching donor and when to wait.
To wait, or not to wait? That is the question — or at least it might be, if you need a kidney transplant. Nearly 89,000 Americans with chronic kidney disease are on a waitlist for a new organ, and an estimated 13 people die each day while awaiting a transplant. But there are real costs to matching patients with the first donor that becomes available, just as there are equally real costs to having them wait in hopes of finding a better one.
Recently, Rice Business professor Süleyman Kerimov and colleagues at Stanford University and Northwestern University developed a mathematical model that helps clarify when it's best to match patients to donors as quickly as possible and when it's best to wait.
Their findings, which appear in two papers published in Management Science and Operations Research, respectively, could help optimize all manner of matching markets in which participants seek to connect with potential partners based on mutual compatibility — a sprawling category that encompasses everything from e-commerce platforms to labor markets that match employees with employers.
Kerimov and his colleagues focused on programs that match live kidney donors with people who need transplants. Live donors typically volunteer to give one of their kidneys to a loved one. But biological differences between a donor and their intended recipient can render the pair incompatible.
Kidney exchange programs solve this problem by swapping donors amongst different patient-donor pairs, choreographing a kind of kidney-transplant square dance aimed at finding a compatible partner for every willing donor.
In countries such as Canada and the Netherlands, kidney-matching programs perform a batch of matches every few months (called periodic policies). American programs, meanwhile, tend to perform daily matches (called greedy policies). Both models seek to produce the greatest number of high-quality transplants possible, but they each have advantages and disadvantages.
Less frequent matches in a periodic policy allow more patient-donor pairs to accumulate in the kidney exchange network, creating potential for better matches over time. But this approach risks making some patients sicker as they wait for a better match that might never appear.
Arranging feasible matches as soon as they become available in a greedy policy avoids that predicament. But it means passing up the opportunity to make a potentially better match that could represent the possibility of a longer, healthier life.
Balancing these trade-offs is tricky. There is no way of predicting precisely when a patient-donor pair with a particular set of characteristics will show up at the kidney-exchange network. And in the world of organ transplants, there are no do-overs.
Kerimov and his colleagues have constructed a mathematical model that represents a simplified version of a kidney exchange network.
Within the model, the researchers could dictate which patient-donor pairs could be matched with one another. They can also assign different values to individual matches based on the number of life years they provide. And they can establish the probability that various kinds of patient-donor pairs with particular characteristics might arrive at the network and queue up for a transplant at any given time.
Having set those parameters, the researchers applied different matching policies and compared the results. As it turns out, the answer to whether one should wait or not is: It depends.
To determine which policies generated the best outcomes — i.e., performing matches either daily or periodically — the researchers calculated the difference between the total value in life years that could possibly be generated within the network and the amount generated by a specific policy at a particular point in time. The goal was to keep that number, evocatively dubbed "all-time regret," as small as possible over both the short and long term.
In their first paper, Kerimov and his team explored a complex network in which donor kidneys could be swapped amongst three or more patient-donor pairs. When such multiway matches were possible, the cost of applying a daily-match policy turned out to be onerous. Using all available matches as quickly as possible eliminated the chance of later performing potentially higher-value matches.
Instead, the researchers found they could minimize regret by applying a periodic policy that required waiting for a certain number of patient-donor pairs to arrive before attempting to match them. The model even allowed the team to calculate precisely how long to wait between matchmaking sessions to get the best possible results.
In their second paper, however, the team looked at a simpler network in which kidneys could only be swapped between two donor-patient pairs. Here, their findings contradicted the first: Applying a daily-match policy minimized regret; a periodic matching process yielded no benefit whatsoever.
To their surprise, the researchers discovered they could design a foolproof algorithm for making two-way matches in simple networks. The algorithm employed a ranked list of possible match types; and the researchers found that no matter how many patient-donor pairs of various kinds randomly arrived at the network, the best choice was always simply to perform the highest-ranked match on the list.
In future research, Kerimov hopes to refine the model by feeding it data on real patient-donor pairs that have participated in actual kidney exchange programs. This would allow him to create a more realistic network, more accurately calculate the likelihood that particular kinds of patient-donor pairs will show up, and assign values to matches based not only on life years but also on rarity and difficulty. (Certain blood types and antibody profiles, for example, are rarer or more difficult to match than others.)
But Kerimov already suspects that in a real-world situation, the wisest course of action will be to alternate between periodic and greedy policies as circumstances dictate. In a simple region within a kidney exchange network that only allows for two-way matches, pursuing a greedy policy that involves taking the first match that appears on a fixed menu of options would be the best choice. In a more complex region that allows three-way matches, however, pursuing a periodic matching policy that involves waiting to make rarer and more difficult matches would ultimately offer more patients more years of healthy life.
The benefits of choosing flexibly between greedy and periodic policies should hold for any kind of matching market that can be represented by a network with simpler and more complex regions, such as a logistics system that matches online orders to delivery trucks or a carpooling system that matches passengers with drivers across different parts of a city.
Süleyman Kerimov is an assistant professor of management – operations management in the Jones Graduate School of Business, Rice University.
To learn more, please see: Kerimov, S., Ashlagi, I., Gurvich, I. (2021). Dynamic Matching: Characterizing and Achieving Constant Regret. Management Science. https://pubsonline.informs.org/doi/10.1287/mnsc.2021.01215
Kerimov, S., Ashlagi, I., Gurvich, I. (2021). On the Optimality of Greedy Policies in Dynamic Matching. Operations Research. https://papers.ssrn.com/sol3/papers.cfm?abstract_id=3918497
