RI: Medium: Algorithms for Robust Barter Exchanges, with Application to Kidneys

仅在美国，每年就有超过3万人患上致命的肾脏疾病，超过7.7万人等待肾脏移植，比其他任何移植手术都要多。这种需求远远超过了尸体肾脏的供应。活着的人可以将肾脏捐赠给亲戚或朋友，而且两人都能活得很好。不幸的是，由于血型和组织类型不相容，给定的献血者不太可能向给定的患者捐献。这为肾脏交换打开了大门。考虑两对供体-患者，A和b。假设每对供体-患者都不相容。然而，供体A可以捐赠给患者B，供体B也可以捐赠给患者A。这构成了一个长度为2的循环。稍长的周期也是可行的。首席研究员之前的研究证明了交易所清算问题是np完全的，并开发了一种可扩展到全国范围的交易所算法。该奖项下的研究正在扩大和扩展交换算法的功能，以开发(a)更快的交换算法（例如，通过搜索树重组），(b)根据不断变化的供体和受体决定选择哪个周期的在线算法，(c)对最后一刻失败具有鲁棒性的算法，以及(d)使用机器学习来预测肾脏移植的生存时间和最后一刻测试的失败概率。为解决这些问题而开发的一些技术和理论也适用于其他组合搜索问题。该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。

In the US alone, over 30,000 fall sick with lethal kidney disease each year, and over 77,000 await for a kidney transplant, many more than any other transplant. That demand far exceeds the supply of cadaver kidneys. It is possible for a living person to donate a kidney, e.g., to a relative or a friend, and both can live well. Unfortunately, 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. Consider two donor-patient pairs, A and B. Say that each of the pairs is incompatible. Yet Donor A may be able to donate to Patient B, and Donor B to Patient A. This constitutes a cycle of length two. Somewhat longer cycles are also practical. The principal investigator's prior research has proved that the exchange clearing problem is NP-complete, and developed an exchange algorithm that scales to the nationwide level. Research under this award is scaling up and expanding the functionality of the exchange algorithms to develop (a) faster exhange algorithms (e.g., through search-tree reorganization), (b) online algorithms for deciding which cycles to select in light of changing donors and recipients, (c) algorithms that are robust to last-minute failures, and (d) using machine learning to predict the survival duration of kidney transplants and failure probabilities of last-minute tests. Some of the techniques and theory developed to address these issues also apply to other combinatorial search problems.This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).