Complexity analysis reveals that constrained existence of subgame-perfect equilibria is NP-complete in parity and mean-payoff games, highlighting foundational computational limits in game theory.
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 \(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.
No takes yet. Share an insight, caveat, or question.
Brice et al. (2026) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: