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

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)
64 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.

Original languageEnglish
Pages (from-to)347–368
Number of pages22
JournalMathematical Programming
Issue number1-2
Early online date21 Jan 2022
Publication statusPublished - Jan 2024


  • Computational complexity
  • Kidney exchange programmes
  • Stackelberg games
  • Σ


Dive into the research topics of 'Identifying optimal strategies in Kidney Exchange games is Σ2p-complete'. Together they form a unique fingerprint.

Cite this