2017/09/26 by John Fearnley, Fearnley, John, Martin Gairing +5
Business, Management and Accounting · Decision Sciences · #Auction Theory and Applications #Deterministic Random Walks #Digital Platforms and Economics #Game Theory and Applications #Mathematik #Model Checking #Reachability #Simple Stochastic Game #Switching Systems
paper · doi:10.15480/882.3658
openalex publication_date 2017/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
We study the problem of deciding the winner of reachability switching games for zero-, one-, and two-player variants. Switching games provide a deterministic analogue of stochastic games. We show that the zero-player case is NL-hard, the one-player case is NP-complete, and that the two-player case is PSPACE-hard and in EXPTIME. For the zero-player case, we also show P-hardness for a succinctly-represented model that maintains the upper bound of NP ∩ coNP. For the one- and two-player cases, our results hold in both the natural, explicit model and succinctly-represented model. Our results show that the switching variant of a game is harder in complexity-theoretic terms than the corresponding stochastic version.