Reachability switching games

MaRDI QIDQ4989405zbMATH OpenFDO

Authors John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani

Publication date 25 May 2021

Full work available at URL https://arxiv.org/abs/1709.08991, https://lmcs.episciences.org/7392

zbMATH Keywords

deterministic random walksmodel checkingreachabilitysimple stochastic gameswitching systems

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Other nonclassical models of computation (68Q09) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60) Applications of game theory (91A80)

Recommendations

• Reachability Switching Games
• On the complexity of counter reachability games
• On the Complexity of Counter Reachability Games
• Reachability in succinct one-counter games
• The complexity of stochastic games

Cites work

• A simplified NP-complete satisfiability problem
• Alternation
• An algorithmic study of switch graphs
• Deterministic random walks on regular trees
• Deterministic random walks on the integers
• Deterministic random walks on the two-dimensional grid
• Did the train reach its destination: the complexity of finding a witness
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• scientific article; zbMATH DE number 17815 (Why is no real title available?)
• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• Quasirandom load balancing
• Reachability Switching Games
• Rotor walks and Markov chains
• Simulating a Random Walk with Constant Error
• SWITCHING GRAPHS
• The Complexity of Markov Decision Processes
• The complexity of stochastic games
• The Simple Reachability Problem in Switch Graphs
• Unique end of potential line

Cited in

(9)

• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• ARRIVAL: next stop in CLS
• Reachability Switching Games
• Did the train reach its destination: the complexity of finding a witness
• Trains, games, and complexity: 0/1/2-player motion planning through input/output gadgets
• The stochastic arrival problem
• The recursive arrival problem
• A quasi-polynomial time algorithm for multi-arrival on tree-like multigraphs
• ARRIVAL: recursive framework \& _1-contraction

Describes a project that uses

Uses Software

• PRISM

This page was built for publication: Reachability switching games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4989405)