David J. Abraham
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.
- C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W. P. Savelsbergh, and P. H. Vance. Branch-and-price: Column generation for solving huge integer programs. Operations Research, 46:316--329, May-June 1998. Google Scholar
Digital Library
- R. Dechter and J. Pearl. Generalized best-first search strategies and the optimality of A*. Journal of the ACM, 32(3):505--536, 1985. Google ScholarDigital Library
- F. L. Delmonico. Exchanging kidneys - advances in living-donor transplantation. New England Journal of Medicine, 350:1812--1814, 2004.Google ScholarCross Ref
- J. Edmonds. Path, trees, and flowers. Canadian Journal of Mathematics, 17:449--467, 1965.Google Scholar
- M. R. Garey and D. S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. 1990. Google ScholarDigital Library
- 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.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- K. Hoffman and M. Padberg. Solving airline crew-scheduling problems by branch-and-cut. Management Science, 39:657--682, 1993. Google ScholarDigital Library
- Intervac. http://intervac-online.com/.Google Scholar
- National odd shoe exchange. http://www.oddshoe.org/.Google Scholar
- Peerflix. http://www.peerflix.com.Google Scholar
- Read it swap it. http://www.readitswapit.co.uk/.Google Scholar
- A. E. Roth, T. Sonmez, and M. U. Unver. Kidney exchange. Quarterly Journal of Economics, 119(2):457--488, May 2004.Google ScholarCross Ref
- 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.Google ScholarCross Ref
- 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.Google Scholar
- E. Rothberg. Gabow's n3 maximum-weight matching algorithm: an implementation. The First DIMACS Implementation Challenge, 1990.Google Scholar
- 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.Google ScholarCross Ref
- T. Sandholm. Optimal winner determination algorithms. In Combinatorial Auctions, Cramton, Shoham, and Steinberg, eds. MIT Press, 2006.Google Scholar
- 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.Google Scholar
- 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.Google ScholarCross Ref
- United Network for Organ Sharing (UNOS). http://www.unos.org/.Google Scholar
- M. U. Unver. Dynamic kidney exchange. Working paper.Google Scholar
- United States Renal Data System (USRDS). http://www.usrds.org/.Google Scholar
- S. A. Zenios. Optimal control of a paired-kidney exchange program. Management Science, 48(3):328--342, March 2002. Google ScholarDigital Library
Index Terms
- Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges
Recommendations
Multi-unit differential auction-barter model for electronic marketplaces
Differential auction-barter (DAB) model augments the well-known double auction (DA) model with barter bids so that besides the usual purchase and sale activities, bidders can also carry out direct bartering of items. The DAB model also provides a ...
Kidney Exchange: An Operations Perspective
Many patients in need of a kidney transplant have a willing but incompatible (or poorly matched) living donor. Kidney exchange programs arrange exchanges among such patient-donor pairs, in cycles and chains of exchange, so that each patient receives a ...
Exact algorithms for the matrix bid auction
In a combinatorial auction, multiple items are for sale simultaneously to a set of buyers. These buyers are allowed to place bids on subsets of the available items. A special kind of combinatorial auction is the so-called matrix bid auction, which was ...
Comments