摘要：Strategy improvement is a widely-used and well-studied class of algorithmsfor solving graph-based infinite games. These algorithms are parameterized by aswitching rule, and one of the most natural rules is "all switches" whichswitches as many edges as possible in each iteration. Continuing a recent lineof work, we study all-switches strategy improvement from the perspective ofcomputational complexity. We consider two natural decision problems, both ofwhich have as input a game $G$, a starting strategy $s$, and an edge $e$. Theproblems are: 1.) The edge switch problem, namely, is the edge $e$ everswitched by all-switches strategy improvement when it is started from $s$ ongame $G$? 2.) The optimal strategy problem, namely, is the edge $e$ used in thefinal strategy that is found by strategy improvement when it is started from$s$ on game $G$? We show $\mathtt{PSPACE}$-completeness of the edge switchproblem and optimal strategy problem for the following settings: Parity gameswith the discrete strategy improvement algorithm of V\"oge and Jurdzi\'nski;mean-payoff games with the gain-bias algorithm [14,37]; and discounted-payoffgames and simple stochastic games with their standard strategy improvementalgorithms. We also show $\mathtt{PSPACE}$-completeness of an analogous problemto edge switch for the bottom-antipodal algorithm for finding the sink of anAcyclic Unique Sink Orientation on a cube.
关键词：Computer Science - Data Structures;Algorithms;Computer Science - Computational Complexity;Computer Science - Computer Science;Game Theory;Computer Science - Logic in Computer Science
