Marie van den Bogaard

The Complexity of Subgame-perfect Equilibria in Parity and Mean-payoff Games

In this paper, we prove that the SPE constrained existence problem, i.e. the problem of deciding, in a given game, the existence of a subgame-perfect equilibrium that generates a payoff profile between two given thresholds, is \(\mathsf {NP} \) -complete for both parity games and mean-payoff games. For that purpose, we...