Identifying optimal strategies in Kidney Exchange games is Σ2p-complete

Bart M.L. Smeulders (Corresponding author), Danny A.M.P. Blom, Frits C.R. Spieksma

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

1 Citaat (Scopus)
71 Downloads (Pure)


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.

Originele taal-2Engels
Pagina's (van-tot)347–368
Aantal pagina's22
TijdschriftMathematical Programming
Nummer van het tijdschrift1-2
Vroegere onlinedatum21 jan. 2022
StatusGepubliceerd - jan. 2024


Duik in de onderzoeksthema's van 'Identifying optimal strategies in Kidney Exchange games is Σ2p-complete'. Samen vormen ze een unieke vingerafdruk.

Citeer dit