Document Open Access Logo

On the Complexity of Heterogeneous Multidimensional Games

Authors Veronique Bruyere, Quentin Hautem, Jean-Francois Raskin

PDF
Thumbnail PDF

File

LIPIcs.CONCUR.2016.11.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Veronique Bruyere
Quentin Hautem
Jean-Francois Raskin

Cite As Get BibTex

Veronique Bruyere, Quentin Hautem, and Jean-Francois Raskin. On the Complexity of Heterogeneous Multidimensional Games. In 27th International Conference on Concurrency Theory (CONCUR 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 59, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CONCUR.2016.11

Abstract

We study two-player zero-sum turn-based games played on multidimensional weighted graphs with heterogeneous quantitative objectives. Our objectives are defined starting from the measures Inf, Sup, LimInf, and LimSup of the weights seen along the play, as well as on the window mean-payoff (WMP) measure recently introduced in [Krishnendu,Doyen,Randour,Raskin, Inf. Comput., 2015]. Whereas multidimensional games with Boolean combinations of classical mean-payoff objectives are undecidable [Velner, FOSSACS, 2015], we show that CNF/DNF Boolean combinations for heterogeneous measures taken among {WMP, Inf, Sup, LimInf, LimSup} lead to EXPTIME-completeness with exponential memory strategies for both players. We also identify several interesting fragments with better complexities and memory requirements, and show that some of them are solvable in PTIME.

Subject Classification

Keywords
  • wo-player zero-sum games played on graphs
  • quantitative objectives
  • multidimensional heterogeneous objectives

Metrics

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

References

  1. R. Alur, S. La Torre, and P. Madhusudan. Playing games with boxes and diamonds. In CONCUR 2003, volume 2761 of LNCS, pages 127-141. Springer, 2003. Google Scholar
  2. C. Beeri. On the membership problem for functional and multivalued dependencies in relational databases. ACM Trans. Database Syst., 5(3):241-259, 1980. Google Scholar
  3. P. Bouyer, U. Fahrenberg, K. G. Larsen, N. Markey, and J. Srba. Infinite runs in weighted timed automata with energy constraints. In FORMATS 2008, volume 5215 of LNCS, pages 33-47. Springer, 2008. Google Scholar
  4. L. Brim, J. Chaloupka, L. Doyen, R. Gentilini, and J.-F. Raskin. Faster algorithms for mean-payoff games. Formal Methods in System Design, 38(2):97-118, 2011. Google Scholar
  5. K. Chatterjee, L. Doyen, T. A. Henzinger, and J.-F. Raskin. Generalized mean-payoff and energy games. In FSTTCS 2010, volume 8 of LIPIcs, pages 505-516, 2010. Google Scholar
  6. K. Chatterjee, L. Doyen, M. Randour, and J.-F. Raskin. Looking at mean-payoff and total-payoff through windows. Inf. Comput., 242:25-52, 2015. Google Scholar
  7. K. Chatterjee and M. Henzinger. Efficient and dynamic algorithms for alternating büchi games and maximal end-component decomposition. J. ACM, 61(3):15:1-15:40, 2014. Google Scholar
  8. K. Chatterjee, M. Randour, and J.-F. Raskin. Strategy synthesis for multi-dimensional quantitative objectives. Acta Inf., 51(3-4):129-163, 2014. Google Scholar
  9. A. Degorre, L. Doyen, R. Gentilini, J.-F. Raskin, and S. Toruńczyk. Energy and mean-payoff games with imperfect information. In CSL 2010, volume 6247 of LNCS, pages 260-274. Springer, 2010. Google Scholar
  10. S. Dziembowski, M. Jurdzinski, and I. Walukiewicz. How much memory is needed to win infinite games? In LICS 1997, pages 99-110. IEEE Computer Society, 1997. Google Scholar
  11. E. Allen Emerson and C. S. Jutla. Tree automata, mu-calculus and determinacy (extended abstract). In FOCS 1991, pages 368-377. IEEE Computer Society, 1991. Google Scholar
  12. N. Fijalkow and F. Horn. Les jeux d'accessibilité généralisée. Technique et Science Informatiques, 32(9-10):931-949, 2013. Google Scholar
  13. E. Grädel, W. Thomas, and T. Wilke, editors. Automata, Logics, and Infinite Games: A Guide to Current Research, volume 2500 of LNCS. Springer, 2002. Google Scholar
  14. P. Hunter, G. A. Pérez, and J.-F. Raskin. Looking at mean-payoff through foggy windows. In ATVA 2015, volume 9364 of LNCS, pages 429-445. Springer, 2015. Google Scholar
  15. N. Immerman. Number of quantifiers is better than number of tape cells. J. Comput. Syst. Sci., 22(3):384-406, 1981. Google Scholar
  16. M. Jurdzinski, R. Lazic, and S. Schmitz. Fixed-dimensional energy games are in pseudo-polynomial time. In ICALP 2015, volume 9135 of LNCS, pages 260-272. Springer, 2015. Google Scholar
  17. D. A. Martin. Borel determinacy. Annals of Mathematics, 102(2):363-371, 1975. Google Scholar
  18. A. Pnueli and R. Rosner. On the synthesis of a reactive module. In ACM 1989, pages 179-190. ACM Press, 1989. Google Scholar
  19. Y. Velner. Robust multidimensional mean-payoff games are undecidable. In FoSSaCS 2015, volume 9034 of LNCS, pages 312-327. Springer, 2015. Google Scholar
  20. Y. Velner, K. Chatterjee, L. Doyen, T. A. Henzinger, A. M. Rabinovich, and J.-F. Raskin. The complexity of multi-mean-payoff and multi-energy games. Inf. Comput., 241:177-196, 2015. Google Scholar
  21. Y. Velner and A. Rabinovich. Church synthesis problem for noisy input. In FOSSACS 2011, volume 6604 of LNCS, pages 275-289. Springer, 2011. Google Scholar
  22. U. Zwick and M. Paterson. The complexity of mean payoff games on graphs. Theor. Comput. Sci., 158(1&2):343-359, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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