Improving Policy-Constrained Kidney Exchange via Pre-Screening
Improving Policy-Constrained Kidney Exchange via Pre-Screening
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Duncan C. McElfresh;Michael Curry;T. Sandholm;John P. Dickerson
中科院分区：
文献类型：
--
作者：
Duncan C. McElfresh;Michael Curry;T. Sandholm;John P. Dickerson
在易货交易中，参与者相互交换货物而不交换货币;交易通常由中央清算所促进，目标是最大限度地提高交换的总体质量（或数量）。易货交易受多种形式的不确定性影响--参与者的偏好、各种交换的可行性和质量等。我们的工作是由肾脏交换推动的，这是一个真实的易货市场，需要肾脏移植的患者交换他们愿意的活体捐赠者，以便找到更好的匹配。现代交换包括双向和三向交换，使得肾脏交换清算问题NP困难。计划中的移植通常会因为各种原因而失败--如果捐赠者的器官被接受者的医疗团队拒绝，或者如果捐赠者和接受者被发现在医学上不相容。由于双向和三方交换，失败的移植可以通过交换“级联”;一家美国的交换所估计，2019年约有85%的计划移植失败。许多基于优化的方法已经被设计来避免这些失败;然而，由于法律的和政策的限制，大多数交易所不能实现这些方法。相反，我们考虑的是一种环境，在这种环境中，交易所可以询问某些捐赠者和接受者的偏好--询问他们是否会接受特定的移植。我们将其描述为一个两阶段决策问题，其中交换程序（a）在提交匹配之前查询少量移植，（B）根据固定策略构建匹配。我们发现，选择这些边缘是一个具有挑战性的组合问题，这是非单调和non-submodular的，除了是NP-难的。我们提出了一个贪婪的启发式和蒙特卡洛树搜索，它优于以前的方法，使用实验的合成数据和真实的肾脏交换数据从联合网络器官共享。
In barter exchanges, participants swap goods with one another without exchanging money; exchanges are often facilitated by a central clearinghouse, with the goal of maximizing the aggregate quality (or number) of swaps. Barter exchanges are subject to many forms of uncertainty--in participant preferences, the feasibility and quality of various swaps, and so on. Our work is motivated by kidney exchange, a real-world barter market in which patients in need of a kidney transplant swap their willing living donors, in order to find a better match. Modern exchanges include 2- and 3-way swaps, making the kidney exchange clearing problem NP-hard. Planned transplants often fail for a variety of reasons--if the donor organ is refused by the recipient's medical team, or if the donor and recipient are found to be medically incompatible. Due to 2- and 3-way swaps, failed transplants can "cascade" through an exchange; one US-based exchange estimated that about 85% of planned transplants failed in 2019. Many optimization-based approaches have been designed to avoid these failures; however most exchanges cannot implement these methods due to legal and policy constraints. Instead we consider a setting where exchanges can query the preferences of certain donors and recipients--asking whether they would accept a particular transplant. We characterize this as a two-stage decision problem, in which the exchange program (a) queries a small number of transplants before committing to a matching, and (b) constructs a matching according to fixed policy. We show that selecting these edges is a challenging combinatorial problem, which is non-monotonic and non-submodular, in addition to being NP-hard. We propose both a greedy heuristic and a Monte Carlo tree search, which outperforms previous approaches, using experiments on both synthetic data and real kidney exchange data from the United Network for Organ Sharing.