John Fearnley ; Martin Gairing ; Matthias Mnich ; Rahul Savani - Reachability Switching Games

lmcs:5425 - Logical Methods in Computer Science, April 22, 2021, Volume 17, Issue 2 - https://doi.org/10.23638/LMCS-17(2:10)2021
Reachability Switching GamesArticle

Authors: John Fearnley ; Martin Gairing ; Matthias Mnich ; Rahul Savani

    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 $\cap$ 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.


    Volume: Volume 17, Issue 2
    Published on: April 22, 2021
    Accepted on: March 25, 2021
    Submitted on: May 3, 2019
    Keywords: Computer Science - Formal Languages and Automata Theory,Computer Science - Computer Science and Game Theory,Computer Science - Logic in Computer Science
    Funding:
      Source : OpenAIRE Graph
    • Algorithms beyond the Worst Case; Funder: European Commission; Code: 306465
    • Solving Parity Games in Theory and Practice; Funder: UK Research and Innovation; Code: EP/P020909/1

    Classifications

    1 Document citing this article

    Consultation statistics

    This page has been seen 1672 times.
    This article's PDF has been downloaded 341 times.