Kybernetika 44 no. 3, 373-384, 2008

Pareto optimality in the kidney exchange problem

Viera Borbeľová and Katarína Cechlárová


To overcome the shortage of cadaveric kidneys available for transplantation, several countries organize systematic kidney exchange programs. The kidney exchange problem can be modelled as a cooperative game between incompatible patient-donor pairs whose solutions are permutations of players representing cyclic donations. We show that the problems to decide whether a given permutation is not (weakly) Pareto optimal are NP-complete.