Strategy recovery for stochastic mean payoff games

DOI10.1016/J.TCS.2017.02.015MaRDI QIDQ528499zbMATH OpenOpenAlexFDO

Authors Marcello Mamino

Publication date 12 May 2017

Published in Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitystochastic mean payoff games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Abstract: We prove that to find optimal positional strategies for stochastic mean payoff games when the value of every state of the game is known, in general, is as hard as solving such games tout court. This answers a question posed by Daniel Andersson and Peter Bro Miltersen.

Recommendations

• The complexity of solving stochastic games on graphs
• Blackwell optimal strategies in priority mean-payoff games
• Blackwell-optimal strategies in priority mean-payoff games
• The complexity of mean payoff games on graphs
• Determining the optimal strategies for zero-sum average stochastic positional games

Cites work

• scientific article; zbMATH DE number 3128733 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• A pumping algorithm for ergodic stochastic mean payoff games with perfect information
• Markov Chains
• Stochastic Games with Perfect Information and Time Average Payoff
• The complexity of ergodic mean-payoff games
• The complexity of solving stochastic games on graphs

This page was built for publication: Strategy recovery for stochastic mean payoff games

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