iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10703-010-0105-x
Faster algorithms for mean-payoff games | Formal Methods in System Design Skip to main content

Advertisement

Springer Nature Link
Log in

Faster algorithms for mean-payoff games

  • Published:
Formal Methods in System Design Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Andersson D, Vorobyov S (2006) Fast algorithms for monotonic discounted linear programs with two variables per inequality. Preprint NI06019-LAA, Isaac Newton Institute for Mathematical Sciences, Cambridge, UK

  2. Bjorklund H, Vorobyov S (2007) A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games. Discrete Appl Math 155:210–229

    Article  MathSciNet  Google Scholar 

  3. Bouyer P, Fahrenberg U, Larsen KG, Markey N, Srba J (2008) Infinite runs in weighted timed automata with energy constraints. In: Proc of FORMATS: formal modeling and analysis of timed systems. LNCS, vol 5215. Springer, Berlin, pp 33–47

    Chapter  Google Scholar 

  4. Chakrabarti A, de Alfaro L, Henzinger TA, Stoelinga M (2003) Resource interfaces. In: Proc of EMSOFT: embedded software. LNCS, vol 2855. Springer, Berlin, pp 117–133

    Google Scholar 

  5. Chaloupka J, Brim L (2009) Faster algorithm for mean-payoff games. In: Proc of the 5th docoral workshop on mathematical and engineering methods in computer science (MEMICS ’09). Novpress, pp 45–53

  6. Condon A (1993) On algorithms for simple stochastic games. In: Advances in computational complexity theory. DIMACS series in discrete mathematics and theoretical computer science, vol 13. American Mathematical Society, Providence, pp 51–73

    Google Scholar 

  7. Dhingra V, Gaubert S (2006) How to solve large scale deterministic games with mean payoff by policy iteration. In: Proc. of Valuetools: International conference on performance evaluation methodologies and tools. ACM, New York

    Google Scholar 

  8. Doyen L, Gentilini R, Raskin J-F (2009) Faster pseudopolynomial algorithms for meanpayoff games Technical Report 2009.120. Universite Libre de Bruxelles (ULB), Bruxelles, Belgium

  9. Ehrenfeucht A, Mycielski J (1979) Positional strategies for mean-payoff games. Int J Game Theory 8:109–113

    Article  MATH  MathSciNet  Google Scholar 

  10. Emerson EA, Jutla C, Sistal AP (1993) On model checking for fragments of the μ-calculus. In: Proc of CAV: computer aided verification. LNCS, vol 697. Springer, Berlin, pp 385–396

    Google Scholar 

  11. Gurevich Y, Harrington L (1982) Trees, automata, and games. In: Proc of STOC: symposium on theory of computing. ACM, New York, pp 60–65

    Google Scholar 

  12. Gurvich VA, Karzanov AV, Kachiyan LG (1988) Cyclic games and an algorithm to find minmax cycle means in directed graphs. USSR Comput Math Math Phys 5(28):85–91

    Article  Google Scholar 

  13. Jurdzinski M (1998) Deciding the winner in parity games is in UP ∩ coUP. Inf Process Lett 68(3): 119–124

    Article  MathSciNet  Google Scholar 

  14. Jurdzinski M (2000) Small progress measures for solving parity games. In: Proceedings of STACS: theoretical aspects of computer science. LNCS, vol 1770. Springer, Berlin, pp 290–301

    Google Scholar 

  15. Karzanov AV, Lebedev VN (1993) Cyclical games with prohibitions. Math Program 60:277–293

    Article  MATH  MathSciNet  Google Scholar 

  16. Kozen D (1983) Results on the propositional mu-calculus. Theor Comput Sci 27:333–354

    Article  MATH  MathSciNet  Google Scholar 

  17. Lifshits Y, Pavlov D (2007) Potential theory for mean payoff games. J Math Sci 145(3):4967–4974

    Article  MathSciNet  Google Scholar 

  18. Manna Z, Pnueli A (1992) The temporal logic of reactive and concurrent programs. Springer, Berlin

    Google Scholar 

  19. Papadimitriou CM (1994) Computational complexity. Addison-Wesley, Reading

    MATH  Google Scholar 

  20. Pisaruk N (1999) Mean cost cyclical games. Math Oper Res 4(24):817–828

    Article  MathSciNet  Google Scholar 

  21. Schewe S (2009) From parity and payoff games to linear programming. In: Proceedings of MFCS: mathematical foundations of computer science. LNCS, vol 5734. Springer, Berlin, pp 675–686

    Google Scholar 

  22. Walukiewicz I (1996) Pushdown processes: Games and model checking. In: Proceedings of CAV: computer aided verification. LNCS, vol 1102. Springer, Berlin, pp 62–74

    Google Scholar 

  23. Zwick U, Paterson M (1996) The complexity of mean payoff games on graphs. Theor Comput Sci 158:343–359

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Informatics, Masaryk University, Brno, Czech Republic

    L. Brim & J. Chaloupka

  2. Computer Science Department, Université Libre de Bruxelles (U.L.B.), Brussels, Belgium

    L. Doyen, R. Gentilini & J. F. Raskin

  3. Department of Mathematics and Informatics, University of Perugia, Perugia, Italy

    R. Gentilini

  4. LSV, ENS Cachan & CNRS, Cachan, France

    L. Doyen

Authors
  1. L. Brim
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. J. Chaloupka
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. L. Doyen
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. R. Gentilini
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. J. F. Raskin
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to R. Gentilini.

Additional information

This work is an extended and revised version of [5], appeared in the 5-th Doctoral Workshop on Mathematics and Engineering Methods in Computer Science (MEMICS’09), and [8], appeared in the 3-rd Workshop of the ESF Networking Programme on Games for Design and Verification (GAMES’09).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Brim, L., Chaloupka, J., Doyen, L. et al. Faster algorithms for mean-payoff games. Form Methods Syst Des 38, 97–118 (2011). https://doi.org/10.1007/s10703-010-0105-x

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10703-010-0105-x

Keywords

Search

Navigation