The complexity of stochastic games

DOI10.1016/0890-5401(92)90048-KzbMath0756.90103WikidataQ29040293 ScholiaQ29040293MaRDI QIDQ1187025

Publication date: 28 June 1992

Published in: Information and Computation (Search for Journal in Brave)

Abstract computational complexity for mathematical programming problems (90C60) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15) Markov and semi-Markov decision processes (90C40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Unnamed Item, The complexity of mean payoff games, Parity Games and Propositional Proofs, Model Checking for Safe Navigation Among Humans, Symbolic verification and strategy synthesis for turn-based stochastic games, Convex lattice equation systems, Symbolic control for stochastic systems via finite parity games, Fixpoint Theory -- Upside Down, OPTIMAL STRATEGY IN “GUESS WHO?”: BEYOND BINARY SEARCH, Optimistic and topological value iteration for simple stochastic games, The stochastic arrival problem, On the complexity of computational problems associated with simple stochastic games, Solving mean-payoff games via quasi dominions, Hardness of Continuous Local Search: Query Complexity and Cryptographic Lower Bounds, Unnamed Item, Combinations of Qualitative Winning for Stochastic Parity Games, Stochastic Games, Solving Mean-Payoff Games via Quasi Dominions, A survey of computational complexity results in systems and control, Partial-Observation Stochastic Games, The Complexity of Computing a Bisimilarity Pseudometric on Probabilistic Automata, Simple Stochastic Games with Few Random Vertices Are Easy to Solve, Stochastic Games with Lossy Channels, Stochastic Müller Games are PSPACE-Complete, Deterministic Graphical Games Revisited, Unnamed Item, On Nash Equilibria in Stochastic Positional Games with Average Payoffs, TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES, General cops and robbers games with randomness, A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations, Expected reachability-time games, Polynomial Time Algorithms for Branching Markov Decision Processes and Probabilistic Min(Max) Polynomial Bellman Equations, Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\), Parameter Synthesis for Probabilistic Timed Automata Using Stochastic Game Abstractions, The mu-calculus and Model Checking, Graph Games and Reactive Synthesis, A short certificate of the number of universal optimal strategies for stopping simple stochastic games, The complexity of mean payoff games on graphs, DISCOUNTING AND AVERAGING IN GAMES ACROSS TIME SCALES, Parameter synthesis for probabilistic timed automata using stochastic game abstractions, Quantitative verification and strategy synthesis for stochastic games, Constant Rank Two-Player Games are PPAD-hard, Efficient and Dynamic Algorithms for Alternating Büchi Games and Maximal End-Component Decomposition, Perfect information two-person zero-sum Markov games with imprecise transition probabilities, Strategy improvement for concurrent reachability and turn-based stochastic safety games, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, On canonical forms for zero-sum stochastic mean payoff games, A game-based abstraction-refinement framework for Markov decision processes, Bidding mechanisms in graph games, On Abstraction of Probabilistic Systems, Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information, Solving generic nonarchimedean semidefinite programs using stochastic game algorithms, Robust worst cases for parity games algorithms, Parameterized Algorithms for Parity Games, Determinacy and optimal strategies in infinite-state stochastic reachability games, Value iteration for simple stochastic games: stopping criterion and learning algorithm, Unnamed Item, A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions, Solving subclasses of multi-player stochastic games via linear complementarity problem formulations -- a survey and some new results, Recursive stochastic games with positive rewards, On Nash equilibria and improvement cycles in pure positional strategies for chess-like and backgammon-like \(n\)-person games, A CSP-Based Approach for Solving Parity Game, Solving Simple Stochastic Games, A Simple P-Matrix Linear Complementarity Problem for Discounted Games, A survey of stochastic \(\omega \)-regular games, The complexity of stochastic Müller games, Value Iteration, Orderfield property of mixtures of stochastic games, ARRIVAL: A Zero-Player Graph Game in NP ∩ coNP, On strategy improvement algorithms for simple stochastic games, Unnamed Item, Equilibria, fixed points, and complexity classes, On the complexity of core, kernel, and bargaining set, A superpolynomial lower bound for strategy iteration based on snare memorization, Another sub-exponential algorithm for the simple stochastic game, Constraint Satisfaction Problems over Numeric Domains, On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness, Polynomial-time algorithms for energy games with special weight structures, ARRIVAL: Next Stop in CLS, Reachability Switching Games, Fixpoint theory -- upside down, Concurrent games with tail objectives, Cyclic games and linear programming, Concurrent reachability games, Solving parity games via priority promotion, Automatizability and Simple Stochastic Games, Weighted modal transition systems, A survey of partial-observation stochastic parity games, Approximation schemes for stochastic mean payoff games with perfect information and few random positions, Quantitative fair simulation games, Energy parity games, Reduction of stochastic parity to stochastic mean-payoff games, Planning and acting in partially observable stochastic domains, Metrics for weighted transition systems: axiomatization and complexity, Unnamed Item, Strategy logic, Qualitative reachability in stochastic BPA games, Unnamed Item, Unnamed Item, Unnamed Item, A policy iteration algorithm for zero-sum stochastic games with mean payoff, A delayed promotion policy for parity games, Unnamed Item, On Solving Mean Payoff Games Using Pivoting Algorithms, Recursive Markov Decision Processes and Recursive Stochastic Games, Verifying minimum stable circuit values, Unnamed Item, Qualitative Analysis of VASS-Induced MDPs, Computational complexity, Newton polytopes, and Schubert polynomials, Deciding probabilistic bisimilarity distance one for probabilistic automata, Verifying Team Formation Protocols with Probabilistic Model Checking, Model-Free Reinforcement Learning for Stochastic Parity Games, PLAYER CO-MODELLING IN A STRATEGY BOARD GAME: DISCOVERING HOW TO PLAY FAST, A Survey of Bidding Games on Graphs (Invited Paper), Unique End of Potential Line, Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time, Decision Problems for Nash Equilibria in Stochastic Games, Stochastic Games for Verification of Probabilistic Timed Automata, A non-iterative algorithm for generalized pig games, New Algorithms for Solving Zero-Sum Stochastic Games, The complexity of multi-mean-payoff and multi-energy games, Qualitative analysis of concurrent mean-payoff games, Comparison of algorithms for simple stochastic games, On the undecidability of probabilistic planning and related stochastic optimization problems, Contingent planning under uncertainty via stochastic satisfiability, Combinatorial structure and randomized subexponential algorithms for infinite games, Verification of multiplayer stochastic games via abstract dependency graphs

Cites Work