We are pleased to have Prof. Tuomas Sandholm
from Carnegie Mellon University as our invited speaker.
Modern Organ Exchanges: Generalized Matching under Dynamics, Edge Failures, and Fairness
In kidney exchanges, patients with kidney disease can obtain compatible donors by swapping their own willing but incompatible donors. The vanilla clearing problem involves finding an optimal set of non-overlapping short cycles. We proved this is NP-hard. 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.
Our algorithms autonomously make the transplant plan twice a week for the UNOS national kidney exchange that has 153 transplant centers. The algorithms have also been used by two private exchanges. We introduced several design enhancements to kidney exchange. For one, we used our algorithms to launch the first never-ending altruist-donor-initiated barter chains. I will present results regarding long chains. I will also present a new integer program model where edges in chains are position indexed, and show that it outperforms prior approaches.
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 for this. 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. Then, I will present an algorithm that finds the highest expected value plan in the face of pre-transplant failures such as last-minute incompatibilities. I will present new computational approaches for dynamic compatibility testing.
I will also discuss approached for striking the fairness-efficiency tradeoff well. Finally, I will describe the FUTUREMATCH framework that combines all these elements and uses data to learn a concrete objective from high-level human value judgments.
We show that similar approaches could be used to set up exchanges for liver lobes, and cross-organ exchanges.
Different parts of this work are joint with dozens of different collaborators, as detailed in the presentation.
Tuomas Sandholm is Professor at Carnegie Mellon University in the Computer Science Department, with affiliate professor appointments in the Machine Learning Department, Ph.D. Program in Algorithms, Combinatorics, and Optimization (ACO), 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. He has 26 years of experience building optimization-powered 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 multi-attribute auctions, with over $60 billion in total spend and over $6 billion in generated savings. Dr. Sandholm’s algorithms also run the UNOS kidney exchange, which includes 66% of the transplant centers in the US. He is Founder and CEO of Optimized Markets, Inc., that is bringing a new paradigm to advertising campaign sales and scheduling—in linear TV, digital TV, Internet display, mobile, game, radio, and cross-media advertising. He also served as the redesign consultant of Baidu’s sponsored search auctions and display advertising markets; 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, Chicago Board Options Exchange, swap.com, Granata Decision Systems, and others. He has developed the leading algorithms for several general classes of game. They won the two most recent world championships in computer Heads-Up No-Limit Texas Hold’em. 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 NSF Career Award, inaugural ACM Autonomous Agents Research Award, Sloan Fellowship, Carnegie Science Center Award for Excellence, Edelman Laureateship, and Computers and Thought Award. He is Fellow of the ACM, AAAI, and INFORMS. He holds an honorary doctorate from the University of Zurich.