Strategy Complexity of Concurrent Safety Games

Authors Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen



PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.55.pdf
  • Filesize: 0.52 MB
  • 13 pages

Document Identifiers

Author Details

Krishnendu Chatterjee
Kristoffer Arnsfelt Hansen
Rasmus Ibsen-Jensen

Cite AsGet BibTex

Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, and Rasmus Ibsen-Jensen. Strategy Complexity of Concurrent Safety Games. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 55:1-55:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.55

Abstract

We consider two player, zero-sum, finite-state concurrent reachability games, played for an infinite number of rounds, where in every round, each player simultaneously and independently of the other players chooses an action, whereafter the successor state is determined by a probability distribution given by the current state and the chosen actions. Player 1 wins iff a designated goal state is eventually visited. We are interested in the complexity of stationary strategies measured by their patience, which is defined as the inverse of the smallest non-zero probability employed. Our main results are as follows: We show that: (i) the optimal bound on the patience of optimal and epsilon-optimal strategies, for both players is doubly exponential; and (ii) even in games with a single non-absorbing state exponential (in the number of actions) patience is necessary.
Keywords
  • Concurrent games
  • Reachability and safety
  • Patience of strategies

Metrics

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

References

  1. R. Alur, T.A. Henzinger, and O. Kupferman. Alternating-time temporal logic. Journal of the ACM, 49:672-713, 2002. Google Scholar
  2. K. Chatterjee. Concurrent games with tail objectives. Theoretical Computer Science, 388:181-198, 2007. Google Scholar
  3. K. Chatterjee, L. de Alfaro, and T.A. Henzinger. Qualitative concurrent parity games. ACM ToCL, 2011. Google Scholar
  4. Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, and Rasmus Ibsen-Jensen. Strategy complexity of concurrent stochastic games with safety and reachability objectives. CoRR, abs/1506.02434, 2015. URL: http://arxiv.org/abs/1506.02434.
  5. Krishnendu Chatterjee and Rasmus Ibsen-Jensen. The Complexity of Ergodic Mean-payoff Games. In ICALP 2014, pages 122-133, 2014. Google Scholar
  6. L. de Alfaro, T.A. Henzinger, and F.Y.C. Mang. The control of synchronous systems. In CONCUR'00, LNCS 1877, pages 458-473. Springer, 2000. Google Scholar
  7. L. de Alfaro, T.A. Henzinger, and F.Y.C. Mang. The control of synchronous systems, Part II. In CONCUR'01, LNCS 2154, pages 566-580. Springer, 2001. Google Scholar
  8. Luca de Alfaro, Thomas A. Henzinger, and Orna Kupferman. Concurrent reachability games. Theor. Comput. Sci, 386(3):188-217, 2007. Google Scholar
  9. K. Etessami and M. Yannakakis. Recursive concurrent stochastic games. In ICALP'06 (2), LNCS 4052, Springer, pages 324-335, 2006. Google Scholar
  10. H. Everett. Recursive games. In CTG, volume 39 of AMS, pages 47-78, 1957. Google Scholar
  11. J. Filar and K. Vrieze. Competitive Markov Decision Processes. Springer-Verlag, 1997. Google Scholar
  12. K. A. Hansen, R. Ibsen-Jensen, and P. B. Miltersen. The complexity of solving reachability games using value and strategy iteration. In CSR, pages 77-90, 2011. Google Scholar
  13. K. A. Hansen, M. Koucký, and P. B. Miltersen. Winning concurrent reachability games requires doubly-exponential patience. In LICS, pages 332-341, 2009. Google Scholar
  14. C. J. Himmelberg, T. Parthasarathy, T. E. S. Raghavan, and F. S. Van Vleck. Existence of p-equilibrium and optimal stationary strategies in stochastic games. Proc. Amer. Math. Soc., 60:245-251, 1976. Google Scholar
  15. R. Ibsen-Jensen. Strategy complexity of two-player, zero-sum games. PhD thesis, Aarhus University, 2013. Google Scholar
  16. Rasmus Ibsen-Jensen and Peter Bro Miltersen. Solving simple stochastic games with few coin toss positions. In ESA, pages 636-647, 2012. Google Scholar
  17. R.J. Lipton, E. Markakis, and A. Mehta. Playing large games using simple strategies. In EC 03: Electronic Commerce, pages 36-41. ACM Press, 2003. Google Scholar
  18. P. B. Miltersen and T. B. Sørensen. A near-optimal strategy for a heads-up no-limit texas hold'em poker tournament. In AAMAS'07, pages 191-197, 2007. Google Scholar
  19. G. Owen. Game Theory. Academic Press, 1995. Google Scholar
  20. T. Parthasarathy. Discounted and positive stochastic games. Bull. Amer. Math. Soc, 77:134-136, 1971. Google Scholar
  21. A. Pnueli and R. Rosner. On the synthesis of a reactive module. In Proc. of POPL, pages 179-190. ACM Press, 1989. Google Scholar
  22. P. J. Ramadge and W. M. Wonham. Supervisory control of a class of discrete-event processes. SIAM Journal of Control and Optimization, 25(1):206-230, 1987. Google Scholar
  23. L.S. Shapley. Stochastic games. PNAS, 39:1095-1100, 1953. Google Scholar
  24. Eilon Solan and Nicolas Vieille. Computing uniformly optimal strategies in two-player stochastic games. Economic Theory, 42(1):237-253, 2010. Google Scholar
  25. M.Y. Vardi. Automatic verification of probabilistic concurrent finite-state systems. In FOCS'85, pages 327-338. IEEE, 1985. Google Scholar
  26. J. von Neumann and O. Morgenstern. Theory of games and economic behavior. Princeton University Press, 1947. Google Scholar
  27. O.J. Vrieze and F. Thuijsman. On equilibria in repeated games with absorbing states. International Journal of Game Theory, 18(3):293-310, 1989. Google Scholar
  28. O.J. Vrieze and S.H. Tijs. Fictitious play applied to sequences of games and discounted stochastic games. International Journal of Game Theory, 11(2):71-85, 1982. 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