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 is NP-hard. It was one of the main obstacles to a national kidney exchange. We developed an algorithm capable of clearing 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 a dynamic problem where patient-donor pairs and altruistic donors appear and expire over time. We first developed trajectory-based online stochastic optimization algorithms (that use our optimal offline solver as a subroutine) for this. Such algorithms tend to be too compute-intensive at run time, so recently we developed a general approach for giving batch algorithms guidance about the future without a run-time hit. It learns potentials of elements of the problem, and then uses them in each batch clearing.
I will share experiences from using our algorithms to run the UNOS US-wide kidney exchange and two regional ones. We introduced several design enhancements to the exchanges. For one, we used our algorithms to launch the first never-ending altruistic donor chains. I will present new results - both theoretical and experimental - on the role of long chains. I will also discuss a brand new optimal probabilistic planning algorithm for this domain that generates plans that are robust against last-minute execution failures.
The talk covers material from the following papers:
-Failure-Aware Kidney Exchange. EC-13. (With Dickerson, J. and Procaccia, A.)
-The Organ Procurement and Transplantation Network (OPTN) Kidney Paired Donation Pilot Program (KPDPP): Review of Current Results. American Transplant Congress (ATC), 2013. (With Leishman, R., Formica, R., Andreoni, K., Friedewald, J., Sleeman, E., Monstello, C., and Stewart, D.)
-Dynamic Matching via Weighted Myopia with Application to Kidney Exchange. AAAI-12. (With Dickerson, J. and Procaccia, A.)
-Optimizing Kidney Exchange with Transplant Chains: Theory and Reality. AAMAS-12. (With Dickerson, J. and Procaccia, A.)
-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 at Carnegie Mellon University in the Computer Science Department, Machine Learning Department, and CMU/UPitt Joint Ph.D. Program in Computational Biology. He is the Founder and Director of the Electronic Marketplaces Laboratory. He has published over 450 papers on market design, optimization (search and integer programming, stochastic optimization, and convex optimization), game theory, auctions and exchanges, automated negotiation and contracting, coalition formation, voting, electronic commerce, preference elicitation, normative models of bounded rationality, resource-bounded reasoning, game solving, equilibrium finding, safe exchange, and machine learning. He has over 20 years of experience building optimization-based electronic marketplaces, and has fielded several of his systems. In parallel with his academic career, 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 of the world's largest-scale generalized combinatorial auctions, with over $60 billion in total spend and over $6 billion in generated savings. Dr. Sandholm's algorithms also run the US-wide UNOS kidney exchange. He is Founder and CEO of Optimized Markets, Inc., a startup that is bringing a new paradigm to advertising sales and scheduling. He also served as the redesign consultant of Baidu's sponsored search auctions; within two years Baidu's market cap increased 5x to $50 billion due to better monetization. He has served as consultant, advisor, or board member for Yahoo!, Google, Rare Crowds, Granata Decision Systems, Netcycler, and others. He has applied his game-solving algorithms to develop some of the world's best poker-playing programs. He holds a Ph.D. and M.S. in computer science and a Dipl. Eng. (M.S. with B.S. included) with distinction in Industrial Engineering and Management Science. Among his many honors are the Computers and Thought Award, inaugural ACM Autonomous Agents Research Award, Carnegie Science Center Award for Excellence, Sloan Fellowship, and NSF Career Award. He is Fellow of the ACM and AAAI.