Document Open Access Logo

Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs

Authors Alexander Weinert, Martin Zimmermann

PDF

File

Thumbnail PDF
PDF
LIPIcs.CSL.2016.31.pdf
  • Filesize: 0.49 MB
  • 17 pages

Document Identifiers

Subject Classification

Keywords
  • Parity Games with Costs
  • Optimal Strategies
  • Memory Requirements
  • Tradeoffs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

The winning condition of a parity game with costs requires an arbitrary, but fixed bound on the distance between occurrences of odd colors and the next occurrence of a larger even one. Such games quantitatively extend parity games while retaining most of their attractive properties, i.e, determining the winner is in NP and co-NP and one player has positional winning strategies.

We show that the characteristics of parity games with costs are vastly different when asking for strategies realizing the minimal such bound: the solution problem becomes PSPACE-complete and exponential memory is both necessary in general and always sufficient. Thus, playing parity games with costs optimally is harder than just winning them. Moreover, we show that the tradeoff between the memory size and the realized bound is gradual in general.

Cite As Get BibTex

Alexander Weinert and Martin Zimmermann. Easy to Win, Hard to Master: Optimal Strategies in Parity Games with Costs. In 25th EACSL Annual Conference on Computer Science Logic (CSL 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 62, pp. 31:1-31:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CSL.2016.31

Author Details

Alexander Weinert
Martin Zimmermann

References

  1. Rajeev Alur, Kousha Etessami, Salvatore La Torre, and Doron Peled. Parametric temporal logic for "model measuring". ACM Trans. Comput. Log., 2(3):388-407, 2001. Google Scholar
  2. Benjamin Aminof and Sasha Rubin. First cycle games. In Fabio Mogavero, Aniello Murano, and Moshe Y. Vardi, editors, SR 2014, volume 146 of EPTCS, pages 83-90, 2014. Google Scholar
  3. Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey, and Jirí Srba. Infinite runs in weighted timed automata with energy constraints. In Franck Cassez and Claude Jard, editors, FORMATS 2008, volume 5215 of LNCS, pages 33-47. Springer, 2008. Google Scholar
  4. Véronique Bruyère, Quentin Hautem, and Mickael Randour. Window parity games: an alternative approach toward parity games with time bounds. arXiv, 1606.01831, 2016. Google Scholar
  5. Arindam Chakrabarti, Luca de Alfaro, Thomas A. Henzinger, and Mariëlle Stoelinga. Resource interfaces. In Rajeev Alur and Insup Lee, editors, EMSOFT 2003, volume 2855 of LNCS, pages 117-133. Springer, 2003. Google Scholar
  6. Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114-133, 1981. Google Scholar
  7. Krishnendu Chatterjee, Luca de Alfaro, and Thomas A. Henzinger. Trading memory for randomness. In Gethin Norman and William Sanders, editors, QEST 2004, pages 206-217. IEEE, 2004. Google Scholar
  8. Krishnendu Chatterjee and Nathanaël Fijalkow. Infinite-state games with finitary conditions. arXiv, 1301.2661, 2013. Google Scholar
  9. Krishnendu Chatterjee, Thomas A. Henzinger, and Florian Horn. Finitary winning in ω-regular games. ACM Trans. Comput. Log., 11(1), 2009. URL: http://dx.doi.org/10.1145/1614431.1614432.
  10. Krishnendu Chatterjee, Thomas A. Henzinger, and Vinayak S. Prabhu. Trading infinite memory for uniform randomness in timed games. In Magnus Egerstedt and Bud Mishra, editors, HSCC 2008, volume 4981 of LNCS, pages 87-100. Springer, 2008. Google Scholar
  11. Andrzej Ehrenfeucht and Jan Mycielski. Positional strategies for mean payoff games. Int. J. Game Theory, 8:109-113, 1979. Google Scholar
  12. E. Allen Emerson and Charanjit S. Jutla. Tree automata, mu-calculus and determinacy (extended abstract). In FOCS 1991, pages 368-377. IEEE, 1991. Google Scholar
  13. Peter Faymonville and Martin Zimmermann. Parametric linear dynamic logic. In Adriano Peron and Carla Piazza, editors, GandALF 2014, volume 161 of EPTCS, pages 60-73, 2014. Google Scholar
  14. Nathanaël Fijalkow, Florian Horn, Denis Kuperberg, and Michal Skrzypczak. Trading bounds for memory in games with counters. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, ICALP 2015, Part II, volume 9135 of LNCS, pages 197-208. Springer, 2015. Google Scholar
  15. Nathanaël Fijalkow and Martin Zimmermann. Parity and Streett Games with Costs. LMCS, 10(2), 2014. Google Scholar
  16. Erich Grädel, Wolfgang Thomas, and Thomas Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research, volume 2500 of LNCS. Springer, 2002. Google Scholar
  17. Florian Horn, Wolfgang Thomas, Nico Wallmeier, and Martin Zimmermann. Optimal strategy synthesis for request-response games. RAIRO - Theor. Inf. and Applic., 49(3):179-203, 2015. Google Scholar
  18. Marcin Jurdziński. Deciding the winner in parity games is in UP ∩ co-UP. Inf. Process. Lett., 68(3):119-124, 1998. URL: http://dx.doi.org/10.1016/S0020-0190(98)00150-1.
  19. Orna Kupferman, Nir Piterman, and Moshe Y. Vardi. From liveness to promptness. Form. Met. in Sys. Des., 34(2):83-103, 2009. URL: http://dx.doi.org/10.1007/s10703-009-0067-z.
  20. Martin Lang. Resource reachability games on pushdown graphs. In Anca Muscholl, editor, FOSSACS 14, volume 8412 of LNCS, pages 195-209. Springer, 2014. Google Scholar
  21. Fabio Mogavero, Aniello Murano, and Loredana Sorrentino. On promptness in parity games. Fundam. Inform., 139(3):277-305, 2015. Google Scholar
  22. Andrzej Mostowski. Games with forbidden positions. Technical Report 78, University of Gdańsk, 1991. Google Scholar
  23. Amir Pnueli and Roni Rosner. On the synthesis of an asynchronous reactive module. In Giorgio Ausiello, Mariangiola Dezani-Ciancaglini, and Simona Ronchi Della Rocca, editors, ICALP 1989, volume 372 of LNCS, pages 652-671. Springer, 1989. URL: http://dx.doi.org/10.1007/BFb0035790.
  24. Mickael Randour. Synthesis in Multi-Criteria Quantitative Games. PhD thesis, University of Mons, 2014. Google Scholar
  25. Alexander Weinert and Martin Zimmermann. Easy to win, hard to master: Optimal strategies in parity games with costs. arXiv, 1604.05543, 2016. Google Scholar
  26. Ernst Zermelo. Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. In Proc. Fifth Congress of Mathematicians, Vol. 2, pages 501-504. Cambridge Press, 1913. Google Scholar
  27. Martin Zimmermann. Time-optimal winning strategies for poset games. In Sebastian Maneth, editor, CIAA 2009, volume 5642 of LNCS, pages 217-226. Springer, 2009. Google Scholar
  28. Martin Zimmermann. Optimal Bounds in Parametric LTL Games. Theoret. Comput. Sci., 493(0):30-45, 2013. Google Scholar
  29. Martin Zimmermann. Parameterized linear temporal logics meet costs: Still not costlier than LTL. In Javier Esparza and Enrico Tronci, editors, GandALF 2015, volume 193 of EPTCS, pages 144-157, 2015. Google Scholar
  30. Uri Zwick and Mike Paterson. The complexity of mean payoff games. In Ding-Zhu Du and Ming Li, editors, COCOON 1995, volume 959 of LNCS, pages 1-10. Springer, 1995. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact