Nash equilibria in the kidney exchange game

Invited abstract in session TB-16: Kidney exchange programs, stream Healthcare Logistics.

Area: Routing, Location, Logistics and Transportation

Tuesday, 10:30-12:00
Room: Building CW, 1st floor, Room 128

Authors (first author is the speaker)

1. Margarida Carvalho
Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal
2. Andrea Lodi
D.E.I.S., University of Bologna
3. Joao Pedro Pedroso
Departamento de Ciencia de Computadores, INESC TEC and Faculdade de Ciencias, Universidade do Porto
4. Ana Viana


Kidney exchange programs have been set in several countries within national, regional or hospital frameworks, to increase the possibility of renal patients being transplanted. Previously, a patient would receive a kidney transplant from a deceased donor, or from a compatible living donor that is a patient's relative or friend. These two possibilities only satisfy a tiny fraction of the demand. Kidney exchange programs allow exchanges between a patient in an incompatible pair and a compatible donor in another incompatible pair.

In some countries the exchange programs take place at regional or hospital level. It has been claimed that these entities would benefit if they collaborated with each other, sharing their internal pools and allowing transplants involving patients of different entities. Nevertheless, for the case of hospital's programs, it has been observed that each hospital is a self-interested agent whose aim is to maximize the number of its patients receiving a kidney. This claim led to the study of multi-player exchange markets. We propose a novel direction in this setting by modeling the exchange market as a game. The analysis of the 2 player case with pairwise exchanges allowed us to prove that the most rational game outcome, Nash equilibrium, maximizes the social welfare, it is Pareto efficient, minimizes the number of external exchanges, and that it can be computed in polynomial time.


Status: accepted

Back to the list of papers