多捐赠者肾脏调换问题  

The multi-donor kidney exchange problem

作　　者：王刚[1] 骆志刚[1] 

机构地区：[1]国防科技大学计算机学院,湖南长沙410073

出　　处：《国防科技大学学报》2013年第6期132-137,共6页Journal of National University of Defense Technology

摘　　要：用于器官移植的肾脏处于严重的短缺状态。为缓解这一问题,越来越多的国家开始实施各种形式的肾脏调换计划。肾脏调换问题一般被建模为一个合作博弈(Kidney Exchange game,KE)。其中的局中人为病人及与其配型失败的捐赠者所构成的二元组。现实中不乏拥有多个配型捐赠者失败的病人。定义了多捐赠者肾脏调换博弈(Multi-Donor Kidney Exchange game,MDKE),分析了其可行解及稳定解的结构,证明了捐赠多颗肾脏无益于参与稳定调换,将TTC算法、KE稳定解的NP难解性以及最大覆盖稳定解的不可近似性拓展到MDKE。实验表明引入MDKE效果显著。The kidney for transplantation is in serious shortage. To alleviate this problem, more and more countries have started various kidney exchange programs. The kidney exchange problem （ KE ） is generally modeled as a cooperative game. Each player represents an incompatible patient-donor pair. A patient may have more than one incompatible donor in reality. In light of this, the multi-donor kidney exchange game （MDKE） was defined. The structures of MDKE~ feasible solutions and stable solutions were studied. It was proved that donating multiple kidneys is useless in joining in a better stable solution. Furthermore, the TTC algorithm, the NP-hardness of a stable solution and the inapproximability of a maximum cover stable solution of KE were extended to MDKE. Experiments show the effectiveness of MDKE.

关 键 词：肾脏调换 合作博弈 核心 稳定解 圈包装 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]