  Kidney exchange programs (KEPs) form an innovative approach to increasing the
donor pool through allowing the participation of renal patients together with a
willing but incompatible donor. The aim of a KEP is to identify groups of
incompatible donor-recipient pairs that could exchange donors leading to
feasible transplants. As the size of a kidney exchange grows, a larger
proportion of participants can be transplanted. Collaboration between multiple
transplant centers, by merging their separate kidney exchange pools is thus
desirable. As each transplant center has its own interest to provide the best
care to its own patients, collaboration requires balancing individual and
common objectives. We consider a class of algorithmic mechanisms for
multi-center kidney exchange programs we call rejection-proof mechanisms. Such
mechanisms propose solutions with the property that no player wishes to
unilaterally deviate. We provide a mechanism optimizing social value under this
restriction, though the underlying optimization problem is Sigma-2-p-Hard. We
also describe a computationally easier but sub-optimal alternative. Experiments
show that rejection-proofness can be achieved at limited cost compared to
optimal solutions for regular kidney exchange. Computationally, we provide
algorithms to compute optimal rejection-proof solutions for small and medium
instance sizes.
