Dynamic Matching Problems with Application to Kidney Allocation

This award will contribute to the Nation's welfare by investigating improved strategies for online matching platforms, with a particular focus on kidney exchanges. The shortage of kidneys for transplants has created a demand for kidney exchanges, where incompatible patient-donor pairs swap their donated transplants. The quality of an organ match is determined by a number of factors, including blood-type and antibody status, age and health condition of patients and donors, and waiting time of the recipient on the exchange.

Kidney exchange platforms, responsible for arranging these matches, face trade-offs between forming matches as soon as a feasible donor-recipient pair is identified and waiting for additional pairs to arrive in order to increase the quality of matches. A similar trade-off arises in other online service platforms, such as ride-sharing and job matching, where matching algorithms seek to balance between serving as many as possible by pooling customers, which may reduce congestion, and responding quickly to individual passengers' requests.

This project will investigate models and data to better understand these tradeoffs and provide guidance to policy makers who manage these exchanges. This project will contribute to improving exchange platforms by studying unexplored, but practically important, models that can illuminate essential ingredients of good policies more generally. The project will support graduate students who will gain experience in using operations research methods that have the potential to significantly improve healthcare policy in the United States.

The project investigates a dynamic queueing model for matching where agents arrive and are matched immediately or placed in a queue (waiting list) for a potentially better match. A match involves several agents and results in reward; a delay (the wait in queue) can result in agents' departure or other disutility, such as deterioration in health condition.

At each point in time the matching policy determines if and which of the feasible matches are to be executed. Departures (abandonments) and delays in queue complicate these calculations, as matching opportunities expire, and foregone matches may also foreclose future opportunites as conditions of those waiting may degrade. The project will rigorously study dynamic matching policies that perform well in real networks by (1) identifying the essential ingredients of good policies and determining the degrees of freedom in designing implementable exchange protocols; (2) understanding the effect of abandonments and change in condition over time; and (3) testing potential protocols with transaction-level data from two American exchange platforms.

Mathematical models, to remain tractable, cannot fully capture all sources of friction. The high-fidelity data-driven simulations developed for this project will reveal which frictions have a first order effect on performance and will inform adjustments to the queueing model.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.