The complexity of solving reachability games using value and strategy iteration

DOI10.1007/s00224-013-9524-6zbMath1319.68149arXiv1007.1812MaRDI QIDQ2254503

Peter Bro Miltersen, Rasmus Ibsen-Jensen, Kristoffer Arnsfelt Hansen

Publication date: 5 February 2015

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.1812

zbMATH Keywords

analysis of algorithms; value iteration; strategy iteration; concurrent reachability games

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

91A05: 2-person games

91A80: Applications of game theory

68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Related Items

The complexity of solving reachability games using value and strategy iteration, Qualitative analysis of concurrent mean-payoff games, Patience of matrix games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of solving reachability games using value and strategy iteration
• Concurrent reachability games
• Algorithms for discounted stochastic games
• New Results on Simple Stochastic Games
• Existence of p-Equilibrium and Optimal Stationary Strategies in Stochastic Games
• Computer Science Logic
• Exact algorithms for solving stochastic games
• On Nonterminating Stochastic Games
• Discounted and positive stochastic games
• Stochastic Games
• Recursive Concurrent Stochastic Games
• Stochastic games