Cross-over kidney transplant increases the chances of finding compatible donors and the survival of patients. According to 2019 data, Spain, the United Kingdom and the Netherlands are the countries in Europe with the most well-established programmes. However, there is room for improvement. That is what a team of economists and mathematicians has done. Using game theory, they have developed an algorithm to improve the allocation of donors and patients. Their work has earned them an award from the BBVA Foundation.

Paired kidney exchange programmes are a ‘market’ for exchange, although there is no economic benefit and participation is completely altruistic. These programmes increase the possibility of finding a compatible donor by crossing donor and recipient pairs. Two incompatible donor-recipient pairs can generate an exchange if the donor of one pair is compatible with the recipient of the other, and vice versa. That is, if the donor of couple A is compatible with the recipient of couple B, and the donor of couple B is compatible with the recipient of couple A, a direct exchange can take place.

However, such exchanges are not necessarily limited to just two couples. It is possible to organise exchange cycles involving three or more couples. For example, in a three-partner cycle, the donor of partner A can donate to the recipient of partner B, the donor of B to the recipient of partner C, and the donor of C to the recipient of partner A. In addition, there is the possibility of generating exchange chains. These chains depend on the participation of a ‘Samaritan donor’, a person willing to donate a kidney without having a specific recipient in mind. This altruistic donor initiates the chain by donating his or her kidney to a recipient in a match, whose donor in turn donates to another person in a new match, and so on.

From time to time, paired kidney exchange programmes perform a ‘matching’ process, in which they try to find the best combination of exchange cycles. The aim of the process is to identify and combine exchanges (as closed chains) so that the total number of transplants performed is maximised.

As Flip Klijn, economist and director of the Institute for Economic Analysis of the CSIC (IAE-CSIC) explains, there are quite a few factors to consider in the exchange: histological and blood compatibility, the patient's age, the urgent need for the transplant, whether there are other diseases that may compromise the success of the transplant, and so on. Some of these factors carry more weight and are more relevant than others, and may limit the number of transplants done in each cycle.

Esquema de ejemplos de combinaciones en trasplante renal cruzado.

Research by Flip Klijn (CSIC Institute for Economic Analysis), together with Péter Biró (Corvinus University of Budapest), Xenia Klimentova and Ana Viana (both from the Institute of Engineering, Technology and Systems and Computer Science, INESC TEC, Porto), has used game theory to propose an algorithm that quickly provides beneficial allocations in cross-over transplant. The authors of the study demonstrate mathematically and through simulations that the algorithm is more equitable than the usual algorithms. More specifically, the proposed algorithm generates allocations that ‘respect the improvement contributed by the participants’. The work, which appeared in the journal Mathematics of Operations Research, recently received the award for Best Applied Contribution to Operations Research in the SEIO-FBBVA 2024 Awards.

The algorithm could also be applied to other areas of exchange, such as time banks or Erasmus scholarship programmes.

Respecting improvement and incentivising new entrants

The research seeks, based on classical game theory solutions, a mechanism that respects the improvement, or what could be defined as the effort made by the participant. In this way, more people are encouraged to participate in the cross-over transplant programme. Above all, it seeks not to ‘punish’ participants who have made an effort to improve the exchanges.

Let’s imagine, Flip Klijn illustrates, a situation in which, when allocating kidney exchanges, it is discovered that the matches are weak. ‘Suppose, in order to improve this situation, one of the patients seeks out and provides new potential donors - he has made the effort to seek them out from family members, close friends, etc. The new donors are of universal blood type (0) and are more compatible, so it is improving the situation and giving more opportunities for all. So, in making the new allocation, it would not be fair that the participant who has made that effort should receive a worse allocation than before (less compatible).

‘Our goal has been to find a mechanism that can be applied systematically and that guarantees a maximum number of cross-over transplants while ensuring stability and respected enhancement,’ says Klijn. The methodology has been tested in simulations based on data recreated from renal exchange programmes.

The study shows that, when renal exchange programmes are large enough, compatibilities can be taken into account and the respected enhancement property can be guaranteed to a large extent, without a significant reduction in the number of transplants.

The algorithm could not only be applied to cross-over kidney transplant programmes (its implementation would require the involvement of other specialists, especially from the clinical and healthcare sector), but could also be applied to other exchange settings, such as time banks or Erasmus scholarship programmes.

Artículo de referencia:
"Shapley-Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange". Klijn, Flip, Péter Biró, Xenia Klimentova and Ana Viana,  Mathematics of Operations Research. https://doi.org/10.1287/moor.2022.0092