Stochastic limit-average games are in EXPTIME

DOI10.1007/S00182-007-0110-5MaRDI QIDQ933752zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

computational complexitystochastic gameslimit-average payoff

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15)

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$.

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

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 2013849 (Why is no real title available?)
• scientific article; zbMATH DE number 3068536 (Why is no real title available?)
• Algorithms for stochastic games ? A survey
• Algorithms in real algebraic geometry
• An orderfield property for stochastic games when one player controls transition probabilities
• 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 Nonterminating Stochastic Games
• On the menbership problem for functional and multivalued dependencies in relational databases
• Stochastic Games
• Stochastic Games with Perfect Information and Time Average Payoff
• Stochastic games
• The Asymptotic Theory of Stochastic Games
• The Big Match
• The complexity of mean payoff games on graphs

Cited in

(18)

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

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)