Paired Kidney Exchange (PKE) programs solve incompatibility problems of donor–patient pairs in living donor kidney transplantation by arranging exchanges of donors among several pairs. Further efficiency gains may emerge if the programs consider the quality of the matches between patients and donors. Limitations on the number of simultaneous required operations imply that every efficient PKE program introduces incentives for the patients to misreport how they rank the option of remaining in dialysis with respect to the available kidneys. Truthfully revealing their preferences is however, the unique protective (lexicographic maximin) strategy for patients under pairwise exchange maximizing PKE programs.