Dynamic Matching Problems with Application to Kidney Allocation

该奖项将通过研究在线配对平台的改进策略，特别是肾脏交换，为国家福利做出贡献。用于移植的肾脏的短缺产生了对肾脏交换的需求，不相容的患者-供体配对交换捐赠的移植器官。器官匹配的质量由许多因素决定，包括血型和抗体状况、患者和献血者的年龄和健康状况，以及接受者等待交换器官的时间。负责安排这些匹配的肾脏交换平台面临着权衡，是在确定可行的供体-受体配对后立即进行匹配，还是等待其他配对的到来以提高匹配的质量。在其他在线服务平台上也出现了类似的权衡，比如拼车和工作匹配，匹配算法寻求通过汇集客户来尽可能多地服务，这可能会减少拥堵，并迅速响应个别乘客的请求。该项目将研究模型和数据，以更好地理解这些权衡，并为管理这些交换的政策制定者提供指导。该项目将通过研究尚未开发但具有重要实际意义的模型来改善交流平台，这些模型可以更普遍地阐明良好政策的基本要素。该项目将支持研究生获得使用运筹学方法的经验，这些方法有可能显著改善美国的医疗保健政策。该项目研究了用于匹配的动态排队模型，其中代理到达并立即进行匹配，或者将其放置在队列（等待列表）中以获得可能更好的匹配。一场比赛涉及多个代理，结果是奖励；延迟（队列中的等待）可能导致代理离开或其他不利效用，例如健康状况恶化。在每个时间点，匹配策略决定是否执行以及执行哪些可行的匹配。离开（放弃）和队列中的延迟使这些计算复杂化，因为匹配机会过期，并且由于等待条件可能降低，放弃的匹配也可能取消未来的机会。该项目将严格研究在现实网络中表现良好的动态匹配策略，方法如下：(1)确定好策略的基本成分，并确定设计可实现交换协议的自由度；(2)了解遗弃的影响和情况随时间的变化；(3)使用来自两个美国交换平台的交易级数据测试潜在的协议。为了便于处理，数学模型不能完全捕捉摩擦的所有来源。为该项目开发的高保真数据驱动模拟将揭示哪些摩擦对性能有一阶影响，并将为排队模型的调整提供信息。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.