Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games

DOI10.1007/S00453-016-0123-1MaRDI QIDQ524362zbMATH OpenOpenAlexFDO

Authors Carlo Comin, Romeo Rizzi

Publication date 2 May 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.04426, https://hal-upec-upem.archives-ouvertes.fr/hal-01577457/file/1503.04426.pdf

zbMATH Keywords

energy gamesmean payoff gamesoptimal strategy synthesispseudo-polynomial timesmall energy-progress measuresvalue problem

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Analysis of algorithms (68W40) Games involving graphs (91A43)

Abstract: In this work we offer an $O(|V{|}^2|E|,W)$ pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor $log(|V|,W)$ the best previously known pseudo-polynomial time upper bound due to Brim,~etal The improvement hinges on a suitable characterization of values, and a description of optimal positional strategies, in terms of reweighted Energy Games and Small Energy-Progress Measures.

Recommendations

• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• Mathematical Foundations of Computer Science 2004
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
• An Improved Bound for Approximate Equilibria
• An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games
• Approximating values of generalized-reachability stochastic games
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games

Cites work

• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Faster algorithms for mean-payoff games
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• Infinite Runs in Weighted Timed Automata with Energy Constraints
• Order statistics in the Farey sequences in sublinear time and counting primitive lattice points in polygons
• Positional strategies for mean payoff games
• The complexity of mean payoff games on graphs

Cited in

(16)

• The GKK algorithm is the fastest over simple mean-payoff games
• Protocol scheduling
• Instantaneous reaction-time in dynamic consistency checking of conditional simple temporal networks
• A note on the approximation of mean-payoff games
• Potential theory for mean payoff games
• The Theory of Universal Graphs for Infinite Duration Games
• Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games
• Faster algorithms for mean-payoff parity games
• A pseudo-quasi-polynomial algorithm for mean-payoff parity games
• Solving mean-payoff games via quasi dominions
• Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games
• The Value 1 Problem Under Finite-memory Strategies for Concurrent Mean-payoff Games
• Solving mean-payoff games via quasi dominions
• Fair quantitative games
• Fast algorithms for energy games in special cases
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

This page was built for publication: Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games

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