AitF: Algorithms and Mechanisms for Kidney Exchange

AitF：肾脏交换的算法和机制

基本信息

批准号：
1733556
负责人：
Ariel Procaccia
金额：
$ 79.96万
依托单位：
Carnegie-Mellon University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-10-01 至 2022-09-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1733556&HistoricalAwards=false
关键词：
AitF Algorithms Mechanisms Kidney Exchange

项目摘要

Severe cases of renal failure require kidney transplantation. But the demand for kidneys is huge while the supply is quite limited. Even when a willing donor is found, several hurdles must be cleared before transplantation can take place. Enter kidney exchange, the idea that patients can exchange willing but incompatible donors. In its most basic form ? 2-way exchanges ? two patient-donor pairs swap kidneys, that is, the first donor donates to the second patient and the second donor to the first patient. However, exchanges along longer cycles and even chains are also taking place. In recent years several kidney exchange programs have become operational, building on the work of economists and computer scientists. And while significant progress has already been made, computer science has an even bigger role to play in kidney exchange research. Indeed, the theme of this proposal is that challenges in kidney exchange give rise to a wealth of exciting theoretical questions. Moreover, solving these problems matters: These problems are important to the design and optimization of real-world kidney exchange programs.An overarching goal of this proposal is to narrow the gap between the theory and practice of kidney exchange. The proposed research will incorporate elements such as 3-way exchanges, weighted edges, and chains initiated by altruistic donors into existing work and develop new models that ? while still abstractions of reality ? are able to distill the essence of practical kidney exchange challenges. The project can therefore impact the evolution of kidney exchange programs, which are still in their infancy. In more detail, the project focuses on two main research directions: 1. Dealing with incentives: Transplant centers care foremost about their own patients. Thus if the individual transplant centers cannot each be confident that their own patients will fare at least as well if they participate in the exchange than if they do not, then they may not join. Even more subtly, the transplant centers may join but "hide" their easier-to-match patients. The proposed research aims to tackle both of these challenges. The goal is to develop algorithms and analysis for exchanges that produce optimal or near-optimal solutions, while providing strong incentive guarantees for transplant centers to join.2. Dealing with crossmatches: Crossmatch tests require mixing samples of the blood of potential donors and patients, and hence are only done after a matching is computed. Unfortunately, crossmatch tests are quite likely to fail, leading to the collapse of large portions of supposedly optimal exchanges. Optimization that takes crossmatches into account offers significant gains compared to the common practice today. The proposal contains plans to more broadly develop a full theoretical and algorithmic understanding of the integration of crossmatch tests into the optimization, and the fundamental tradeoffs involved.

严重的肾功能衰竭需要进行肾移植。但肾脏的需求量巨大，而供应量却相当有限。即使找到愿意的捐赠者，在进行移植之前也必须清除一些障碍。肾脏交换是指患者可以交换愿意但不相容的捐赠者。最基本的形式？ 2 路交换 ?两对患者-捐赠者交换肾脏，即第一个捐赠者捐赠给第二个患者，第二个捐赠者捐赠给第一个患者。但更长周期甚至链条的交换也在发生。近年来，在经济学家和计算机科学家的工作基础上，一些肾脏交换项目已经开始运作。尽管已经取得了重大进展，但计算机科学在肾脏交换研究中可以发挥更大的作用。事实上，该提案的主题是肾脏交换的挑战引发了大量令人兴奋的理论问题。此外，解决这些问题也很重要：这些问题对于现实世界的肾脏交换项目的设计和优化非常重要。该提案的首要目标是缩小肾脏交换理论与实践之间的差距。拟议的研究将把由利他捐助者发起的三向交换、加权边缘和链等元素纳入现有工作中，并开发新模型？同时仍然是现实的抽象？能够提炼出实际肾脏交换挑战的精髓。因此，该项目可以影响仍处于起步阶段的肾脏交换计划的发展。更详细地说，该项目侧重于两个主要研究方向： 1. 处理激励措施：移植中心最关心的是自己的患者。因此，如果各个移植中心不能确信自己的患者参加交换至少会比不参加交换的情况好，那么他们就可能不会加入。更巧妙的是，移植中心可能会加入但“隐藏”更容易匹配的患者。拟议的研究旨在解决这两个挑战。目标是为交易所开发算法和分析，产生最优或接近最优的解决方案，同时为移植中心的加入提供强有力的激励保证。2．处理交叉配血：交叉配血测试需要混合潜在捐献者和患者的血液样本，因此只有在计算匹配后才能进行。不幸的是，交叉匹配测试很可能会失败，导致大部分所谓的最佳交换崩溃。与当今的常见做法相比，考虑交叉匹配的优化可带来显着的收益。该提案包含更广泛地发展对交叉匹配测试与优化的集成以及所涉及的基本权衡的完整理论和算法理解的计划。

项目成果

期刊论文数量（171）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games

顺序决策和扩展博弈的强盗线性优化

DOI：
发表时间：
2021-01
期刊：
AAAI Annual conference
影响因子：
0
作者：
Farina, G.;Schmucker, R.;Sandholm, T.
通讯作者：
Sandholm, T.

Bayesian Multiagent Inverse Reinforcement Learning for Policy Recommendation

用于政策建议的贝叶斯多智能体逆强化学习

DOI：
发表时间：
2021-01
期刊：
AAAI-21 Workshop on Reinforcement Learning in Games
影响因子：
0
作者：
Martin, C.;Sandholm, T.
通讯作者：
Sandholm, T.

Dynamic Placement in Refugee Resettlement

难民安置中的动态安置

DOI：
发表时间：
2021-01
期刊：
EC
影响因子：
0
作者：
Ahani, Narges;Gölz, Paul;Procaccia, Ariel D.;Teytelboym, Ale;Trapp, Andrew
通讯作者：
Trapp, Andrew

Inverse Reinforcement Learning From Like-Minded Teachers

向志趣相投的老师学习逆向强化学习

DOI：
发表时间：
2021-01
期刊：
AAAI
影响因子：
0
作者：
Noothigattu, Ritesh;Yan, Tom;Procaccia, Ariel D.
通讯作者：
Procaccia, Ariel D.

Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games

扩展型零和博弈中最优事前协调共谋策略的更快算法

DOI：
发表时间：
2021-01
期刊：
AAAI Workshop on Reinforcement Learning in Games
影响因子：
0
作者：
Farina, G.;Celli, A.;Gatti, N.;Sandholm, T.
通讯作者：
Sandholm, T.

DOI：
{{ item.doi }}
发表时间：
{{ item.publish_year }}
期刊：
{{ item.journal_name }}
影响因子：
{{ item.factor }}
作者：
{{ item.authors }}
通讯作者：
{{ item.author }}

数据更新时间：{{ journalArticles.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ monograph.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ sciAawards.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ conferencePapers.updateTime }}

作者：
{{ item.author }}

数据更新时间：{{ patent.updateTime }}

Ariel Procaccia其他文献

In defense of liquid democracy

捍卫流动民主

DOI：
发表时间：
2023-07
期刊：
Twenty-fourth ACM Conference on Electronic Commerce
影响因子：
0
作者：
Daniel Halpern;Joseph Y. Halpern, Ali Jadbabaie;Elchanan Mossel;Ariel Procaccia;Manon Revel
通讯作者：
Manon Revel