John Fearnley ; Rahul Savani - The Complexity of All-switches Strategy Improvement

lmcs:3794 - Logical Methods in Computer Science, October 31, 2018, Volume 14, Issue 4 - https://doi.org/10.23638/LMCS-14(4:9)2018
The Complexity of All-switches Strategy Improvement

Authors: John Fearnley ; Rahul Savani ORCID-iD

    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öge 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.


    Volume: Volume 14, Issue 4
    Published on: October 31, 2018
    Accepted on: October 31, 2018
    Submitted on: July 18, 2017
    Keywords: Computer Science - Data Structures and Algorithms,Computer Science - Computational Complexity,Computer Science - Computer Science and Game Theory,Computer Science - Logic in Computer Science

    Share

    Consultation statistics

    This page has been seen 429 times.
    This article's PDF has been downloaded 287 times.