AitF: Algorithms and Mechanisms for Kidney Exchange

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

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.