Adaptation, comparison and practical implementation of fairness schemes in Kidney Exchange Programs

Kidney Exchange Programs (KEPs) typically maximize overall patient benefit through donor exchanges. This aggregation of benefits (utilitarian objective) calls into question potential individual patient disparities in terms of access to transplantation in KEPs. Moreover, current KEP policies are all-or-nothing, meaning that only one exchange plan is determined — each patient is either selected or not as part of that unique solution. In this work, we extend the space of policies by seeking a lottery over the set of exchange plans that contemplates the (ex-ante) probability of patients being in a solution. To guide the determination of our policy, we adapt popular fairness schemes to KEPs to balance the usual approach of maximizing the utilitarian objective. Different combinations of fairness and utilitarian objectives are modeled as conic programs with an exponential number of variables. We propose a column generation approach to solve them effectively in practice. Finally, we make an extensive comparison of the different schemes in terms of the balance of utility and fairness score, and validate the scalability of our methodology for benchmark instances from the literature.