We establish that the subgame perfect equilibrium (SPE) threshold problem for mean-payoff games is NP-complete. While the SPE threshold problem was recently shown to be decidable (in doubly exponential time) and NP-hard, its exact worst case complexity was left open.
Related papers
Ranked by semantic similarity — how closely each paper's abstract matches this one (100% = near-identical topic).