Fearnley, J and Savani, R ORCID: 0000-0003-1262-7831
(2018)
The complexity of all-switches strategy improvement.
In: ACM-SIAM Symposium on Discrete Algorithms (SODA-16).
There is a more recent version of this item available. |
Text
abstract.pdf - Author Accepted Manuscript Download (357kB) |
Abstract
Strategy improvement is a widely-used and well-studied class of algorithms for solving graph-based infinite games. These algorithms are parametrized 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 Voge and Jurdzinski; mean-payoff games with the gain-bias algorithm; 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 Acyclic Unique Sink Orientations on Cubes.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Additional Information: | ** ITEM MARKED CONFIDENTIAL – HELD IN REVIEW ** |
Depositing User: | Symplectic Admin |
Date Deposited: | 01 Feb 2017 11:31 |
Last Modified: | 19 Jan 2023 07:19 |
DOI: | 10.23638/LMCS-14(4:9)2018 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3005496 |
Available Versions of this Item
- The complexity of all-switches strategy improvement. (deposited 01 Feb 2017 11:31) [Currently Displayed]