Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
barter exchange; kidney transplantation; Pareto optimality; NP- completeness
barter exchange; kidney transplantation; Pareto optimality; NP- completeness
Summary:
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.
References:
[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 2258195 | Zbl 1115.90049
[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 2292110
[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 1726561 | Zbl 0976.91002
[6] Cechlárová K., Hajduková J.: Computational complexity of stable partitions with ${\mathcal B}$-preferences. Internat. J. Game Theory 31 (2003), 353–364 MR 1983410
[7] Cechlárová K., Medina A. Romero: Stability in coalition formation games. Internat. J. Game Theory 29 (2001), 487–494 MR 1831208
[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 2206984 | Zbl 1142.91385
[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 1467836 | Zbl 0885.90123
[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 1939046 | Zbl 1083.91017
[12] Garey M. R., Johnson D. S.: Computers and Intractability. Freeman, San Francisco, CA 1979 MR 0519066 | Zbl 0522.68040
[13] Granot D., Huberman G.: Minimum cost spanning tree games. Math. Programming 21 (1981), 1–18 MR 0618611 | Zbl 0461.90099
[14] Gusfield D., Irving R. W.: The stable marriage problem: Structure and algorithms. Foundations of Computing, MIT Press, Cambridge, Mass. 1989 MR 1021242 | Zbl 0703.68046
[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 2066773 | Zbl 1036.90511
[16] Irving R. W.: The cycle roommates problem: a hard case of kidney exchange. Inform. Process. Lett. 103 (2007), 1, 1–4 MR 2321852 | Zbl 1184.68271
[17] Kalai E., Zemel E.: Totally balanced games and games of flow. Math. Oper. Res. 7 (1982), 476–478 MR 0667936 | Zbl 0498.90030
[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 0403700 | Zbl 0318.90060
[21] Roth A., Sönmez, T., Ünver U.: Kidney exchange. Quarterly J. Econom. 119 (2004), 457–488 Zbl 1081.92023
[22] Roth A., Sönmez, T., Ünver U.: Pairwise kidney exchange. J. Econom. Theory 125 (2005), 151–188 MR 2186970 | Zbl 1081.92023
[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 0416531 | Zbl 0349.90135
[28] Yuan Y.: Residence exchange wanted: A stable residence exchange problem. European J. Oper. Res. 90 (1996), 536–546 Zbl 0907.90199
[29] Zenios S. A.: Optimal control of a paired-kidney exchange program. Management Sci. 48 (2002), 328–342 Zbl 1232.90298
Search
Partner of
