Exact algorithms for solving stochastic games

DOI10.1145/1993636.1993665MaRDI QIDQ5419090zbMATH OpenOpenAlexFDO

Authors Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas

Publication date 5 June 2014

Published in Proceedings of the forty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1993636.1993665

zbMATH Keywords

real algebraic geometrystochastic games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Other game-theoretic models (91A40)

Recommendations

• Algorithms for stochastic games ? A survey
• scientific article; zbMATH DE number 177098
• scientific article; zbMATH DE number 18885
• New algorithms for solving simple stochastic games
• New algorithms for solving zero-sum stochastic games
• scientific article; zbMATH DE number 549853
• The complexity of solving stochastic games on graphs
• A subexponential randomized algorithm for the simple stochastic game problem
• Optimization and dynamical systems algorithms for finding equilibria of stochastic games
• Algorithms for stochastic games with perfect monitoring

Cited in

(33)

• Acceptable strategy profiles in stochastic games
• Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems
• Faster algorithms for extensive-form game solving via improved smoothing functions
• Zero-sum stochastic games over the field of real algebraic numbers
• Qualitative analysis of concurrent mean-payoff games
• Patience of matrix games
• A probabilistic representation of exact games on image-algebras
• A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
• Achieving Unbounded Resolution inFinitePlayer Goore Games Using Stochastic Automata, and Its Applications
• Graph Games and Reactive Synthesis
• scientific article; zbMATH DE number 5292473 (Why is no real title available?)
• The complexity of solving stochastic games on graphs
• scientific article; zbMATH DE number 3956860 (Why is no real title available?)
• scientific article; zbMATH DE number 3968395 (Why is no real title available?)
• Addendum to ‘A stochastic algorithm to compute optimal probabilities in the chaos game’: a new convergence criterion
• Conditionally Optimal Algorithms for Generalized B\"uchi Games
• Effective algorithms for games with prohibitions and their applications
• Shapley-Snow kernels, multiparameter eigenvalue problems, and stochastic games
• New algorithms for solving zero-sum stochastic games
• Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
• Extended Sprague–Grundy theory for locally finite games, and applications to random game-trees
• Towards solving 2-TBSG efficiently
• Stochastic games
• The Complexity of Interior Point Methods for Solving Discounted Turn-Based Stochastic Games
• A polynomial time algorithm for computing extinction probabilities of multitype branching processes
• Rigorous Computer Analysis of the Chow–Robbins Game
• A formula for the value of a stochastic game
• Approximating the existential theory of the reals
• Approximating the existential theory of the reals
• Semidefinite games
• Bounded-memory strategies in partial-information games
• Concurrent stochastic games with stateful-discounted and parity objectives: complexity and algorithms
• Stochastic limit-average games are in EXPTIME

This page was built for publication: Exact algorithms for solving stochastic games

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