The mathematics of matching kidneys

“Kidneys are unusual organs,” says the blogger and academic Michael Trick, “We are given two, though we can get by with one. So, unlike the heart, say, we each have a 'spare' that we can donate to others.” Indeed, for patients suffering from kidney failure – known more technically as end stage renal disease – one option is transplantation: taking somebody else’s healthy kidney and grafting it in the patient. In the United States, there are estimated to be more than 60,000 patients waiting for such transplants to happen. Kidneys of deceased as well as living donors can be used, and both approaches have their pros and cons. But transplants involving living donors are increasing – in the United States they are 47% of all transplants.

If a transplant involves a living donor, then who might such a donor be? Perhaps someone close to the patient – a sister, a relative, a friend. But it turns out you can’t just use any kidney. You can accept a kidney only if your blood group and the donor’s are compatible. An O recipient can accept only O kidneys; A can accept O and A; B can accept O and B; and AB can accept any kidney. And there may be other medical reasons and patient preferences too that may disallow certain transplants.

So, from the above discussion, you may end up with an incompatible donor-recipient pair, and this frequently happens in practice. But this is not a dead-end; what you can do is find another incompatible donor-recipient pair, such that the blood group of the donor in the first pair is compatible with that of the recipient in the second pair, and vice-versa. If this is the case, an exchange can happen, as shown below.

Figure 1 (Picture from here)

Both pairs are now set. Simple enough. But if you look at this from the larger, societal point of view, the problem is more nuanced. There may be thousands of such incompatible donor-recipient pairs in the waiting list. If you just go from the point of view of one pair, you are likely to find a match, but you may end up ruining options for others.

How can this happen? Well, let’s look at this simple example involving just five pairs. Each pair is represented using a node, while the edges indicate that an exchange is possible. So an exchange of the type shown in figure 1 is possible between pairs 1 and 2; 2 and 3; 2 and 4; 4 and 5. Since there is no edge between 1 and 5, the pairs cannot exchange – this might be, say, because the donor of 1 belongs to blood group B but the recipient of 5 belongs to O, ruling out an exchange.

Figure 2 (mine)

Now let’s look at possible solutions. If 2 decides to exchange with 4, then only one match is possible. Three other pairs (1, 3 and 5) will have to wait for future pairs to enter the list – until then, the recipient in each pair will be on dialysis, which is extremely expensive. But there exists a better solution: let 1 exchange with 2 and let 4 exchange with 5. Four pairs now get matches, and only one pair has to wait. Thus the latter solution maximizes the number of matches in the graph, while the former solution leaves many dissatisfied.

Imagine now that there are thousands of pairs with myriad linkages – as there indeed are in reality. Can you visually think of a graph of the type above and come up with a solution? Clearly, it’s not feasible – unless we develop the superhuman ability to delineate complex and dense graphs in our minds and traverse them. Fortunately, though, the matching of kidneys turns out to be equivalent to a well studied problem in graph theory called maximum matching. Even better, there exists an algorithm that will give a solution in quick time no matter how large your graph is. Got a thousand pairs in your list? No problem – you’ll get a solution in a few seconds! The algorithm was first proposed way back in 1965, in a groundbreaking paper by Jack Edmonds. Edmonds clearly was not into sleep-inducing technical titles that are the norm in most publications: his paper is stylishly called Paths, Trees and Flowers [1] and can be accessed easily online.

Thus did the solution to a puzzle in graph theory become relevant for a pressing medical problem of today – and it is not always possible to see such happy marriages. Not that this one is perfect: the kidney matching problem in reality is not as simple as the maximum matching problem of graph theory. Medical problems – especially transplantations – are riddled with ethical, political, logistical and cost issues. Despite this, the kidney matching problem (or the paired donation problem) is something to be celebrated. It’s a neat, easy-to-understand application, and its importance can’t be overstated.

Picture from here

The problem became known in the medical community due to a paper in the prestigious Journal of the American Medical Association (JAMA) [2]. Sommer Gentry and Dorry Segev were the principal researchers. If graph theory in an organ transplantation context seems like a unique marriage, then is it any surprise that it emerged from an actual marriage - between a mathematician and a transplant surgeon? Sommer is the mathematician; Dorry the surgeon. I met Sommer at a conference in Philadelphia last year, and chatted with her over lunch (which is how I became aware of the problem). She is currently at the US Naval Academy, while Dorry is a surgeon at John Hopkins; they live in Anapolis, near Baltimore.

But to return to the paper. There is an extensive discussion in it about the challenges that come up in kidney transplantations: national vs. regional matching, logistical issues, and how to deal with patients with greater need. The national vs. regional question is especially worth mentioning. Local and regional kidney donation programs already exist in the United States, but what if a national system was to be tried out? Clearly the availability of a larger pool of kidneys would mean more matches. But then travel and the cost of transporting organs becomes an issue. But here's the twist: the paper demonstrates that in the national system, the number of matches would increase and yet only 2.9% of the national pool would actually need to travel. Who would have guessed! But this is precisely the sort of counterintuitive insight that a mathematical model is capable of providing.

Finally, why have we discussed only 2-way exchanges so far? Indeed, we can do better. Let's consider three pairs. The donor of Pair 1 could donate to the recipient of Pair 2; the donor of Pair 2 then donates to the recipient of Pair 3; and lastly, to complete the cycle, the donor of Pair 3 donates to recipient of Pair 1. That's a 3-way exchange. Perhaps longer ones can be identified in a pool but what effect does the length of a cycle have on the number of matches in the overall pool? This is a fertile area of research, and some it has already been implemented. Recently, at the Johns Hopkins Hospital in Maryland, there was a six-way exchange – the largest of its kind – involving twelve people. And the cycle of six was completed because of an altruistic donor who was unrelated to the twelve people involved, yet gave away his/her kidney.

Indeed, if you are going to have an impact on twelve rather than two, wouldn’t you be more inclined to be altruistic?

References

[1] Paths, trees and Flowers, by Jack Edmonds, Canadian Journal of Mathematics (1965).

[2] Kidney paired donation and optimizing the use of live donor organs, Segev D., Gentry S., Warren D., Reeb B., and Montgomery R. Journal of the American Medical Association (2005).