论文标题
平均付款游戏中SPE的复杂性
The Complexity of SPEs in Mean-payoff Games
论文作者
论文摘要
我们确定平均付款游戏的子游戏子游戏完美平衡（SPE）阈值问题是NP完整的。尽管最近显示出SPE阈值问题是可决定的（以双重指数时间为单位）和NP-HARD，但其确切的最坏情况的复杂性被打开了。
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.
