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

DOI10.1007/s00453-016-0123-1zbMath1364.68384arXiv1503.04426OpenAlexW1592208609MaRDI QIDQ524362

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

zbMATH Keywords

mean payoff gamesenergy gamesoptimal strategy synthesispseudo-polynomial timesmall energy-progress measuresvalue problem

Mathematics Subject Classification ID

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

Related Items (9)

The Theory of Universal Graphs for Infinite Duration Games ⋮ Protocol scheduling ⋮ Instantaneous reaction-time in dynamic consistency checking of conditional simple temporal networks ⋮ Solving mean-payoff games via quasi dominions ⋮ Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games ⋮ Solving Mean-Payoff Games via Quasi Dominions ⋮ Unnamed Item ⋮ Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games ⋮ The GKK algorithm is the fastest over simple mean-payoff games

Cites Work

• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Faster algorithms for mean-payoff games
• 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
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• Infinite Runs in Weighted Timed Automata with Energy Constraints

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