Document Open Access Logo

Reachability for Branching Concurrent Stochastic Games (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2019.115.pdf
  • Filesize: 0.48 MB
  • 14 pages

Document Identifiers

Author Details

Kousha Etessami
  • School of Informatics, University of Edinburgh, UK
Emanuel Martinov
  • School of Informatics, University of Edinburgh, UK
Alistair Stewart
  • Department of Computer Science, University of Southern California, Los Angeles, CA, USA
Mihalis Yannakakis
  • Department of Computer Science, Columbia University, New York City, NY, USA

Funding

Research partially supported by an EPSRC studentship EP/N509644/1-1789473 (Martinov), and by NSF Grants CCF-1703925,CCF-1763970 (Yannakakis).

Cite As Get BibTex

Kousha Etessami, Emanuel Martinov, Alistair Stewart, and Mihalis Yannakakis. Reachability for Branching Concurrent Stochastic Games (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 115:1-115:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ICALP.2019.115

Abstract

We give polynomial time algorithms for deciding almost-sure and limit-sure reachability in Branching Concurrent Stochastic Games (BCSGs). These are a class of infinite-state imperfect-information stochastic games that generalize both finite-state concurrent stochastic reachability games ([L. de Alfaro et al., 2007]) and branching simple stochastic reachability games ([K. Etessami et al., 2018]).

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • stochastic games
  • multi-type branching processes
  • concurrent games
  • minimax-polynomial equations
  • reachability
  • almost-sure
  • limit-sure

Metrics

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

Related Versions

References

  1. R. Bonnet, S. Kiefer, and A. W. Lin. Analysis of Probabilistic Basic Parallel Processes. In Proc. of FoSSaCS'14, pages 43-57, 2014. Google Scholar
  2. Bozic and et. al. Evolutionary dynamics of cancer in response to targeted combination therapy. eLife, 2:e00747, 2013. Google Scholar
  3. T. Brázdil, V. Brozek, V. Forejt, and A. Kucera. Reachability in recursive markov decision processes. Inf. Comput., 206(5):520-537, 2008. Google Scholar
  4. T. Brázdil, V. Brozek, A. Kucera, and J. Obdrzálek. Qualitative reachability in stochastic BPA games. Inf. Comput., 209(8):1160-1183, 2011. Google Scholar
  5. K. Chatterjee, K. A. Hansen, and R. Ibsen-Jensen. Strategy complexity of concurrent safety games. In Proc. of 42nd Inter. Symp. on Math. Found. of Computer Science (MFCS), volume 83 of LIPIcs, pages 55:1-55:13, 2017. Google Scholar
  6. T. Chen, K. Dräger, and S. Kiefer. Model Checking Stochastic Branching Processes. In Proc. of MFCS'12, volume 7464 of Springer LNCS, pages 271-282, 2012. Google Scholar
  7. A. Condon. The complexity of stochastic games. Inf. &Comput., 96(2):203-224, 1992. Google Scholar
  8. L. de Alfaro, T. A. Henzinger, and O. Kupferman. Concurrent reachability games. Theoretical Computer Science, 386(3):188-217, 2007. (Conference version in FOCS'98). Google Scholar
  9. E. Denardo and U. Rothblum. Totally expanding multiplicative systems. Linear Algebra Appl., 406:142-158, 2005. Google Scholar
  10. J. Esparza, A. Kučera, and R. Mayr. Model checking probabilistic pushdown automata. Logical Methods in Computer Science, 2(1):1-31, 2006. Google Scholar
  11. K. Etessami, A. Stewart, and M. Yannakakis. Polynomial-time algorithms for Branching Markov Decision Processes, and probabilistic min(max) polynomial Bellman equations. In Proc. of 39th Int. Coll. on Automata, Languages and Programming (ICALP), 2012. (All references are to the full preprint Arxiv:1202.4789). Google Scholar
  12. K. Etessami, A. Stewart, and M. Yannakakis. A polynomial-time algorithm for computing extinction probabilities of multitype branching processes. SIAM J. Computing, 46(5):1515-1553, 2017. (Conference version in STOC'12). Google Scholar
  13. K. Etessami, A. Stewart, and M. Yannakakis. Greatest Fixed Points of Probabilistic Min/Max Polynomial Equations, and Reachability for Branching Markov Decision Processes. Information and Computation, 261:355-382, 2018. (special issue for ICALP'15). Google Scholar
  14. K. Etessami, D. Wojtczak, and M. Yannakakis. Recursive stochastic games with positive rewards. In Proc. of 35th ICALP (1), volume 5125 of Springer LNCS, pages 711-723, 2008. Google Scholar
  15. K. Etessami and M. Yannakakis. Recursive Concurrent Stochastic Games. Logical Methods in Computer Science, 4(4), 2008. Google Scholar
  16. K. Etessami and M. Yannakakis. Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations. Journal of the ACM, 56(1), 2009. Google Scholar
  17. K. Etessami and M. Yannakakis. Recursive Markov decision processes and recursive stochastic games. Journal of the ACM, 62(2):1-69, 2015. Google Scholar
  18. H. Everett. Recursive games. Contributions to the Theory of Games, 3(39):47-78, 1957. Google Scholar
  19. S. K. S Frederiksen and P. B. Miltersen. Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy. In Proc. of 24th ISAAC, pages 457-467, 2013. Google Scholar
  20. P. Haccou, P. Jagers, and V. A. Vatutin. Branching Processes: Variation, Growth, and Extinction of Populations. Cambridge U. Press, 2005. Google Scholar
  21. K. A. Hansen, R. Ibsen-Jensen, and P. B. Miltersen. The Complexity of Solving Reachability Games using Value and Strategy Iteration. Theory Comput. Syst., 55(2):380-403, 2014. Google Scholar
  22. K. A. Hansen, M. Koucky, and P. B. Miltersen. Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. In Proc. of 24th Annual IEEE Symp. on Logic in Computer Science, pages 332-341, 2009. Google Scholar
  23. T. E. Harris. The Theory of Branching Processes. Springer-Verlag, 1963. Google Scholar
  24. M. Kimmel and D. E. Axelrod. Branching processes in biology. Springer, 2002. Google Scholar
  25. H. Michalewski and M. Mio. On the problem of computing the probability of regular sets of trees. In Proc. of FSTTCS'15, pages 489-502, 2015. Google Scholar
  26. S. Pliska. Optimization of multitype branching processes. Management Sci., 23(2):117-124, 1976/77. Google Scholar
  27. M. Przybyłko and M. Skrzypczak. On the complexity of branching games with regular conditions. In Proc. of MFCS'16, volume 78 of LIPIcs, 2016. Google Scholar
  28. G. Reiter, I. Bozic, K. Chatterjee, and M. A. Nowak. TTP: Tool for tumor progression. In Proc. of CAV'2013, volume 8044 of Springer LNCS, pages 101-106, 2013. Google Scholar
  29. U. Rothblum and P. Whittle. Growth optimality for branching Markov decision chains. Math. Oper. Res., 7(4):582-601, 1982. Google Scholar
  30. A. Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5(2):285-309, 1955. Google Scholar
  31. D. Wojtczak. Expected termination time in BPA games. In Proc of ATVA'2013, pages 303-318, 2013. 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