{"docId":4940,"paperId":3794,"url":"https:\/\/lmcs.episciences.org\/3794","doi":"10.23638\/LMCS-14(4:9)2018","journalName":"Logical Methods in Computer Science","issn":"","eissn":"1860-5974","volume":[{"vid":346,"name":"Volume 14, Issue 4"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"1507.04500","repositoryVersion":4,"repositoryLink":"https:\/\/arxiv.org\/abs\/1507.04500v4","dateSubmitted":"2017-07-18 10:38:20","dateAccepted":"2018-10-31 12:13:46","datePublished":"2018-10-31 12:14:17","titles":["The Complexity of All-switches Strategy Improvement"],"authors":["Fearnley, John","Savani, Rahul"],"abstracts":["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."],"keywords":["Computer Science - Data Structures and Algorithms","Computer Science - Computational Complexity","Computer Science - Computer Science and Game Theory","Computer Science - Logic in Computer Science"]}