Identifying optimal strategies in kidney exchange games is Σ2p-complete
成果类型：
Article
署名作者：
Smeulders, B.; Blom, D. A. M. P.; Spieksma, F. C. R.
署名单位：
Eindhoven University of Technology
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01748-6
发表日期：
2024
页码：
347-368
关键词：
摘要：
In Kidney Exchange Games, agents (e.g. hospitals or national organizations) have control over a number of incompatible recipient-donor pairs whose recipients are in need of a transplant. Each agent has the opportunity to join a collaborative effort which aims to maximize the 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 recipients under its control. Then, the question becomes: which recipient-donor pairs to submit to the collaborative effort? We model this situation by introducing the Stackelberg Kidney Exchange Game, a game where an agent, having perfect information, needs to identify a strategy, i.e., to decide which recipient-donor pairs to submit. We show that even in this simplified setting, identifying an optimal strategy is Sigma(p)(2)-complete, whenever we allow exchanges involving at most a fixed number K >= 3 pairs. However, when we restrict ourselves to pairwise exchanges only, the problem becomes solvable in polynomial time.