×

Pairwise kidney exchange. (English) Zbl 1081.92023

Summary: The literature on exchange of indivisible goods finds natural application in the exchange of live donor kidneys for transplant. However, in kidney exchange, there are constraints on the size of exchanges. Initially, kidney exchanges are likely to be between just two patient-donor pairs. We show that, although this constraint eliminates some potential exchanges, there is a wide class of constrained-efficient mechanisms that are strategy proof when patient-donor pairs and surgeons have \(0\,-\,1\) preferences. This includes deterministic mechanisms that accommodate the priority setting that organ banks currently use to allocate cadaver organs, and stochastic mechanisms that allow distributive justice issues to be addressed.

MSC:

92C50 Medical applications (general)
91B68 Matching models
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Abdulkadiroğlu, P.A. Pathak, A.E. Roth, The New York City high school match, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.; A. Abdulkadiroğlu, P.A. Pathak, A.E. Roth, The New York City high school match, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.
[2] A. Abdulkadiroğlu, P.A. Pathak, A.E. Roth, T. Sönmez, The Boston public school match, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.; A. Abdulkadiroğlu, P.A. Pathak, A.E. Roth, T. Sönmez, The Boston public school match, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.
[3] Abdulkadiroğlu, A.; Sönmez, T., Random serial dictatorship and the core from random endowments in house allocation problems, Econometrica, 66, 689-701 (1998) · Zbl 1019.91016
[4] Abdulkadiroğlu, A.; Sönmez, T., House allocation with existing tenants, J. Econ. Theory, 88, 233-260 (1999) · Zbl 0939.91068
[5] Abdulkadiroğlu, A.; Sönmez, T., Ordinal efficiency and dominated sets of assignments, J. Econ. Theory, 112, 157-172 (2003) · Zbl 1076.91023
[6] Abdulkadiroğlu, A.; Sönmez, T., School choice: a mechanism design approach, Amer. Econ. Rev., 93, 729-747 (2003)
[7] Abecassis, M., Consensus statement on the live organ donor, J. Amer. Med. Assoc., 284, 2919-2926 (2002)
[8] Abeledo, H.; Rothblum, U. G., Stable matchings and linear inequalities, Discrete Appl. Math., 54, 1-27 (1994) · Zbl 0820.90090
[9] A. Bogomolnaia, L. Ehlers, R. Deb, Incentive-compatible assignment on the full preference domain, J. Econ. Theory, forthcoming. doi:10.1016/j.jet.2004.05.004; A. Bogomolnaia, L. Ehlers, R. Deb, Incentive-compatible assignment on the full preference domain, J. Econ. Theory, forthcoming. doi:10.1016/j.jet.2004.05.004 · Zbl 1115.91019
[10] Bogomolnaia, A.; Moulin, H., A new solution to the random assignment problem, J. Econ. Theory, 100, 295-328 (2001) · Zbl 1134.91357
[11] Bogomolnaia, A.; Moulin, H., A simple random assignment problem with a unique solution, Econ. Theory, 19, 623-635 (2002) · Zbl 1022.91018
[12] Bogomolnaia, A.; Moulin, H., Random matching under dichotomous preferences, Econometrica, 72, 257-279 (2004) · Zbl 1142.91691
[13] Chung, K.-S., On the existence of stable roommate matchings, Games Econ. Behav., 33, 206-230 (2000) · Zbl 1047.91012
[14] Cres, H.; Moulin, H., Scheduling with opting out: improving upon random priority, Oper. Res., 49, 565-577 (2001) · Zbl 1163.90520
[15] V.P. Crawford, The flexible-salary match: a proposal to increase the salary flexibility of the National Resident Matching Program, working paper, UCSD, 2005.; V.P. Crawford, The flexible-salary match: a proposal to increase the salary flexibility of the National Resident Matching Program, working paper, UCSD, 2005.
[16] Delmonico, F. L., Exchanging kidneys—advances in living-donor transplantation, New Eng. J. Med., 350, 1812-1814 (2004)
[17] Diamantoudi, E.; Miyagawa, E.; Xue, L., Random paths to stability in the roommate problem, Games Econ. Behav., 48, 18-28 (2004) · Zbl 1093.91046
[18] Dutta, B.; Ray, D., A concept of egalitarianism under participation constraints, Econometrica, 57, 615-635 (1989) · Zbl 0703.90105
[19] Edmonds, J., Paths, trees, and flowers, Canad. J. Math., 17, 449-467 (1965) · Zbl 0132.20903
[20] Edmonds, J., Matroids and the greedy algorithm, Math. Programming, 1, 127-136 (1971) · Zbl 0253.90027
[21] Ehlers, L., Coalitional strategy-proof house allocation, J. Econ. Theory, 105, 298-317 (2002) · Zbl 1021.91035
[22] Ehlers, L.; Klaus, B., Coalitional strategy-proof and resource monotonic solutions for multiple assignment problems, Soc. Choice Welfare, 21, 265-280 (2003) · Zbl 1073.91596
[23] Ehlers, L.; Klaus, B.; Papai, S., Strategy-proofness and population-monotonicity in house allocation problems, J. Math. Econ., 38, 329-339 (2002) · Zbl 1010.90034
[24] Gale, D.; Shapley, L. S., College admissions and the stability of marriage, Amer. Math. Monthly, 69, 9-15 (1962) · Zbl 0109.24403
[25] Gallai, T., Magyar Tud. Akad. Mat. Kutató Int. Közl., 8, 373-395 (1963)
[26] Gallai, T., Maximale Systeme unabhängiger kanten, Magyar Tud. Akad. Mat. Kutató Int. Közl., 9, 401-413 (1964) · Zbl 0135.42001
[27] Gjertson, D. W.; Cecka, J. M., Living unrelated donor kidney transplantation, Kidney Int., 58, 491-499 (2000)
[28] M.X. Goemans, Lecture notes on topics in combinatorial optimization, Massachusetts Institute of Technology Lecture Notes, 2004.; M.X. Goemans, Lecture notes on topics in combinatorial optimization, Massachusetts Institute of Technology Lecture Notes, 2004.
[29] Hall, P., On representatives of subsets, J. London Math. Soc., 10, 26-30 (1935) · Zbl 0010.34503
[30] Korte, B.; Vygen, J., Combinatorial Optimization: Theory and Algorithms (2002), Springer: Springer Berlin, Heidelberg, New York · Zbl 1002.90046
[31] Lovász, L.; Plummer, M. D., Matching Theory (1986), North-Holland: North-Holland Amsterdam, New York, Oxford, Tokyo · Zbl 0618.05001
[32] Lucan, M.; Rotariu, P.; Neculoiu, D.; Iacob, G., Kidney exchange program: a viable alternative in countries with low rate of cadaver harvesting, Transplant. Proc., 35, 933-934 (2003)
[33] Milgrom, P., Putting Auction Theory to Work (2004), Cambridge University Press: Cambridge University Press Cambridge
[34] Niederle, M.; Roth, A. E., The gastroenterology fellowship match: how it failed and why it could succeed once again, Gastroenterology, 127, 658-666 (2004)
[35] M. Niederle, A.E. Roth, The Gastroenterology fellowship market: should there be a match?, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.; M. Niederle, A.E. Roth, The Gastroenterology fellowship market: should there be a match?, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.
[36] Opelz, G., Impact of HLA compatibility on survival of kidney transplants from unrelated live donors, Transplantation, 64, 1473-1475 (1997)
[37] Opelz, G., for the Collaborative Transplant Study, HLA compatibility and kidney grafts from unrelated live donors, Transplant. Proc., 30, 704-705 (1998)
[38] Papai, S., Strategyproof assignment by hierarchical exchange, Econometrica, 68, 1403-1433 (2000) · Zbl 1023.91019
[39] Rado, R., Note on independence functions, Proc. London Math. Soc., 7, 300-320 (1957) · Zbl 0083.02302
[40] Rapaport, F. T., The case for a living emotionally related international kidney donor exchange registry, Transplant. Proc., 18, 5-9 (1986)
[41] Ross, L. F.; Woodle, E. S., Ethical issues in increasing living kidney donations by expanding kidney paired exchange programs, Transplantation, 69, 1539-1543 (2000)
[42] Ross, L. F.; Rubin, D. T.; Siegler, M.; Josephson, M. A.; Thistlethwaite, J. R.; Woodle, E. S., Ethics of a paired-kidney-exchange program, New Eng. J. Med., 336, 1752-1755 (1997)
[43] Roth, A. E., Incentive compatibility in a market with indivisible goods, Econ. Lett., 9, 127-132 (1982) · Zbl 0722.90009
[44] Roth, A. E., The economics of matching: stability and incentives, Math. Oper. Res., 7, 617-628 (1982) · Zbl 0496.90008
[45] Roth, A. E., The evolution of the labor market for medical interns and residents: a case study in game theory, J. Polit. Economy, 92, 991-1016 (1984)
[46] Roth, A. E., The college admissions problem is not equivalent to the marriage problem, J. Econ. Theory, 36, 277-288 (1985) · Zbl 0594.90002
[47] Roth, A. E., The economist as engineer: game theory, experimental economics and computation as tools of design economics, Econometrica, 70, 1341-1378 (2002) · Zbl 1137.91339
[48] Roth, A. E.; Peranson, E., The redesign of the matching market for American physicians: some engineering aspects of economic design, Amer. Econ. Rev., 89, 748-780 (1999)
[49] Roth, A. E.; Postlewaite, A., Weak versus strong domination in a market with indivisible goods, J. Math. Econ., 4, 131-137 (1977) · Zbl 0368.90025
[50] Roth, A. E.; Rothblum, U. G.; Vande Vate, J. H., Stable matchings, optimal assignment and linear programming, Math. Oper. Res., 18, 803-828 (1993) · Zbl 0806.90085
[51] Roth, A. E.; Sönmez, T.; Ünver, M. U., Kidney exchange, Quart. J. Econ., 119, 457-488 (2004) · Zbl 1064.92029
[52] A.E. Roth, T. Sönmez , M.U. Ünver, A kidney exchange clearinghouse in New England, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.; A.E. Roth, T. Sönmez , M.U. Ünver, A kidney exchange clearinghouse in New England, Amer. Econ. Rev. Papers Proc. 95 (2005) May, forthcoming.
[53] Roth, A. E.; Sotomayor, M., Two-Sided Matching: A Study in Game-Theoretic Modelling and Analysis (1990), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0726.90003
[54] Roth, A. E.; Vande Vate, J. H., Random paths to stability in two-sided matching, Econometrica, 58, 1475-1480 (1990) · Zbl 0731.90007
[55] Roth, A. E.; Xing, X., Turnaround time and bottlenecks in market clearing: decentralized matching in the market for clinical psychologists, J. Polit. Economy, 105, 284-329 (1997)
[56] D.L. Segev, S.E. Gentry, D.S. Warren, B. Reeb, R. A. Montgomery, Paired kidney donation and optimizing the use of live donor organs, J. Amer. Med. Assoc. (2005), forthcoming.; D.L. Segev, S.E. Gentry, D.S. Warren, B. Reeb, R. A. Montgomery, Paired kidney donation and optimizing the use of live donor organs, J. Amer. Med. Assoc. (2005), forthcoming.
[57] Shapley, L.; Scarf, H., On cores and indivisibility, J. Math. Econ., 1, 23-28 (1974) · Zbl 0281.90014
[58] T. Sönmez, M.U. Ünver, House allocation with existing tenants: an equivalence, Games Econ. Behav., forthcoming, doi:10.1016/j.geb.2004.04.008; T. Sönmez, M.U. Ünver, House allocation with existing tenants: an equivalence, Games Econ. Behav., forthcoming, doi:10.1016/j.geb.2004.04.008
[59] Svensson, L-G., Queue allocation of indivisible goods, Soc. Choice Welfare, 11, 323-330 (1994) · Zbl 0812.90034
[60] Svensson, L.-G., Strategy-proof allocation of indivisible goods, Soc. Choice Welfare, 16, 557-567 (1999) · Zbl 1066.91571
[61] Teo, C.-P.; Sethuraman, J., On a cutting plane heuristic for the stable roommates problem and its applications, European J. Oper. Res., 123, 195-205 (2000) · Zbl 0961.90092
[62] Wilson, R. B., Architecture of power markets, Econometrica, 70, 1299-1340 (2002) · Zbl 1137.91575
[63] Zenios, S. A., Optimal control of a paired-kidney exchange program, Manage. Sci., 48, 328-342 (2002) · Zbl 1232.90298
[64] Zenios, S. A.; Woodle, E. S.; Ross, L. F., Primum non nocere: avoiding harm to vulnerable waitlist candidates in an indirect kidney exchange, Transplantation, 72, 648-654 (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.