HCIL BBL: Better Matching Markets via Optimization
Better Matching Markets via Optimization
John Dickerson (University of Maryland, College Park)
HCIL (2105 Hornbake, South Wing)
The exchange of indivisible goods without money addresses a variety of constrained economic settings where a medium of exchange—such as money—is considered inappropriate. Participants are either matched directly with another participant or, in more complex domains, in barter cycles and chains with other participants before exchanging their endowed goods. We show that techniques from computer science and operations research, combined with the recent availability of massive data and inexpensive computing, can guide the design of such matching markets and enable the markets by running them in the real world.
A key application domain for our work is kidney exchange, an organized market where patients with end-stage renal failure swap willing but incompatible donors. We present new models that address three fundamental dimensions of kidney exchange: (i) uncertainty over the existence of possible trades, (ii) balancing efficiency and fairness, and (iii) inherent dynamism. For each dimension, we design scalable branch-and-price-based integer programming market clearing methods. Next, we combine these dimensions, along with high-level human-provided guidance, into a unified framework for learning to match in a general dynamic setting. This framework, which we coin FutureMatch, takes as input a high-level objective (e.g., “maximize graft survival of transplants over time”) decided on by experts, then automatically learns based on data how to make this objective concrete and learns the “means” to accomplish this goal—a task that, in our experience, humans handle poorly.
John Dickerson is an Assistant Professor in the Department of Computer Science at the University of Maryland, College Park. I’m the lead developer of the US nationwide kidney exchange program, and lead developer of a better way to deal with TV advertisements (currently in the pilot phase with two of the nation’s largest MSOs). He holds a PhD in Computer Science from Carnegie Mellon University, and has been supported by a Facebook Fellowship, Siebel Scholarship, and an NDSEG Fellowship.