Dynamic Matching Problems with Application to Kidney Allocation

动态匹配问题在肾脏分配中的应用

• 批准号: 2137286
• 负责人: Itai Gurvich
• 金额: $ 51.71万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-01-01 至 2024-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2137286&HistoricalAwards=false
• 关键词: Dynamic; Matching; Problems; Application; Kidney

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.

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