Inapproximability of the kidney exchange problem

To overcome the shortage of kidneys available for transplantation, several countries have started various programmes of kidney exchanges between incompatible patient–donor pairs. This situation can be modeled as a cooperative game in which the players are the patient–donor pairs and their preferences are derived in the first step from the suitability of the donated kidney and in the second step from the length of the obtained cycle of exchanges. Although the core of such a cooperative game is always nonempty and one core solution can be found by the famous Top Trading Cycles algorithm, many questions concerning the structure of the core are NP-hard. In this paper we show that the problem of finding a core permutation that maximizes the number of patients who obtain a suitable kidney is not approximable within n1−ε for any ε>0 unless P=NP.