Abstract: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's 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.