The complexity of mean payoff games

DOI10.1007/BFB0030814MaRDI QIDQ6064008zbMATH OpenOpenAlexFDO

Authors Uri Zwick, Mike Paterson

Publication date 12 December 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bfb0030814

Mathematics Subject Classification ID

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

Recommendations

• The complexity of mean payoff games on graphs
• The complexity of solving stochastic games on graphs
• The complexity of stochastic games
• The complexity of ergodic mean-payoff games
• New algorithms for solving simple stochastic games

Cites work

• A characterization of the minimum cycle mean in a digraph
• A subexponential randomized algorithm for the simple stochastic game problem
• An optimal on-line algorithm for metrical task system
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Cyclical games with prohibitions
• Every Prime Has a Succinct Certificate
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• Positional strategies for mean payoff games
• Stochastic Games
• The complexity of stochastic games
• Tighter Lower Bounds on the Exact Complexity of String Matching

Cited in

(5)

• The complexity of mean payoff games on graphs
• A note on the complexity of determining optimal strategies in games with common payoffs
• Predictive Complexity for Games with Finite Outcome Spaces
• The complexity of stochastic Müller games
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games

This page was built for publication: The complexity of mean payoff games

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