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.