Academic Journal
Identifying optimal strategies in Kidney Exchange games is Σ2p-complete
| العنوان: | Identifying optimal strategies in Kidney Exchange games is Σ2p-complete |
|---|---|
| المؤلفون: | Smeulders, Bart M.L., Blom, Danny A.M.P., Spieksma, Frits C.R. |
| المصدر: | Smeulders , B M L , Blom , D A M P & Spieksma , F C R 2024 , ' Identifying optimal strategies in Kidney Exchange games is Σ2p-complete ' , Mathematical Programming , vol. 203 , no. 1-2 , pp. 347–368 . https://doi.org/10.1007/s10107-021-01748-6 |
| سنة النشر: | 2024 |
| مصطلحات موضوعية: | Computational complexity, Kidney exchange programmes, Stackelberg games, Σ |
| الوصف: | 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 Σ2p-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. |
| نوع الوثيقة: | article in journal/newspaper |
| وصف الملف: | application/pdf |
| اللغة: | English |
| DOI: | 10.1007/s10107-021-01748-6 |
| الاتاحة: | https://research.tue.nl/en/publications/449262e2-1f81-4098-90f0-e79edefea557 https://doi.org/10.1007/s10107-021-01748-6 https://pure.tue.nl/ws/files/195825124/Stackleberg_Kidney_Exchange_Game.pdf https://pure.tue.nl/ws/files/318886944/s10107-021-01748-6.pdf http://www.scopus.com/inward/record.url?scp=85123266012&partnerID=8YFLogxK |
| Rights: | info:eu-repo/semantics/openAccess |
| رقم الانضمام: | edsbas.88D108CA |
| قاعدة البيانات: | BASE |
| DOI: | 10.1007/s10107-021-01748-6 |
|---|