Design and Algorithms for Modern Kidney Exchanges
Computer Science Department
Carnegie Mellon University
In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The clearing problem involves finding a social welfare maximizing set of non-overlapping short cycles. We proved this NP-hard. It was one of the main obstacles to a national kidney exchange. We developed the
first algorithm capable of clearing these exchanges optimally on a nationwide scale. The key was incremental problem formulation because the formulation that gives tight LP bounds is too large to even store.
On top of the branch-and-price paradigm we developed techniques that dramatically improve runtime and memory usage. Furthermore, clearing is actually an online problem where patient-donor pairs and altruistic donors appear and expire over time. We developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. I will discuss design parameters and tradeoffs. Our best online algorithms outperform the current practice of solving each batch separately. I will share experiences from using our algorithms as the clearing engine of two large regional kidney exchanges, and since October 2010, the UNOS nationwide kidney exchange. We also introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains.
The talk covers material from the following papers:
- Online Stochastic Optimization in the Large: Application to Kidney Exchange. IJCAI-09. (With Awasthi, P.)
- A Nonsimultaneous, Extended, Altruistic-Donor Chain. New England Journal of Medicine 360(11), March 2009. (With Rees, M., Kopke, J., Pelletier, R., Segev, D., Rutter, M., Fabrega, A., Rogers, J., Pankewycz, O., Hiller, J., Roth, A., Ünver, U., and Montgomery, R.)
- Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. EC-07. (With Abraham, D. and Blum, A.)
Tuomas Sandholm is Professor in the Computer Science Department at Carnegie Mellon University. He has published over 400 papers on AI; game theory; electronic commerce; multiagent systems; auctions and exchanges; automated negotiation and contracting; coalition formation;voting; search and integer programming; safe exchange; normative models of bounded rationality; resource-bounded reasoning; machine learning;and networks. He has over 20 years of experience building optimization-based electronic marketplaces, and has fielded several of his systems. He was Founder, Chairman, and CTO/Chief Scientist of CombineNet, Inc. from 1997 until its acquisition in 2010. During this period the company commercialized over 800 large-scale generalized combinatorial auctions, with over $50 billion in total spend and over $6 billion in generated savings. Dr. Sandholm's algorithms also run the
US-wide kidney exchange. Since early 2009, he has been the design consultant of Baidu's sponsored search auctions; Baidu's market cap increased 4x to $38 billion during this period due to better monetization. He has also consulted for Yahoo!, Netcycler, Google, and others. He received the Ph.D. and M.S. degrees in computer science from the University of Massachusetts at Amherst in 1996 and 1994. He earned an M.S. (B.S. included) with distinction in Industrial Engineering and Management Science from the Helsinki University of Technology, Finland,
in 1991. He is recipient of the NSF Career Award, the inaugural ACM Autonomous Agents Research Award, the Alfred P. Sloan Foundation Fellowship, the Carnegie Science Center Award for Excellence, and the Computers and Thought Award. He is Fellow of the ACM and AAAI.