Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games

DOI10.4230/LIPICS.MFCS.2020.34OpenAlexW3043364318MaRDI QIDQ5089201FDOQ5089201

Nathanaël Fijalkow, Paweł Gawrychowski, Pierre Ohlmann

Publication date: 18 July 2022

Full work available at URL: https://hal-cnrs.archives-ouvertes.fr/hal-03800510

Recommendations

• The complexity of mean payoff games on graphs
• The complexity of solving reachability games using value and strategy iteration
• The complexity of solving reachability games using value and strategy iteration
• On the Complexity of Value Iteration
• The complexity of mean payoff games
• The complexity of solving stochastic games on graphs
• Iterated regret minimization in game graphs
• Optimistic and topological value iteration for simple stochastic games
• Values of games with probabilistic graphs
• The theory of universal graphs for games: past and future

zbMATH Keywords

value iterationmean payoff gamesuniversal graphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• The complexity of mean payoff games on graphs
• Mathematical problems for the next century
• A subexponential bound for linear programming
• An application of simultaneous diophantine approximation in combinatorial optimization
• Positional strategies for mean payoff games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Implicat Representation of Graphs
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Faster algorithms for mean-payoff games
• Linear programming, the simplex algorithm and simple polytopes
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• Title not available (Why is that?)
• Optimal Distance Labeling Schemes for Trees
• Combinatorial Simplex Algorithms Can Solve Mean Payoff Games
• Deciding parity games in quasipolynomial time
• Universal graphs and good for games automata: new tools for infinite duration games
• Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time
• A modal μ perspective on solving parity games in quasi-polynomial time
• Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (4)

• The Theory of Universal Graphs for Infinite Duration Games
• New algorithms for combinations of objectives using separating automata
• The complexity of solving reachability games using value and strategy iteration
• The GKK algorithm is the fastest over simple mean-payoff games

This page was built for publication: Value Iteration Using Universal Graphs and 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 Q5089201)