The assignment problem for Kidney Paired Donation

Abstract

(EN] For patients with end-stage renal disease, kidney transplant is the best available treatment, but due to graft accessibility and compatibility limitations, fewer transplants than desired are performed. As a solution, F. T. Rapaport proposed in 1986 the idea of a paired kidney exchange with living donors. In this dissertation we present the adaptation of the Top Trading Cycles algorithm of Gale, published in 1974 by L. Shapley and H. Scarf for an economic model of trading, to the paired kidney exchange idea of Rapaport. Such adaptation is due to A. E. Roth, T. Sönmez and M. U. Ünver (2004). Gale’s TTC algorithm allows to achieve an assignation of the kidneys among the patients that ensures the proper utilization of the grafts, the satisfaction of the patients, and the non-manipulability of the mechanism. In this paper we deeply study the main theoretical properties of the algorithm. Later, we implement a C++ program for the mentioned algorithm, and perform 140 simulations, varying the dimensions of the problem and the preference input matrices generated according to real data from the Spanish National Transplant Organization. Finally, we have analysed the results and draw some conclusions and further research.

(ES) El mejor tratamiento disponible para pacientes con enfermedad renal en etapa terminal es el trasplante de riñón, pero debido a las limitaciones en la compatibilidad y accesibilidad de los órganos, se llevan a cabo menos trasplantes de los deseados. Como solución, F.T. Rapaport propuso en 1986 el trasplante cruzado de riñones de donantes vivos. En este trabajo presentamos la adaptación del algoritmo ’Top Trading Cycles’ de Gale, publicado en 1974 por L. Shapley y H. Scarf para un modelo económico de intercambio, a la idea de trasplantes cruzados de riñones de Rapaport. Dicha adaptación se debe a A. E. Roth, T. Sönmez y M. U. Ünver (2004). El algoritmo TTC de Gale permite lograr una asignación de los riñones entre los pacientes que asegura el uso adecuado de los órganos, la satisfacción de los pacientes y la no manipulabilidad del mecanismo. En esta disertación hemos estudiado a fondo las principales propiedades teóricas del algoritmo. Posteriormente, hemos implementado un programa en C++ para el algoritmo anterior y ejecutado 140 simulaciones variando las dimensiones del problema y las matrices de entrada generadas de acuerdo a datos reales de la Organización Nacional de Trasplantes. Finalmente, hemos analizado los resultados y apuntado algunas conclusiones y futura investigación.