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-交流方式？两个患者-供体对交换肾脏，即第一个供体捐献给第二个患者，第二个供体捐献给第一个患者。但沿着沿着更长周期甚至链条的交换也在发生。近年来，在经济学家和计算机科学家的工作基础上，几个肾脏交换项目已经开始运作。虽然已经取得了重大进展，但计算机科学在肾脏交换研究中发挥着更大的作用。事实上，这项提案的主题是肾脏交换的挑战引发了大量令人兴奋的理论问题。此外，解决这些问题很重要：这些问题对现实世界肾脏交换计划的设计和优化很重要。本提案的首要目标是缩小肾脏交换理论与实践之间的差距。拟议的研究将纳入要素，如3路交流，加权优势，并链发起的利他捐助者到现有的工作和开发新的模型，？同时仍然是现实的抽象？能够提炼出实际肾脏交换挑战的精髓。因此，该项目可以影响肾脏交换计划的发展，这些计划仍处于起步阶段。具体而言，该项目主要集中在两个研究方向：1。处理激励措施：移植中心最关心的是他们自己的病人。因此，如果各个移植中心都不能确信他们自己的病人参加交换会比不参加交换会至少有同样的效果，那么他们可能不会参加。更微妙的是，移植中心可能会加入，但“隐藏”他们的移植匹配的病人。这项研究旨在解决这两个挑战。目标是为产生最佳或接近最佳解决方案的交换开发算法和分析，同时为移植中心加入提供强有力的激励保证。2.处理交叉匹配：交叉配血试验需要混合潜在献血者和患者的血液样本，因此仅在计算匹配后进行。不幸的是，交叉匹配测试很可能失败，导致大部分被认为是最佳的交易所崩溃。与当今的常见做法相比，考虑交叉匹配的优化提供了显着的收益。该提案包含了更广泛地发展交叉配型测试整合到优化中的完整理论和算法理解以及所涉及的基本权衡的计划。

项目成果

Advancing Subgroup Fairness via Sleeping Experts

通过沉睡的专家促进子群体公平

• 发表时间: 2020
• 期刊: Innovations in Theoretical Computer Science Conference (ITCS
• 作者: Blum, Avrim;Lykouris, Thodoris
• 通讯作者: Lykouris, Thodoris

One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning

• 发表时间: 2021-03
• 期刊: ArXiv
• 作者: Avrim Blum;Nika Haghtalab;R. L. Phillips;Han Shao

Low-Distortion Social Welfare Functions

• DOI: 10.1609/aaai.v33i01.33011788
• 发表时间: 2019-07
• 作者: Gerdus Benade;Ariel D. Procaccia;Mingda Qiao

Bilu-Linial stability, certified algorithms and the Independent Set problem

• DOI: 10.4230/lipics.esa.2019.7
• 发表时间: 2018-10
• 期刊: ArXiv
• 作者: Haris Angelidakis;Pranjal Awasthi;Avrim Blum;Vaggos Chatziafratis;Chen Dan

Efficient and Thrifty Voting by Any Means Necessary

采取任何必要手段进行高效、节俭的投票

• 发表时间: 2019
• 期刊: NeurIPS'19
• 作者: Mandal, D;Procaccia, AD;Shah, N;Woodruff, DP
• 通讯作者: Woodruff, DP