The Complexity of SPEs in Mean-payoff Games

02/17/2022

∙

by   Léonard Brice, et al.

∙

0

∙

share

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.