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.