The Complexity of All-Switches Strategy Improvement



Fearnley, JS and Savani, RSJ ORCID: 0000-0003-1262-7831
(2018) The Complexity of All-Switches Strategy Improvement. Logical Methods in Computer Science, 14 (4). 1 - 57.

This is the latest version of this item.

[img] Text
abstract.pdf - Accepted Version
Available under License : See the attached licence file.

Download (357kB)
[img] Text
note.pdf - Accepted Version
Available under License : See the attached licence file.

Download (547kB)

Abstract

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

Item Type: Article
Uncontrolled Keywords: Computer Science, Data Structures and Algorithms,Computer Science, Computational Complexity,Computer Science, Computer Science and Game Theory,Computer Science, Logic in Computer Science
Depositing User: Symplectic Admin
Date Deposited: 12 Jan 2021 08:27
Last Modified: 16 Aug 2022 15:14
DOI: 10.23638/LMCS-14(4:9)2018
Related URLs:
URI: https://livrepository.liverpool.ac.uk/id/eprint/3113288

Available Versions of this Item