EXAMPLE: How does NEPKE optimization software work?

Suppose there are 8 patient-donor pairs registered to the database through the participating transplant centers. All information is gathered by the administrator. Then NEPKE software is run:

TASK 1. FIND the Compatibility matrix

In the table below, the rows denote the recipients and columns denote the donors. D1 is the paired donor of recipient R1, D2 is the paired donor of recipient R2, …, so on so forth. NEPKE software finds the compatible and incompatible donors for each recipient and the reasons for incompatibility:

For example, recipient 2 is incompatible with the donor 7 (the donor of recipient 7) because of her tissue (HLA) type and recipient 2 is incompatible with donor 3 (the donor of recipient 3) because of her blood (ABO) type. On the other hand donor 6 can feasibly donate a kidney to recipient 2.

TASK 2: Identify Optimal Exchanges

Then using the above table, NEPKE software finds all possible exchanges in this data set: There are 4 of them:

Without using optimization one can choose the first exchange, but none of the other exchanges will be feasible and, in this, case only pair 1 and pair 2 participate.

However, by using optimization:

• a Maximal 2-way match is identified by the NEPKE software as follows:
  2nd and 3rd exchanges are chosen, so pair 1, pair 2, pair 3 and pair 4 (and hence a total of four pairs) benefits from kidney exchange
  
  
• a Maximal 2 & 3-way match is identified by the NEPKE software as follows:
  2nd and 4th exchanges are chosen, so pair 1, pair 2, pair 3, pair 5 and pair 6 (and hence a total of five pairs) benefits from kidney exchange
  
  

-----

NEPKE optimization software is based on the following scientific work of Alvin E. Roth, Tayfun Sönmez and Utku Ünver:

• A. E. Roth, T. Sönmez and M. U. Ünver, “Kidney Exchange.” NBER working paper version (no: w10002, September 2003) Quarterly Journal of Economics (2004), 119: 457-488
• A. E. Roth, T. Sönmez and M. U. Ünver, “Pairwise Kidney Exchange.” NBER working paper version (no: w10698, August 2004) Journal of Economic Theory (December, 2005)
• A. E. Roth, T. Sönmez, and M. U. Ünver, “A Kidney Exchange Clearinghouse in New England. (.pdf)” American Economic Review, Papers and Proceedings (May, 2005) 95: 376-380.
• A. E. Roth , T. Sönmez and M. U. Ünver, “Efficient Kidney Exchange: Coincidence of Wants in a Structured Market.” NBER working paper (no: w11402, June 2005)
  

Also see the National Science Foundation press release about the scientific work on the optimal organization of kidney exchange.

Kidney Exchange:
A Chronology of
Scientific Contributions

Concept & Ethics:

• The idea of live donor kidney exchange was first proposed by F. T. Rapaport:
  • F. T. Rapaport [1986] “The case for a living emotionally related international kidney donor exchange registry.” Transplantation Proceedings 18, 5-9.
    • In addition to proposing 2-way kidney exchange between two incompatible donor-recipient pairs, Rapaport also proposed to form a database of incompatible pairs to facilitate such exchanges.
      
      
• Ethics of 2-way kidney exchange:
  • L. F. Ross, D. T. Rubin, M. Siegler, M. A. Josephson, J. R. Thistlethwaite, Jr., and E S. Woodle [1997] “Ethics of a paired-kidney-exchange program.” The New England Journal of Medicine. 336: 1752-1755.
    
    
• General concepts on practice of a 2-way kidney exchange:
  • F.L. Delmonico [2004] "Exchanging kidneys -- Advances in living-donor transplantation." The New England Journal of Medicine. 350: 1812-1814.
    

• List exchange and its ethics:
  • L. F. Ross and E. S. Woodle [2000]. “Ethical issues in increasing living kidney donations by expanding kidney paired exchange programs.” Transplantation. 69: 1539-1543.
  • L. F. Ross and S. Zenios [2004 "Practical and ethical challenges to paired exchange programs." Am J Transplant. 4: 1553-4

• Alturistically unbalanced exchange and its ethics:
  • E.S. Woodle, and L. F. Ross [1998] “Paired Exchanges Should Be Part of the Solution to ABO Incompatibility in Living Donor Kidney Transplantation.” Transplantation. 66(3): 406-7.

Transplant Center Experiences:

• The Korean Experience:
  • K. Park, J.I. Moon, S.I. Kim, Y.S. Kim [1999] “Exchange donor program in kidney transplantation.” Transplantation. 67: 336-338.
    • 2-way kidney exchanges started in Korea in 1991.

• The Romanian Experience:
  • The first 3-way and 4-way kidney exchanges in the world are reported to take place in Romania.M. Lucan, P. Rotariu, D. Neculoiu, and G. Iacob [2003] “Kidney exchange program: A viable alternative in countries with low rate of cadaver harvesting.” Transplantation Proceedings. 35: 933-934.
    • The first 3-way and 4-way kidney exchanges are reported to take place in Romania.

• The New England Experience:
  • F.L. Delmonico, P.E. Morrissey, G.S. Lipkowitz, J.S. Stoff, J. Himmelfarb, W. Harmon, M. Pavlakis, H. Mah, J. Goguen, R. Luskin, E. Milford, G. Basadonna, M. Chobanian, B. Bouthot, M. Lorber, and R.J. Rohrer [2004] “Donor kidney exchanges.” Am J Transplant. 4:1628.

• The Johns Hopkins Experience:
  • R. A. Montgomery, A.A. Zachary, L.E. Ratner, D.L. Segev, J.M. Hiller, J. Houp, M. Cooper, L. Kavoussi, T. Jarrett, J. Burdick, W. R. Maley, J.K. Melancon, T. Kozlowski, C. E. Simpkins, M. Phillips, A. Desai, V. Collins, B. Reeb; E. Kraus, H. Rabb, M.S. Leffell, and D.S. Warren [2005] “Clinical Results From Transplanting Incompatible Live Kidney Donor/Recipient Pairs Using Kidney Paired Donation” Journal of American Medical Association [2005] 294:1655-1663.

• The Dutch Experience:
  • L.W. Kranenburg, T. Visak, W. Weimar et al. [2004] “Starting a crossover kidney transplantation program in the Netherlands: ethical and psychological considerations.” Transplantation. 78:194-7.
  • K.M. Keizer, M. de Klerk M, B. J. Haase-Kromwijk and W. Weimar W [2005] “The Dutch algorithm for allocation in living donor kidney exchange.” Transplant Proceedings. 37:589-91.

Optimal Matching & Mechanism Design:

• Efficient and incentive-compatible organization of paired and list exchanges:
  • A. E. Roth, T. Sönmez and M. U. Ünver [2004] “Kidney Exchange.” Quarterly Journal of Economics, 119: 457-488.
    • First paper to apply techniques from mechanism design literature to kidney exchange.
    • Introduces more elaborate versions of list exchange.
    • Originally appeared as National Bureau of Economic Research Working Paper 10002, September 2003.

• Optimal and incentive compatible mechanisms for organization of 2-way kidney exchange:
  • A. E. Roth, T. Sönmez and M. U. Ünver [2005a] “Pairwise Kidney Exchange.” Journal of Economic Theory, 125: 151-188.
    • Originally appeared as National Bureau of Economic Research Working Paper 10698, August 2004.
    • Builds on techniques developed in the discrete optimization literature by J. Edmonds [1965] “Paths, Trees and Flowers” Canadian Journal of Mathematics.

• The Importance of 3-way kidney exchange:
  • A. E. Roth , T. Sönmez and M. U. Ünver [2005b] “Efficient Kidney Exchange: Coincidence of Wants in a Structured Market.” National Bureau of Economic Research Working Paper 11402, June 2005.
    

Simulations:

• List Exchanges:
  • S. Zenios, E. S. Woodle, and L. F. Ross [2001] “Primum non nocere: avoiding increased waiting times for individual racial and blood-type subsets of kidney wait list candidates in a living donor/cadaveric donor exchange program.” Transplantation. 66, 406-407.

• Gains from 2-way exchanges as well as more elaborate exchanges:
  • A. E. Roth, T. Sönmez and M. U. Ünver [2004]. “Kidney Exchange,” Quarterly Journal of Economics, 119: 457-488.

• Gains from 2-way exchange based on optimization:
  • D.L. Segev, S.E. Gentry, D.S. Warren, B. Reeb, and R.A. Montgomery [2005] “Kidney Paired Donation and optimizing the use of live donor organs.” Journal of American Medical Association (2005) 293(15):1883-90.

• Gains from paired and list exchange using centralized mechanisms:
  • A. E. Roth, T. Sönmez, and M. U. Ünver [2005] “A Kidney Exchange Clearinghouse in New England.” American Economic Review, Papers and Proceedings. 95: 376-380.

• Gains from 3-way exchanges:
  • S. Saidman, A. E. Roth, T. Sönmez, M. U. Ünver, and F.L. Delmonico [2005] “Increasing the Opportunity of Live Kidney Donation By Matching for Two and Three Way Exchanges” Transplantation, forthcoming.

• Waiting time of pairs in the paired exchange pool:
  • D. L. Segev, S. E. Gentry, J. K. Melancon, R. A. Montgomery [2005] “Characterization of Waiting Times in a Simulation of Kidney Paired Donation" D.L. Segev, S.E. Gentry, J.K. Melancon, R.A. Montgomery, American Journal of Transplantation, 5 10): 2448-55.