eng
episciences.org
Logical Methods in Computer Science
1860-5974
2018-10-31
Volume 14, Issue 4
10.23638/LMCS-14(4:9)2018
3794
journal article
The Complexity of All-switches Strategy Improvement
John Fearnley
Rahul Savani
https://orcid.org/0000-0003-1262-7831
Strategy improvement is a widely-used and well-studied class of algorithms
for solving graph-based infinite games. These algorithms are parameterized by a
switching rule, and one of the most natural rules is "all switches" which
switches as many edges as possible in each iteration. Continuing a recent line
of work, we study all-switches strategy improvement from the perspective of
computational complexity. We consider two natural decision problems, both of
which have as input a game $G$, a starting strategy $s$, and an edge $e$. The
problems are: 1.) The edge switch problem, namely, is the edge $e$ ever
switched by all-switches strategy improvement when it is started from $s$ on
game $G$? 2.) The optimal strategy problem, namely, is the edge $e$ used in the
final strategy that is found by strategy improvement when it is started from
$s$ on game $G$? We show $\mathtt{PSPACE}$-completeness of the edge switch
problem and optimal strategy problem for the following settings: Parity games
with the discrete strategy improvement algorithm of V\"oge and Jurdzi\'nski;
mean-payoff games with the gain-bias algorithm [14,37]; and discounted-payoff
games and simple stochastic games with their standard strategy improvement
algorithms. We also show $\mathtt{PSPACE}$-completeness of an analogous problem
to edge switch for the bottom-antipodal algorithm for finding the sink of an
Acyclic Unique Sink Orientation on a cube.
https://lmcs.episciences.org/3794/pdf
Computer Science - Data Structures and Algorithms
Computer Science - Computational Complexity
Computer Science - Computer Science and Game Theory
Computer Science - Logic in Computer Science