Mathematics of kidney transplant matching

Right now, there are more than 70,000 people on the waiting list for a kidney transplant in the US alone. Sometimes, a family member will offer to donate a kidney to a relative. That's a really amazing thing to do. The problem is that one-third of the time, the match isn't right. But what if the donor, say, from one family, is a good match for the recipient in another family, and vice versa? According to Science News, researchers at the United States Naval Academy and Johns Hopkins University hope to address this with a mathematical method to "match up the maximum number of donors with recipients while simultaneously guaranteeing high compatibility in each case." The technique is based on graph theory, a way to model the relationship between pairs of objects. From Science News:
 Articles 20070901 F8797 2553 (US Naval Academy mathematician Sommer) Gentry expects that if there were a national registry in place for kidney matching, and if it used her team's method, then each month, about half the pairs in the registry would find a compatible match. Each year, 1,000–2,000 patients would get kidneys who currently would not.

By contrast, as of 2005, only 51 patients had ever received kidneys through a swap in which two incompatible pairs exchange donors to create compatible pairs. Gentry calculates that developing a national registry could save $750 million per year, because dialysis, the only alternative to transplantation, is very expensive.


  1. I know many people don’t want to “degrade” human life by bringing in capitalism, but it works for a reason. If organs were bought and sold on the marketplace, you would see a great reduction in shortages.

    The real tragedy is government preventing people who consent, to make such trades. Which leads to some people dying who would otherwise have lived.

  2. Please delete my anonymous comment above – I have now activated my account.(curse those spam filters)

    Is a person needing a kidney only allowed to recruit one potential donor or more than one – say family and close friends?

    Then, what if more than one of that person’s “team of donors” is a match for someone else in the network? Do they all drop out of the ring once the first donation is made?

    Can a person needing a kidney “bank” a donation from one of their team or must the donations all occur simultaneously (or within a month)?


  3. For those interested in the computation: the algorithm here can be fairly simple as the graph is bipartite (each vertex is either a donor or a recipient). Thus we can establish a minimum-cost maximum match (perhaps with some cost threshold, where cost is some composite of compatibility, distance, urgency, etc..) in polynomial time – even using very simple techniques like Ford Fulkerson,

  4. Some answers for karnuvap:

    A recipient has one potential donor at most going through the process at a time. The process is pricy (typing plus medical suitability) & so insurance companies pay for only one at a time.

    If a match is identified with a different recipient & the match the other way works as well, the operations are done simultaneously to reduce the chance that only one of the operations goes through (donors back out, donors or recipients become medically incapable of proceeding..).

    The discussion at the link includes a link to another paper that computes 3-way exchanges. More then that is considered impractical because of the need for all the operations to occur during the same short period of time.

    -Jim (I almost donated a kidney & learned a lot).

  5. Actually, the graph isn’t quite bipartite. For one thing, the goal is to find matching donor/recipient pairs, where the donor of one pair can give a kidney to the recipient of the other pair, and vice versa. You don’t want, for example, a volunteer to be used but the recipient they’re representing not to receive a kidney in return.

    There’s two ways to model this:

    1. Let donors and recipients be vertices, and add an edge between a donor and a recipient if either the donor has volunteered on behalf of a recipient, or if the donor is a good match for the recipient. Then, search for 4-cycles in the graph. Exercise to the reader to show that a 4-cycle must consist of two volunteer donor/recipient pairs where the donors can cross-transplant the recipients (assuming that a volunteer donor cannot help the recipient s/he is paired with).

    2. Let a vertex consist of a donor and (one or more) volunteers associated to that donor. Add edges between two vertices if any of the volunteers in one vertex would be a match to the recipient in the other vertex, and vice versa. Then find a maximum matching.

    A noble use for graph theory, to be certain.

  6. Totally randomly, I happen to know Sommer Gentry and Dorry Segev, two of the scientists who developed this process. They also happen to be two of the country’s best lindy hoppers. Sommer’s big project when she was at MIT was creating a robotic arm that could accurately lead lindy hop. You can see them dancing in a contest here, although I imagine being a great dancer pales in comparison to this kind of work.

    It’s really great to see how they’re making the world a much better place by creating this system.

  7. Ahh – I misunderstood the problem. I figured that a matching could be “ragged” (with donations possibly being made for “credit” in hopes of a future match). But I suppose requiring matches to be full cycles (to use your first model) makes more sense realistically both in terms of human nature and logistics.

  8. I hesitate to comment on this, as I am one of the 70k waiting for a kidney. However, it seems to me that a simple change would clear up a lot of backlog: Opt-out instead of opt-in.

    Meaning, instead of asking the relatives of the person in a suitable medical position (basically, brain dead with good organs) for permission, the gov’t assumes permission unless that person went to the effort to deny it at some point in their lives.

    As for myself, I’ve been on the list for four years and have no acceptable family donors. My expectation, given the current system, is to receive a transplant within the next two years.

  9. If as a policy matter, we believe that organs will be “priced too low”, the government can step in with subsidies. Add $100,000 for every kidney. Of course, that will dramatically increase the number of transactions …

  10. In response to Dave’s comment (#7):

    I donated to a friend about 3 years ago. When I started the process, your question didn’t occur to me, but as test after test and screening after screening went on, I began to worry about if I ever ended up on the other end of the transplant.

    According to the hospital, the doctor, and several websites, living donors get moved to the front of the line for transplants. It’s not a law, but it is policy for the transplant medical community. Kind of a ‘pay back’ for putting yourself in the situation to help someone else that went through their system.

    So that’s a nice safety net that I hope I’ll never need to use.

  11. @Jim (#5)

    “The discussion at the link includes a link to another paper that computes 3-way exchanges. More then that is considered impractical because of the need for all the operations to occur during the same short period of time.”

    I’m at Hopkins, and they did a 5-way transplant last year. One altruistic donor and four family donors that were not a match for their relative but a match for someone else in the chain. The operations were all completed in the same day.

  12. Well, I sure hope it’s a long life expectancy…

    I was told (and researched to confirm this) that I could expect a normal life span after I donated. And I’m counting on it too.

    There are lots of things that I didn’t know before I donated that I would have liked to know. It wouldn’t have changed my mind, but still.

    For example, I can’t take Ibuprofen or most anti-inflammatory medicines anymore. And I was put on a migraine medicine last year that really messed up my efficiency of kidney function. So it’s something that I have to be aware of. But nothing has made me think “Man, I wish I hadn’t done that”.

    It’s not something to be taken lightly, but I survived it physically, mentally, and emotionally and the recipient is doing great. So I feel good about it.

Comments are closed.