RI: Small: New Computational Techniques and Market Designs for Kidney Exchanges and Other Barter Markets

仅在美国，每年就有3.5万名患有晚期肾脏疾病的患者加入死亡捐赠者的等待名单，10万人等待肾脏移植——比所有其他实体器官移植的总和还要多。这种需求远远超过了死者捐献肾脏的供应。活着的人捐献肾脏是可能的，但由于血型和组织类型不相容，特定的捐赠者不太可能捐赠给特定的患者。这为肾脏交换打开了大门，在这里，这些自愿的捐赠者-患者对“交换”捐赠者。在现代肾脏交换中，这些“交换”是通过循环和利他主义者-捐赠者发起的链条进行的。在开发肾脏交换的方法、算法和软件方面的前期工作已经被美国两个最大的区域性肾脏交换所使用。更重要的是，它管理着器官共享联合网络（UNOS）全国肾脏交换，其中包括153个移植中心。这项工作揭示了物物交换中无数悬而未决的问题，这笔拨款将通过开发计算技术、进行计算实验和研究成果来解决这些问题。仅在美国，这项资助下的研究每年就有可能挽救数百人的生命，而与已故捐赠者等待名单的整合有可能挽救数千人的生命。该方法还通过使患者摆脱透析并重新投入生产性工作，从而显著改善了生活质量。社会效益还来自于移植比透析更便宜；据独立机构估计，这一影响在美国五年内造成了7.5亿美元的损失。该项目将重点关注肾脏交换和其他易货市场的四个方面：1。为动态问题开发自动导出市场出清政策的计算技术；2)开发计算技术，自动动态确定哪些边缘（可能的捐赠）需要测试兼容性和其他可行性；3)开发市场设计和计算技术，整合死者供体等待名单和肾脏交换；4)开发市场设计和计算技术，使患者可以有多个供体，反之亦然。这里开发的技术也将适用于其他广泛领域的其他易货交换。

In the US alone, 35,000 patients with terminal kidney disease get added to the deceased-donor wait list each year, and 100,000 await for a kidney transplant - more than all other solid-organ transplants combined. That demand far exceeds the supply of deceased-donor kidneys. It is possible for a living person to donate a kidney, but it is unlikely that a given donor can donate to a given patient due to blood type and tissue type incompatibilities. This opens the door for kidney exchange where such willing donor-patient pairs "swap" donors. In modern kidney exchanges these "swaps" are conducted via cycles and altruist-donor-initiated chains. Prior work in developing the methods, algorithms, and software for kidney exchanges has already been used by two of the largest regional kidney exchanges in the US. More importantly, it runs the United Network for Organ Sharing (UNOS) nationwide kidney exchange, which includes 153 transplant centers. This work has uncovered a myriad of open problems in barter exchanges, which this grant will address by developing computational techniques, conducting computational experiments, and fielding the fruits of the research. The research under this grant has the potential to save hundreds of lives annually in the US alone, and the integration with the deceased-donor waiting list has the potential to save thousands. The approach also leads to dramatic improvements in the quality of life by moving patients off dialysis and back into the productive work force. Societal benefits come also from transplants being less expensive than dialysis; this effect has been independently estimated to be $750 million in the US over five years. This project will focus on four prongs for kidney exchanges and other barter markets, as follows: 1. developing computational techniques for automatically deriving market-clearing policies for dynamic problems; 2) developing computational techniques for automatically determining dynamically which edges (possible donations) to test for compatibility and other viability; 3) developing market designs and computational techniques for integrating the deceased-donor waiting list and kidney exchange; and 4) developing market designs and computational techniques for generalizations where a patient can have multiple donors and vice versa. The techniques developed here will apply to other barter exchanges in a broad range of other domains as well.