Design and Algorithms for Modern Kidney Exchanges
Tuomas Sandholm
Carnegie Mellon University
May 7, 2009
Bailey 207

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 presented the first algorithm capable of clearing these exchanges optimally on a nationwide scale. Furthermore, clearing is an online problem where patient-donor pairs and altruistic donors appear and expire over time. Recently we developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. They outperform the current practice of solving each batch separately. I will share my experiences from using our algorithms in real kidney exchanges, and the generalizations we introduced. For one, we used them to launch the first never-ending altruistic donor chains. I am also involved with UNOS in designing the nationwide kidney exchange. I will discuss design considerations in modern kidney exchanges.

The talk will cover the following papers:

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.)

Online Stochastic Optimization in the Large: Application to Kidney Exchange. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 2009. (With Awasthi, P.)

Clearing Algorithms for Barter Exchange Markets: Enabling Nationwide Kidney Exchanges. In Proceedings of the ACM Conference on Electronic Commerce, 2007. (With Blum, A. and Abraham, D.)

Tuomas Sandholm is Professor in the Computer Science Department at Carnegie Mellon University. He has published over 350 papers on electronic commerce; game theory; artificial intelligence; multiagent systems; auctions and exchanges; automated negotiation and contracting; coalition formation; voting; safe exchange; normative models of bounded rationality; resource-bounded reasoning; machine learning; networks; and combinatorial optimization. He has 19 years of experience building optimization-based electronic marketplaces, and has fielded several of his systems. He is also Founder, Chairman, and Chief Scientist of CombineNet, Inc., which has commercialized over 600 large-scale generalized combinatorial auctions, with over $40 billion in total spend and over $5 billion in generated savings. 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 National Science Foundation Career Award, the inaugural ACM Autonomous Agents Research Award, the Alfred P. Sloan Foundation Fellowship, and the Computers and Thought Award. He is Fellow of the ACM and AAAI. See his website for more information.

Jointly hosted with the Math department.

Please email Kristina Striegnitz ( if you have any questions concerning the seminar series or if you would like to receive the seminar announcements by email.