Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games

DOI10.1007/S00236-016-0276-ZzbMATH Open1362.68203OpenAlexW2364159064MaRDI QIDQ520343FDOQ520343

Authors Thomas Brihaye, G. Geeraerts, Axel Haddad, Benjamin Monmege

Publication date 3 April 2017

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00236-016-0276-z

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Games involving graphs (91A43) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• To reach or not to reach? Efficient algorithms for total-payoff games
• Faster algorithms for mean-payoff games
• 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
• The complexity of mean payoff games on graphs

Cites work

• scientific article; zbMATH DE number 700091 (Why is no real title available?)
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• Adding negative prices to priced timed games
• Automatic verification of competitive stochastic systems
• Borel determinacy
• Depth-First Search and Linear Graph Algorithms
• Faster algorithms for mean-payoff games
• Games through Nested Fixpoints
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Mathematical Foundations of Computer Science 2004
• Multiplayer cost games with simple Nash equilibria
• Nash equilibria in concurrent priced games
• Negative Dynamic Programming
• On short paths interdiction problems: Total and node-wise limited interdiction
• On the synthesis of strategies in infinite games
• Positional strategies for mean payoff games
• Quantitative Languages Defined by Functional Automata
• Simple priced timed games are not that simple
• The bad match; a total reward stochastic game
• The complexity of mean payoff games on graphs
• To reach or not to reach? Efficient algorithms for total-payoff games

Cited in

(8)

• Reaching Your Goal Optimally by Playing at Random with No Memory
• Computing branching distances with quantitative games
• Optimal controller synthesis for timed systems
• To reach or not to reach? Efficient algorithms for total-payoff games
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Optimal reachability in divergent weighted timed games
• scientific article; zbMATH DE number 7577581 (Why is no real title available?)
• Symbolic Approximation of Weighted Timed Games

This page was built for publication: Pseudopolynomial iterative algorithm to solve total-payoff games and min-cost reachability games

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