Pareto optimality in the kidney exchange problem

Viera Borbeľová; Katarína Cechlárová

Kybernetika (2008)

  • Volume: 44, Issue: 3, page 373-384
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Borbeľová, Viera, and Cechlárová, Katarína. "Pareto optimality in the kidney exchange problem." Kybernetika 44.3 (2008): 373-384. <http://eudml.org/doc/33934>.

@article{Borbeľová2008,
abstract = {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.},
author = {Borbeľová, Viera, Cechlárová, Katarína},
journal = {Kybernetika},
keywords = {barter exchange; kidney transplantation; Pareto optimality; NP- completeness; barter exchange; kidney transplantation; Pareto optimality; NP-completeness},
language = {eng},
number = {3},
pages = {373-384},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Pareto optimality in the kidney exchange problem},
url = {http://eudml.org/doc/33934},
volume = {44},
year = {2008},
}

TY - JOUR
AU - Borbeľová, Viera
AU - Cechlárová, Katarína
TI - Pareto optimality in the kidney exchange problem
JO - Kybernetika
PY - 2008
PB - Institute of Information Theory and Automation AS CR
VL - 44
IS - 3
SP - 373
EP - 384
AB - 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.
LA - eng
KW - barter exchange; kidney transplantation; Pareto optimality; NP- completeness; barter exchange; kidney transplantation; Pareto optimality; NP-completeness
UR - http://eudml.org/doc/33934
ER -

References

top
  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 Zbl1115.90049MR2258195
  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 MR2292110
  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 (1999) Zbl0976.91002MR1726561
  6. Cechlárová K., Hajduková J., Computational complexity of stable partitions with ℬ -preferences, Internat. J. Game Theory 31 (2003), 353–364 MR1983410
  7. Cechlárová K., Medina A. Romero, Stability in coalition formation games, Internat. J. Game Theory 29 (2001), 487–494 MR1831208
  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 Zbl1142.91385MR2206984
  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 (1997) Zbl0885.90123MR1467836
  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 Zbl1083.91017MR1939046
  12. Garey M. R., Johnson D. S., Computers and Intractability, Freeman, San Francisco, CA 1979 Zbl0522.68040MR0519066
  13. Granot D., Huberman G., Minimum cost spanning tree games, Math. Programming 21 (1981), 1–18 (1981) Zbl0461.90099MR0618611
  14. Gusfield D., Irving R. W., The stable marriage problem: Structure and algorithms, Foundations of Computing, MIT Press, Cambridge, Mass. 1989 Zbl0703.68046MR1021242
  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 Zbl1036.90511MR2066773
  16. Irving R. W., The cycle roommates problem: a hard case of kidney exchange, Inform. Process. Lett. 103 (2007), 1, 1–4 Zbl1184.68271MR2321852
  17. Kalai E., Zemel E., Totally balanced games and games of flow, Math. Oper. Res. 7 (1982), 476–478 (1982) Zbl0498.90030MR0667936
  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 (1975) Zbl0318.90060MR0403700
  21. Roth A., Sönmez, T., Ünver U., Kidney exchange, Quarterly J. Econom. 119 (2004), 457–488 Zbl1081.92023
  22. Roth A., Sönmez, T., Ünver U., Pairwise kidney exchange, J. Econom. Theory 125 (2005), 151–188 Zbl1081.92023MR2186970
  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 (1974) Zbl0349.90135MR0416531
  27. Yuan Y., Residence exchange wanted: A stable residence exchange problem, European J. Oper. Res. 90 (1996), 536–546 (1996) Zbl0907.90199
  28. Zenios S. A., Optimal control of a paired-kidney exchange program, Management Sci. 48 (2002), 328–342 Zbl1232.90298

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.