Nash equilibria in the kidney exchange game
Room: Building CW, 1st floor, Room 128
Authors (first author is the speaker)
|Department of Mathematics and Industrial Engineering, École Polytechnique de Montréal|
|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|
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.
- Game Theory
- Graphs and Networks
Back to the list of papers