A potential reduction algorithm for two-person zero-sum mean payoff stochastic games

DOI10.1007/s13235-016-0199-xzbMath1390.91037arXiv1508.03455OpenAlexW2245890606MaRDI QIDQ2636482

Endre Boros, Kazuhisa Makino, Vladimir A. Gurvich, Khaled M. Elbassioni

Publication date: 5 June 2018

Published in: Dynamic Games and Applications (Search for Journal in Brave)

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

zbMATH Keywords

mean payoffcomputational game theoryundiscounted stochastic gamespotential transformationlimiting average payofflocal reward

Mathematics Subject Classification ID

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

Related Items (2)

Metric and ultrametric inequalities for directed graphs ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On canonical forms for zero-sum stochastic mean payoff games
• Stochastic limit-average games are in EXPTIME
• Solving systems of polynomial inequalities in subexponential time
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
• The complexity of mean payoff games on graphs
• A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions
• On discounted approximations of undiscounted stochastic games and Markov decision processes with limited randomness
• A Potential Reduction Algorithm for Ergodic Two-Person Zero-Sum Limiting Average Payoff Stochastic Games
• Maximum-Minimum Sätze über Graphen
• A Pumping Algorithm for Ergodic Stochastic Mean Payoff Games with Perfect Information
• The Complexity of Solving Stochastic Games on Graphs
• Successive Approximation Methods in Undiscounted Stochastic Games
• Algorithms for stochastic games ? A survey
• On the combinatorial and algebraic complexity of quantifier elimination
• The Complexity of Ergodic Mean-payoff Games
• Exact algorithms for solving stochastic games
• On Nonterminating Stochastic Games
• The Big Match
• Boundary Theory for Recurrent Markov Chains
• Stochastic Games
• Stochastic games

This page was built for publication: A potential reduction algorithm for two-person zero-sum mean payoff stochastic games