Faster algorithms for mean-payoff games

Investor logo

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

BRIM Luboš CHALOUPKA Jakub DOYEN Laurent GENTILINI Raffaella RASKIN Jean-François

Year of publication 2011
Type Article in Periodical
Magazine / Source Formal Methods in System Design
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/s10703-010-0105-x
Field Informatics
Keywords Mean payoff objectives; Algorithms and complexity upper bounds
Description In this paper, we study algorithmic problems for quantitative models that are motivated by the applications in modeling embedded systems. We consider two-player games played on a weighted graph with mean-payoff objective and with energy constraints. We present a new pseudopolynomial algorithm for solving such games, improving the best known worst-case complexity for pseudopolynomial mean-payoff algorithms. Our algorithm can also be combined with the procedure by Andersson and Vorobyov to obtain a randomized algorithm with currently the best expected time complexity. The proposed solution relies on a simple fixpoint iteration to solve the log-space equivalent problem of deciding the winner of energy games. Our results imply also that energy games and mean-payoff games can be reduced to safety games in pseudopolynomial time.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.