| Title:
|
Pareto optimality in the kidney exchange problem (English) |
| Author:
|
Borbeľová, Viera |
| Author:
|
Cechlárová, Katarína |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
44 |
| Issue:
|
3 |
| Year:
|
2008 |
| Pages:
|
373-384 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
barter exchange |
| Keyword:
|
kidney transplantation |
| Keyword:
|
Pareto optimality |
| Keyword:
|
NP- completeness |
| MSC:
|
68Q25 |
| MSC:
|
91A06 |
| MSC:
|
91A12 |
| MSC:
|
91B68 |
| idZBL:
|
Zbl 1154.91579 |
| idMR:
|
MR2436038 |
| . |
| Date available:
|
2009-09-24T20:35:25Z |
| Last updated:
|
2012-06-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135857 |
| . |
| Reference:
|
[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 Zbl 1115.90049, MR 2258195 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[4] Biró P., Cechlárová K.: Inapproximability for the kidney exchange problem.Inform. Process. Lett. 101 (2007), 199–202 MR 2292110 |
| Reference:
|
[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 Zbl 0976.91002, MR 1726561 |
| Reference:
|
[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 |
| Reference:
|
[7] Cechlárová K., Medina A. Romero: Stability in coalition formation games.Internat. J. Game Theory 29 (2001), 487–494 MR 1831208 |
| Reference:
|
[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 Zbl 1142.91385, MR 2206984 |
| Reference:
|
[9] Cechlárová K., Lacko V.: The kidney exchange problem: How hard is it to find a donor? IM Preprint 4/200. |
| Reference:
|
[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 Zbl 0885.90123, MR 1467836 |
| Reference:
|
[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 Zbl 1083.91017, MR 1939046 |
| Reference:
|
[12] Garey M. R., Johnson D. S.: Computers and Intractability.Freeman, San Francisco, CA 1979 Zbl 0522.68040, MR 0519066 |
| Reference:
|
[13] Granot D., Huberman G.: Minimum cost spanning tree games.Math. Programming 21 (1981), 1–18 Zbl 0461.90099, MR 0618611 |
| Reference:
|
[14] Gusfield D., Irving R. W.: The stable marriage problem: Structure and algorithms.Foundations of Computing, MIT Press, Cambridge, Mass. 1989 Zbl 0703.68046, MR 1021242 |
| Reference:
|
[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 Zbl 1036.90511, MR 2066773 |
| Reference:
|
[16] Irving R. W.: The cycle roommates problem: a hard case of kidney exchange.Inform. Process. Lett. 103 (2007), 1, 1–4 Zbl 1184.68271, MR 2321852 |
| Reference:
|
[17] Kalai E., Zemel E.: Totally balanced games and games of flow.Math. Oper. Res. 7 (1982), 476–478 Zbl 0498.90030, MR 0667936 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[20] Owen G.: On the core of linear production games.Math. Programming 9 (1975), 358–370 Zbl 0318.90060, MR 0403700 |
| Reference:
|
[21] Roth A., Sönmez, T., Ünver U.: Kidney exchange.Quarterly J. Econom. 119 (2004), 457–488 Zbl 1081.92023 |
| Reference:
|
[22] Roth A., Sönmez, T., Ünver U.: Pairwise kidney exchange.J. Econom. Theory 125 (2005), 151–188 Zbl 1081.92023, MR 2186970 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[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 |
| Reference:
|
[26] Shapley L., Scarf H.: On cores and indivisibility.J. Math. Econom. 1 (1974), 23–37 Zbl 0349.90135, MR 0416531 |
| Reference:
|
[28] Yuan Y.: Residence exchange wanted: A stable residence exchange problem.European J. Oper. Res. 90 (1996), 536–546 Zbl 0907.90199 |
| Reference:
|
[29] Zenios S. A.: Optimal control of a paired-kidney exchange program.Management Sci. 48 (2002), 328–342 Zbl 1232.90298 |
| . |
