Strategy recovery for stochastic mean payoff games

DOI10.1016/J.TCS.2017.02.015zbMATH Open1371.91013arXiv1506.04641OpenAlexW2231633468MaRDI QIDQ528499FDOQ528499

Marcello Mamino

Publication date: 12 May 2017

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

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.

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

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

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)

Cites Work

• Markov Chains
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
• The complexity of solving stochastic games on graphs
• Stochastic Games with Perfect Information and Time Average Payoff
• The Complexity of Ergodic Mean-payoff Games

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)