Dynamic Matching via Weighted Myopia with Application to Kidney Exchange

Abstract

In many dynamic matching applications — especially high-stakes ones — the competitive ratios of prior-free online algorithms are unacceptably poor. The algorithm should take distributional information about possible futures into account in deciding what action to take now. This is typically done by drawing sample trajectories of possible futures at each time period, but may require a prohibitively large number of trajectories or prohibitive memory and/or computation to decide what action to take. Instead, we propose to learn potentials of elements (e.g., vertices) of the current problem. Then, at run time, we simply run an offline matching algorithm at each time period, but subtracting out in the objective the potentials of the elements used up in the matching. We apply the approach to kidney exchange. Kidney exchanges enable willing but incompatible patient-donor pairs (vertices) to swap donors. These swaps typically include cycles longer than two pairs and chains triggered by altruistic donors. Fielded exchanges currently match myopically, maximizing the number of patients who get kidneys in an offline fashion at each time period. Myopic matching is sub-optimal; the clearing problem is dynamic since patients, donors, and altruists appear and expire over time. We theoretically compare the power of using potentials on increasingly large elements: vertices, edges, cycles, and the entire graph (optimum). Then, experiments show that by learning vertex potentials, our algorithm matches more patients than the current practice of clearing myopically. It scales to exchanges orders of magnitude beyond those handled by the prior dynamic algorithm.