Probing for maximizing the expected number of transplants

Abstract

Kidney exchange programs rely on the exchange of donors between patients having an in compatible willing donor. In this paper, we address two problems of deciding which potential transplants to probe for maximizing the expected number of transplants. For both of them each potential transplant has a probability of failure and a set of crossmatch tests can be made (removing the uncertainty of the potential transplants of that set) before the actual transplants are decided. In the first problem, tests are made sequentially and, in the second, they are made simultaneously. We propose one method for each problem based on solving integer program ming models and on the concept of expected number of transplants with probing for selecting the tests to conduct. Preliminary computational tests are presented for the method that solves the sequential problem and for two variants of the method that solves the simultaneous problem.