Here’s a fantastic idea. Computer scientists at Carnegie Mellon University thought that two-, three- or four-way barter exchanges might improve kidney donor/recipient matching. Lo and behold, they were right! A recently presented paper “Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges” has proven just that:
The matching algorithm makes it possible to create matches for three- and four-way exchanges–that is, three or four donors matched to three or four recipients–as well as two-way exchanges. It is the first that is scalable so it can be used for a national pool of donors and recipients, said Tuomas Sandholm, professor of computer science.
A paper detailing the algorithm, developed by Sandholm, Computer Science Professor Avrim Blum and graduate assistant David J. Abraham, will be presented Friday at the Association for Computing Machinery’s Conference on Electronic Commerce in San Diego.
The Alliance for Paired Donation, a kidney exchange program for 50 transplant centers in 15 states, began using the matching algorithm in December. The Alliance director, Dr. Michael Rees of the University of Toledo Medical Center, said it improves on previous methods both by including three- and four-way exchanges and by factoring in so-called altruistic donors–kidney donors without a specified recipient.
For instance, in a match run in early May, the algorithm identified four potential two-way exchanges, three three-way exchanges and one four-way exchange among about 100 donor-patient pairs and seven altruistic donors. Whether any of those transplants take place will depend on factors such as final compatibility testing, Rees said. With the same set of donor-patient pairs and without altruistic donors, the matching method previously used by the Alliance would have identified only one two-way exchange, he added.
About 140 paired kidney donations have occurred in the United States since 1999, Rees said. These paired donations can happen when a friend or loved one is willing to donate a kidney to a patient but is found to be incompatible. When possible, a paired donation is then arranged, in which donor A is incompatible with recipient A, but can donate to recipient B, and donor B can donate to recipient A.
Sandholm said the number of transplants could be increased by expanded use of three-way exchanges–donor A gives to recipient B, donor B gives to recipient C and donor C gives to recipient A–and four-way exchanges. Numbers could also be increased by enlarging the pool of donor-patient pairs, he added.
Several regional exchanges are in operation and the possibility of a national exchange has been discussed. Rees predicted that in perhaps five years a national pool could include 3,000 donor-patient pairs and accumulate 1,000 to 1,500 pairs each year. Potentially, as many as 2,000 transplants could be performed from a pool of this size if three- and four-way exchanges are arranged, he said. But existing matching algorithms can arrange only two-way exchanges for such a large pool, and current algorithms capable of arranging three- and four-way exchanges can handle no more than 600 to 900 pairs.
The paper (.pdf)…
Press release: Carnegie Mellon Scientists Devise Method To Increase Kidney Transplants …