Stochastic limit-average games are in EXPTIME

DOI10.1007/S00182-007-0110-5zbMATH Open1154.91004arXiv0805.2622OpenAlexW2018658986MaRDI QIDQ933752FDOQ933752

Authors: Krishnendu Chatterjee, Rupak Majumdar, Thomas A. Henzinger 

Publication date: 25 July 2008

Published in: International Journal of Game Theory (Search for Journal in Brave)

Abstract: The value of a finite-state two-player zero-sum stochastic game with limit-average payoff can be approximated to within $epsilon$ in time exponential in a polynomial in the size of the game times polynomial in logarithmic in $frac1epsilon$, for all $epsilon>0$.

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

Recommendations

• A Survey of Stochastic Games with Limsup and Liminf Objectives
• The complexity of solving stochastic games on graphs
• Approximation schemes for stochastic mean payoff games with perfect information and few random positions
• Another sub-exponential algorithm for the simple stochastic game
• Exact algorithms for solving stochastic games

zbMATH Keywords

computational complexitystochastic gameslimit-average payoff

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15)

Cites Work

• The complexity of mean payoff games on graphs
• Title not available (Why is that?)
• Stochastic Games
• Algorithms for stochastic games ? A survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• Stochastic games
• The Asymptotic Theory of Stochastic Games
• The Big Match
• Title not available (Why is that?)
• Algorithms in real algebraic geometry
• Stochastic Games with Perfect Information and Time Average Payoff
• An orderfield property for stochastic games when one player controls transition probabilities
• On Nonterminating Stochastic Games
• Continuity of the value of competitive Markov decision processes
• New results on quantifier elimination over real closed fields and applications to constraint databases
• Number of quantifiers is better than number of tape cells
• On the menbership problem for functional and multivalued dependencies in relational databases

Cited In (18)

• A survey of stochastic \(\omega \)-regular games
• Approximating the value of a concurrent reachability game in the polynomial time hierarchy
• Denumerable state stochastic games with limiting average payoff
• Definable zero-sum stochastic games
• A potential reduction algorithm for two-person zero-sum mean payoff stochastic games
• Acceptable strategy profiles in stochastic games
• A formula for the value of a stochastic game
• Graph Games and Reactive Synthesis
• Games through Nested Fixpoints
• Computing uniformly optimal strategies in two-player stochastic games
• Ergodic Mean-Payoff Games for the Analysis of Attacks in Crypto-Currencies
• Zero-sum stochastic games over the field of real algebraic numbers
• Stochastic games
• New algorithms for solving zero-sum stochastic games
• A Survey of Stochastic Games with Limsup and Liminf Objectives
• Qualitative analysis of concurrent mean-payoff games
• Defense and security planning under resource uncertainty and multi‐period commitments
• Value Iteration

This page was built for publication: Stochastic limit-average games are in EXPTIME

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