Strategy-Proof and Efficient Kidney Exchange Using a Credit Mechanism


  • Chen Hajaj Bar-Ilan University
  • John Dickerson Carnegie Mellon University
  • Avinatan Hassidim Bar-Ilan University
  • Tuomas Sandholm Carnegie Mellon University
  • David Sarne Bar-Ilan University



Dynamic mechanism design, kidney exchange


We present a credit-based matching mechanism for dynamic barter markets — and kidney exchange in particular — that is both strategy proof and efficient, that is, it guarantees truthful disclosure of donor-patient pairs from the transplant centers and results in the maximum global matching. Furthermore, the mechanism is individually rational in the sense that, in the long run, it guarantees each transplant center more matches than the center could have achieved alone. The mechanism does not require assumptions about the underlying distribution of compatibility graphs — a nuance that has previously produced conflicting results in other aspects of theoretical kidney exchange. Our results apply not only to matching via 2-cycles: the matchings can also include cycles of any length and altruist-initiated chains, which is important at least in kidney exchanges. The mechanism can also be adjusted to guarantee immediate individual rationality at the expense of economic efficiency, while preserving strategy proofness via the credits. This circumvents a well-known impossibility result in static kidney exchange concerning the existence of an individually rational, strategy-proof, and maximal mechanism. We show empirically that the mechanism results in significant gains on data from a national kidney exchange that includes 59% of all US transplant centers.




How to Cite

Hajaj, C., Dickerson, J., Hassidim, A., Sandholm, T., & Sarne, D. (2015). Strategy-Proof and Efficient Kidney Exchange Using a Credit Mechanism. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1).



AAAI Technical Track: Game Theory and Economic Paradigms