REACHABILITY SWITCHING GAMES

Fearnley, John, Gairing, Martin ORCID: 0000-0002-0569-7113, Mnich, Matthias and Savani, Rahul ORCID: 0000-0003-1262-7831 (2021) REACHABILITY SWITCHING GAMES. In: ICALP 2018.

Text note.pdf - Author Accepted Manuscript Download (534kB)

Abstract

<jats:p>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.</jats:p>

Item Type:	Conference Item (Unspecified)
Uncontrolled Keywords:	Deterministic Random Walks, Model Checking, Reachability, Simple Stochastic Game, Switching Systems
Depositing User:	Symplectic Admin
Date Deposited:	22 May 2018 09:36
Last Modified:	05 Apr 2025 07:54
DOI:	10.23638/LMCS-17(2:10)2021
Related Websites:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3020805