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

Abstract

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 use the notion of negotiation function, and the fact that a play is compatible with an SPE if and only if it is consistent with a fixed point of that function. Our algorithms consist in guessing (1) such a fixed point, (2) a certificate of the existence of a play consistent with that fixed points that matches the constraints, and (3) a certificate proving that it is a fixed point.