The kidney exchange problem: How hard is it to find a donor?

The most effective treatment for kidney failure that is currently known is transplantation. However, the supply of kidneys from cadaveric donors does not meet the fast‐growing demand and the kidney from a willing living donor (genetically or emotionally relative of the patient) is often not suitable for immunological reasons. Therefore in several countries attempts have started to organize exchanges of kidneys between incompatible patient‐donor pairs. On the theoretical side, game‐theoretical models have been proposed to analyze various optimality criteria for such exchanges and various search schemes have been tested. One possibility to model patients’ preferences is to take into account in the first step the suitability of the donated kidney and in the second step the length of the obtained cycle of exchanges. Although the core of such a cooperative game is always nonempty and one solution can be found by the famous Top Trading Cycles algorithm, in this paper we show that many questions concerning the structure of the core are difficult to answer.