The complexity of mean payoff games

DOI10.1007/bfb0030814zbMath1527.68091OpenAlexW1494664245MaRDI QIDQ6064008

Mike S. Paterson, Uri Zwick

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) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15) Algorithmic game theory and complexity (91A68)

Cites Work

• Unnamed Item
• Cyclical games with prohibitions
• Positional strategies for mean payoff games
• The complexity of stochastic games
• A characterization of the minimum cycle mean in a digraph
• A subexponential randomized algorithm for the simple stochastic game problem
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Every Prime Has a Succinct Certificate
• An optimal on-line algorithm for metrical task system
• Tighter Lower Bounds on the Exact Complexity of String Matching
• Stochastic Games

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