Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges

ABSTRACT

In barter-exchange markets, agents seek to swap their items with one another, in order to improve their own utilities. These swaps consist of cycles of agents, with each agent receiving the item of the next agent in the cycle. We focus mainly on the upcoming national kidney-exchange market, where patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. With over 70,000 patients already waiting for a cadaver kidney in the US, this market is seen as the only ethical way to significantly reduce the 4,000 deaths per year attributed to kidney diseas.

The clearing problem involves finding a social welfare maximizing exchange when the maximum length of a cycle is fixed. Long cycles are forbidden, since, for incentive reasons, all transplants in a cycle must be performed simultaneously. Also, in barter-exchanges generally, more agents are affected if one drops out of a longer cycle. We prove that the clearing problem with this cycle-length constraint is NP-hard. Solving it exactly is one of the main challenges in establishing a national kidney exchange.

We present the first algorithm capable of clearing these markets on a nationwide scale. The key is incremental problem formulation. We adapt two paradigms for the task: constraint generation and column generation. For each, we develop techniques that dramatically improve both runtime and memory usage. We conclude that column generation scales drastically better than constraint generation. Our algorithm also supports several generalizations, as demanded by real-world kidney exchanges.

Our algorithm replaced CPLEX as the clearing algorithm of the Alliance for Paired Donation, one of the leading kidney exchanges. The match runs are conducted every two weeks and transplants based on our optimizations have already been conducted.

REFERENCES

• 1: Cynthia Barnhart , Ellis L. Johnson , George L. Nemhauser , Martin W. P. Savelsbergh , Pamela H. Vance, Branch-And-Price: Column Generation for Solving Huge Integer Programs, Operations Research, v.46 n.3, p.316-329, March 1998
• 2: Rina Dechter , Judea Pearl, Generalized best-first search strategies and the optimality af A*, Journal of the ACM (JACM), v.32 n.3, p.505-536, July 1985 [doi>10.1145/3828.3830]
• 3: F. L. Delmonico. Exchanging kidneys - advances in living-donor transplantation. New England Journal of Medicine, 350:1812--1814, 2004.
• 4: J. Edmonds. Path, trees, and flowers. Canadian Journal of Mathematics, 17:449--467, 1965.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990
• 6: S. E. Gentry, D. L. Segev, and R. A. Montgomery. A comparison of populations served by kidney paired donation and list paired donation. American Journal of Transplantation, 5(8):1914--1921, August 2005.
• 7: P. Hart, N. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2):100--107, 1968.
• 8: Karla L. Hoffman , Manfred Padberg, Solving airline crew scheduling problems by branch-and-cut, Management Science, v.39 n.6, p.657-682, June 1993
• 9: Intervac. http://intervac-online.com/.
• 10: National odd shoe exchange. http://www.oddshoe.org/.
• 11: Peerflix. http://www.peerflix.com.
• 12: Read it swap it. http://www.readitswapit.co.uk/.
• 13: A. E. Roth, T. Sonmez, and M. U. Unver. Kidney exchange. Quarterly Journal of Economics, 119(2):457--488, May 2004.
• 14: A. E. Roth, T. Sonmez, and M. U. Unver. A kidney exchange clearinghouse in New England. American Economic Review, 95(2):376--380, May 2005.
• 15: A. E. Roth, T. Sonmez, and M. U. Unver. Efficient kidney exchange: Coincidence of wants in a market with compatibility-based preferences. American Economic Review, forthcoming.
• 16: E. Rothberg. Gabow's n3 maximum-weight matching algorithm: an implementation. The First DIMACS Implementation Challenge, 1990.
• 17: S. L. Saidman, A. E. Roth, T. Snmez, M. U. Unver, and F. L. Delmonico. Increasing the opportunity of live kidney donation by matching for two and three way exchanges. Transplantation, 81(5):773--782, 2006.
• 18: T. Sandholm. Optimal winner determination algorithms. In Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds. MIT Press, 2006.
• 19: T. Sandholm and S. Suri. Side constraints and non-price attributes in markets. In IJCAI-2001 Workshop on Distributed Constraint Reasoning, pages 55--61, Seattle, WA, 2001. To appear in Games and Economic Behavior.
• 20: D. L. Segev, S. E. Gentry, D. S. Warren, B. Reeb, and R. A. Montgomery. Kidney paired donation and optimizing the use of live donor organs. Journal of the American Medical Association, 293(15):1883--1890, April 2005.
• 21: United Network for Organ Sharing (UNOS). http://www.unos.org/.
• 22: M. U. Unver. Dynamic kidney exchange. Working paper.
• 23: United States Renal Data System (USRDS). http://www.usrds.org/.
• 24: Stefanos A. Zenios, Optimal Control of a Paired-Kidney Exchange Program, Management Science, v.48 n.3, p.328-342, March 2002 [doi>10.1287/mnsc.48.3.328.7732]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Economics

Keywords:
barter, branch-and-price, column generation, exchange, kidney, matching, transplant