Geodesic
Pareto optimality in the kidney exchange problem
Kybernetika, Tome 44 (2008) no. 3, pp. 373-384 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

To overcome the shortage of cadaveric kidneys available for transplantation, several countries organize systematic kidney exchange programs. The kidney exchange problem can be modelled as a cooperative game between incompatible patient-donor pairs whose solutions are permutations of players representing cyclic donations. We show that the problems to decide whether a given permutation is not (weakly) Pareto optimal are NP-complete.
To overcome the shortage of cadaveric kidneys available for transplantation, several countries organize systematic kidney exchange programs. The kidney exchange problem can be modelled as a cooperative game between incompatible patient-donor pairs whose solutions are permutations of players representing cyclic donations. We show that the problems to decide whether a given permutation is not (weakly) Pareto optimal are NP-complete.
Classification : 68Q25, 91A06, 91A12, 91B68
Keywords: barter exchange; kidney transplantation; Pareto optimality; NP- completeness 
@article{KYB_2008_44_3_a7,
     author = {Borbe\v{l}ov\'a, Viera and Cechl\'arov\'a, Katar{\'\i}na},
     title = {Pareto optimality in the kidney exchange problem},
     journal = {Kybernetika},
     pages = {373--384},
     year = {2008},
     volume = {44},
     number = {3},
     mrnumber = {2436038},
     zbl = {1154.91579},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2008_44_3_a7/}
}
TY  - JOUR
AU  - Borbeľová, Viera
AU  - Cechlárová, Katarína
TI  - Pareto optimality in the kidney exchange problem
JO  - Kybernetika
PY  - 2008
SP  - 373
EP  - 384
VL  - 44
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/KYB_2008_44_3_a7/
LA  - en
ID  - KYB_2008_44_3_a7
ER  - 
%0 Journal Article
%A Borbeľová, Viera
%A Cechlárová, Katarína
%T Pareto optimality in the kidney exchange problem
%J Kybernetika
%D 2008
%P 373-384
%V 44
%N 3
%U http://geodesic.mathdoc.fr/item/KYB_2008_44_3_a7/
%G en
%F KYB_2008_44_3_a7
Borbeľová, Viera; Cechlárová, Katarína. Pareto optimality in the kidney exchange problem. Kybernetika, Tome 44 (2008) no. 3, pp. 373-384. http://geodesic.mathdoc.fr/item/KYB_2008_44_3_a7/

[1] Abraham D., Cechlárová K., Manlove, D., Mehlhorn K.: Pareto optimality in house allocation problems. In: Algorithms and Computation (Lecture Notes in Computer Science 3827, R. Fleischer and G. Trippen, eds.), Springer-Verlag, Berlin 2004, pp. 1163–1175 | MR | Zbl

[2] Abraham D., Manlove D.: Pareto Optimality in the Roommates Problem. Technical Report No. TR-2004-182 of the Computing Science Department of Glasgow University, 2004

[3] Abraham D., Blum, A., Sandholm T.: Clearing algorithms for barter exchaneg markets: Enabling nationwide kidney exchanges. In: EC’07, San Diego 2007, pp. 11–15

[4] Biró P., Cechlárová K.: Inapproximability for the kidney exchange problem. Inform. Process. Lett. 101 (2007), 199–202 | MR

[5] Cechlárová K., Hajduková J.: Stability testing in coalition formation games. In: Proc. SOR’99, Preddvor (V. Rupnik, L. Zadnik-Stirn, and S. Drobne, eds.), Slovenia 1999, pp. 111–116 | MR | Zbl

[6] Cechlárová K., Hajduková J.: Computational complexity of stable partitions with ${\mathcal B}$-preferences. Internat. J. Game Theory 31 (2003), 353–364 | MR

[7] Cechlárová K., Medina A. Romero: Stability in coalition formation games. Internat. J. Game Theory 29 (2001), 487–494 | MR

[8] Cechlárová K., Fleiner, T., Manlove D.: The kidney exchange game. In: Proc. SOR’05, (L. Zadnik-Stirn and S. Drobne, eds.), Slovenia 2005, pp. 77–83 | MR | Zbl

[9] Cechlárová K., Lacko V.: The kidney exchange problem: How hard is it to find a donor? IM Preprint 4/200.

[10] Faigle U., Kern W., Fekete S. P., Hochstättler W.: On the complexity of testing membership in the core of min-cost spanning tree games. Internat. J. Game Theory 26 (1997), 361–366 | MR | Zbl

[11] Fang Q., Zhu S., Cai, M., Deng X.: On computational complexity of membership test in flow games and linear production games. Internat. J. Game Theory 31 (2002), 39–45 | MR | Zbl

[12] Garey M. R., Johnson D. S.: Computers and Intractability. Freeman, San Francisco, CA 1979 | MR | Zbl

[13] Granot D., Huberman G.: Minimum cost spanning tree games. Math. Programming 21 (1981), 1–18 | MR | Zbl

[14] Gusfield D., Irving R. W.: The stable marriage problem: Structure and algorithms. Foundations of Computing, MIT Press, Cambridge, Mass. 1989 | MR | Zbl

[15] Irving R. W., Manlove D. F., Scott S.: Strong stability in the hospitals/residents problem. In: STACS 2003 (Lecture Notes in Computer Science 2607), Springer-Verlag, Berlin 2003, pp. 439–450 | MR | Zbl

[16] Irving R. W.: The cycle roommates problem: a hard case of kidney exchange. Inform. Process. Lett. 103 (2007), 1, 1–4 | MR | Zbl

[17] Kalai E., Zemel E.: Totally balanced games and games of flow. Math. Oper. Res. 7 (1982), 476–478 | MR | Zbl

[18] Keizer K. M., Klerk M. de, Haase-Kromwijk B. J. J. M., Weimar W.: The Dutch algorithm for allocation in living donor kidney exchange. Transplantation Proceedings 37 (2005), 589–591

[19] Lucan M., Rotariu P., Neculoiu, D., Iacob G.: Kidney exchange program: a viable alternative in countries with low rate of cadaver harvesting. Transplantation Proceedings 35 (2003), 933–934

[20] Owen G.: On the core of linear production games. Math. Programming 9 (1975), 358–370 | MR | Zbl

[21] Roth A., Sönmez, T., Ünver U.: Kidney exchange. Quarterly J. Econom. 119 (2004), 457–488 | Zbl

[22] Roth A., Sönmez, T., Ünver U.: Pairwise kidney exchange. J. Econom. Theory 125 (2005), 151–188 | MR | Zbl

[23] Roth A., Sönmez, T., Ünver U.: Efficient kidney exchange: Coincidence of wants in a structured market. American Econom. Rev. 97 (2007), 828–851

[24] Saidman S. L., Roth A., Sönmez T., Ünver, U., Delmonico F. L.: Increasing the opportunity of live kidney donation by matching for two and three way exchanges. Transplantation 81 (2006), 773–782

[25] Segev D. L., Gentry S. E., Warren D. S., Reeb, B., Montgomery R. A.: Kidney paired donation and optimizing the use of live donor organs. JAMA 293 (2005), 1883–1890

[26] Shapley L., Scarf H.: On cores and indivisibility. J. Math. Econom. 1 (1974), 23–37 | MR | Zbl

[28] Yuan Y.: Residence exchange wanted: A stable residence exchange problem. European J. Oper. Res. 90 (1996), 536–546 | Zbl

[29] Zenios S. A.: Optimal control of a paired-kidney exchange program. Management Sci. 48 (2002), 328–342 | Zbl