Cette page appartient aux archives web de l'EPFL et n'est plus tenue à jour.
This page belongs to EPFL's web archive and is no longer updated.

Applications: Kidney Exchanges

I. Ashlagi and A. Roth, 2011, Individual rationality and participation in large scale, multi-hospital kidney exchange, Working Paper (Short abstract appeared in EC 2011)

Posted by Katherine Skirving Larson on Friday 18 May 2012 at 12:06
This paper addresses the kidney exchange problem. It shows that with current matching mechanism it is not rational for hospitals to enter all their pairs (including matchings) to the mechanism. In fact, the paper shows that in worst case it could be very costly for a hospital to do so. On the other hand, in large market this cost could be significantly lower.
To study the large market and obtain analytical results, the authors use the concept of random graphs. An interesting result raise from this theorem that shows in a very large market the allocations are efficient with chains no longer than 3 pairs. Although these results show a strong theoretical argument, the simulated graph from real data shows results far from efficiency due to sparse data. These problem is very bold with presence of highly sensitized patients. These patients are compatible with a very small number of donors even in a large graph because of blood type distributions in reality.
Posted by Laleh Makarem on Wednesday 23 May 2012 at 11:30
The paper captures an important application area, namely kidney exchange.

Instead of considering one to one exchange, or under one hospital exchange, this paper offer a mechanism to perform kidney exchanges in national level (possibly also cross country border) under multi-hospital. Therefore, the goal is that we want to maximize the number of exchange happens (that is save as many life as possible).

Nevertheless, a problem occur when the result of this global mechanism not individually rational, i.e. perform less number exchanges for a hospital that it is expected to be (that is, when this hospital perform internal exchanges for all its patients itself). This condition potentially will discourage the hospital to not participate in the global exchange.

While the obvious approach is to design a strategyproof mechanism, the authors have proved that there is not individually rational mechanism that is both maximal and strategyproof.

Hence, to show that the global exchange is still worth to be considered, the authors show that the loss of a hospital (because of not individual rationality) to participate in a global exchange is low when the exchange pool is large.

Overall, the paper present definition, lemma, theorem, proof clearly. However, some question might arise for the simulation in section 3 (on how they did it, what parameter to be set). I also wonder how significant is the influence of the assumption of person's blood type distribution has on Proposition 5.2, in particular, whether the result does apply for any distribution.
Posted by Tri Kurniawan Wijaya on Friday 25 May 2012 at 17:29