Approximation schemes for stochastic mean payoff games with perfect information and few random positions

DOI10.1007/s00453-017-0372-7zbMath1417.91070OpenAlexW2754286068WikidataQ59527899 ScholiaQ59527899MaRDI QIDQ1755732

Endre Boros, Bodo Manthey, Kazuhisa Makino, Mahmoud Fouz, Vladimir A. Gurvich, Khaled M. Elbassioni

Publication date: 11 January 2019

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://research.utwente.nl/en/publications/approximation-schemes-for-stochastic-mean-payoff-games-with-perfect-information-and-few-random-positions(437d93e1-2938-4039-bb15-270b5c154293).html

zbMATH Keywords

Nash equilibriumapproximation schemesapproximation algorithmsstochastic mean payoff games

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Another sub-exponential algorithm for the simple stochastic game
• Cyclical games with prohibitions
• Cyclic games and linear programming
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Extensions of two person zero sum games
• A characterization of the minimum cycle mean in a digraph
• The complexity of mean payoff games on graphs
• Markov chain sensitivity measured by mean first passage times
• A convex programming-based algorithm for mean payoff stochastic games with perfect information
• A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
• A note on the approximation of mean-payoff games
• Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems
• Non-cooperative games
• Mean Cost Cyclical Games
• Solving Simple Stochastic Games with Few Coin Toss Positions
• Stochastic Mean Payoff Games: Smoothed Analysis and Approximation Schemes
• From Parity and Payoff Games to Linear Programming
• Settling the complexity of computing two-player Nash equilibria
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
• The Complexity of Solving Stochastic Games on Graphs
• Deciding parity games in quasipolynomial time
• The Complexity of Ergodic Mean-payoff Games
• Simple Stochastic Games with Few Random Vertices Are Easy to Solve
• Stochastic Games with Perfect Information and Time Average Payoff
• Equilibrium points in n -person games