Design and Algorithms for Dynamic Kidney Exchanges

Monday, January 30, 2012 - 11:25am


10:30 AM – 11:00 AM Reception
11:00 AM – 12:00 PM Talk
Engineering Sciences Building, Room 1001

HOST: Subhash Suri

SPEAKER: Tuomas Sandholm
Professor, Computer Science Department
Carnegie Mellon University


Design and Algorithms for Dynamic Kidney Exchanges


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


Tuomas Sandholm is Professor in the Computer Science Department at
Carnegie Mellon University. He has published over 430 papers on game
theory; electronic commerce; artificial intelligence; 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 $60 billion in total spend
and over $6 billion in generated savings. Since early 2009, he has been
the design consultant of Baidu’s sponsored search auctions; Baidu’s
market cap increased 5x to $50 billion during this period due to better
monetization. He has also consulted for Yahoo!, Netcycler, Google, and
others. He holds a Ph.D. and M.S. in computer science and an M.S. (B.S.
included) with distinction in Industrial Engineering and Management
Science. 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.