ARTS & FARCES internet

Three Carnegie Mellon computer science researchers, Tuomas Sandholm, Avrim Blum, and David Abraham, have developed an algorithm for matching altruistic kidney donors with recipients. Say you’re an end-stage renal disease patient on the waiting list for a cadaver kidney. Your spouse wants to donate one of his kidneys to you but isn’t a match. Instead, your spouse donates to a matching recipient selected by the Carnegie Mellon software, becoming an altruistic donor. If everyone plays fair, someone down the line matches you and altruistically donates an organ.

This chain of matching altruistic donors with best-case recipients goes on, in theory, forever.

For those waiting for kidneys—right now that’s close to 75,000 folks—this is potentially a lifesaver. Live donor organs are qualitatively better than cadaver kidneys and last year alone, almost 4,000 folks died waiting for a kidney.

Tuomas Sandholm got the idea during a game theory conference where economist Alvin Roth lectured about paired exchange, an arrangement by which two kidney patients with willing, but incompatible, donors swap organs with each other. But the idea didn’t scale to a national network. The computers ran out of memory calculating the matches between 600-900 pairs of patients with willing donors.

Sandholm, Blum, and Abraham built an algorithm capable of handling the billions of calculations necessary with a national registry of thousands of patients and donors:

“To bypass the computer memory limitations, the Carnegie Mellon trio created an algorithm that attacks the matching problem incrementally through a technique called column generation. That means that at no given time are all of the potential cycles in the computer’s memory together. In addition, rather than examining every possible solution, the algorithm can decide when it is headed in the wrong direction and stop itself from exploring paths unlikely to produce the optimal cycle of matches—a method known as ‘branch-and-price.’”

Last year, Roth’s team discovered that “allowing for exchanges among more than four donor-patient pairs doesn’t substantially increase the number of transplants that can be arranged.” That gave the Carnegie Mellon algorithm the ability to make the best match even earlier. As of June the algorithm is capable of analyzing 10,000 patient-donor pairs.