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的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的审查标准通过评估来进行评估的。