文章基本信息

标题：The Complexity of All-switches Strategy Improvement
本地全文：下载
作者：Savani, Rahul ; Fearnley, John
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2018
卷号：14
期号：4
DOI：10.23638/LMCS-14(4:9)2018
语种：English
出版社：Technical University of Braunschweig
摘要：Strategy improvement is a widely-used and well-studied class of algorithmsfor solving graph-based infinite games. These algorithms are parameterized by aswitching rule, and one of the most natural rules is "all switches" whichswitches as many edges as possible in each iteration. Continuing a recent lineof work, we study all-switches strategy improvement from the perspective ofcomputational complexity. We consider two natural decision problems, both ofwhich have as input a game $G$, a starting strategy $s$, and an edge $e$. Theproblems are: 1.) The edge switch problem, namely, is the edge $e$ everswitched by all-switches strategy improvement when it is started from $s$ ongame $G$? 2.) The optimal strategy problem, namely, is the edge $e$ used in thefinal strategy that is found by strategy improvement when it is started from$s$ on game $G$? We show $\mathtt{PSPACE}$-completeness of the edge switchproblem and optimal strategy problem for the following settings: Parity gameswith the discrete strategy improvement algorithm of V\"oge and Jurdzi\'nski;mean-payoff games with the gain-bias algorithm [14,37]; and discounted-payoffgames and simple stochastic games with their standard strategy improvementalgorithms. We also show $\mathtt{PSPACE}$-completeness of an analogous problemto edge switch for the bottom-antipodal algorithm for finding the sink of anAcyclic Unique Sink Orientation on a cube.
关键词：Computer Science - Data Structures;Algorithms;Computer Science - Computational Complexity;Computer Science - Computer Science;Game Theory;Computer Science - Logic in Computer Science