论文标题
Stackelberg肾脏交换问题是$σ_2^p $ -complete
The Stackelberg Kidney Exchange Problem is $Σ_2^p$-complete
论文作者
论文摘要
我们介绍了Stackelberg肾脏交换问题。在此问题中，代理（例如医院或国家组织）控制了许多不兼容的患者唐纳对患者，其患者需要移植。代理商有机会加入协作努力，旨在增加可以实现的最大移植总数。但是，单个药物仅有兴趣最大程度地利用其控制患者组中的移植数量。然后，问题变成了要服从合作努力的患者。我们表明，每当我们允许最多涉及固定数字$ k \ ge 3 $对的交换时，回答此问题为$σ_2^p $ -complete。但是，当我们仅限于成对交换时，问题在多项式时间内就可以解决
We introduce the Stackelberg kidney exchange problem. In this problem, an agent (e.g. a hospital or a national organization) has control over a number of incompatible patient-donor pairs whose patients are in need of a transplant. The agent has the opportunity to join a collaborative effort which aims to increase the maximum total number of transplants that can be realized. However, the individual agent is only interested in maximizing the number of transplants within the set of patients under its control. Then, the question becomes which patients to submit to the collaborative effort. We show that, whenever we allow exchanges involving at most a fixed number $K \ge 3$ pairs, answering this question is $Σ_2^p$-complete. However, when we restrict ourselves to pairwise exchanges only, the problem becomes solvable in polynomial time
