How can Computer Science help match transplant patients with donors?

Worldwide, thousands of patients require a kidney transplant. Some patients may have a friend or relative willing to donate a kidney but bloodand tissue-type problems may make that donation impossible.

A Kidney Exchange Programme (KEP), in which all patient-donor pairs are placed in a pool, to enable donors to be swapped, is one solution, and increasingly countries are starting to collaborate on such programmes to increase the number of successful matches.

However, this brings many obstacles, not least ensuring fair participation and benefit for each country.

Calculating fairness

Research involving Professor Daniel Paulusma in our Department of Computer Science has looked at how an international KEP could ensure fair participation and benefit, and in particular prevent countries from only registering their hard-to-match pairs.

The researchers have developed a new credit-based system. It uses concepts originating from Cooperative Game Theory as the basis for calculating fair shares of the total number of available kidney transplants in a matching round for each participating country.

A country that was at a disadvantage in one matching round would receive compensation in the next round, to level out discrepancies and remove the incentive not to register easy-to-match pairs.

Algorithms and opportunities

The team undertook numerous computational experiments to make sure the system could work. They developed efficient algorithms for calculating the fair shares, and for finding a kidney transplant schedule that results in a fair distribution of the total number of available kidney transplants.

The new model offers KEP coordinators more opportunities to agree international kidney transplant schemes, which could result in more patients being treated.