Rejection-proof mechanisms for multi-agent kidney exchange

Kidney exchange programs (KEPs) increase kidney transplantation by facilitating the exchange of incompatible donors. Increasing the scale of KEPs leads to more opportunities for transplants. Collaboration between transplant organizations (agents) is thus desirable. As agents are primarily interested in providing transplants for their own patients, collaboration requires balancing individual and common objectives. In this paper, we consider ex-post strategic behavior, where agents can modify a proposed set of kidney exchanges. We introduce the class of rejection -proof mechanisms, which propose a set of exchanges such that agents have no incentive to reject them. We provide an exact mechanism and establish that the underlying optimization problem is sigma P2-hard; we also describe computationally less demanding heuristic mechanisms. We show rejection-proofness can be achieved at a limited cost for typical instances. Furthermore, our experiments show that the proposed rejection-proof mechanisms also remove incentives for strategic behavior in the ex-ante setting, where agents withhold information.

Automated summary

This paper investigates the strategic behavior of agents in kidney exchange programs and proposes rejection-proof mechanisms to eliminate incentives for strategic behavior. Experiments demonstrate the effectiveness of these mechanisms in both ex-ante information withholding and ex-post exchange modification scenarios.