The complexity of stochastic games
From MaRDI portal
Publication:1187025
DOI10.1016/0890-5401(92)90048-KzbMath0756.90103DBLPjournals/iandc/Condon92WikidataQ29040293 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 (only showing first 100 items - show all)
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
This page was built for publication: The complexity of stochastic games
