Reachability for Branching Concurrent Stochastic Games

Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ([8]) and branching simple stochastic reachability games ([13]).
Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages115:1–115:14
Number of pages14
Volume132
ISBN (Electronic)978-3-95977-109-2
DOIs
Publication statusE-pub ahead of print - 12 Jul 2019
Event46th International Colloquium on Automata, Languages and Programming - Patras, Greece
Duration: 8 Jul 201912 Jul 2019
https://icalp2019.upatras.gr/index.php#welcome

Publication series

NameLIPICS
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume132
ISSN (Electronic)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages and Programming
Abbreviated titleICALP 2019
Country/TerritoryGreece
CityPatras
Period8/07/1912/07/19
Internet address

Keywords

  • stochastic games
  • multi-type branching processes
  • concurrent games
  • minimaxpolynomial equations
  • reachability
  • almost-sure
  • limit-sure

Fingerprint

Dive into the research topics of 'Reachability for Branching Concurrent Stochastic Games'. Together they form a unique fingerprint.

Cite this