Reachability for Branching Concurrent Stochastic Games

Kousha Etessami; Emanuel Martinov; Alistair Stewart; Mihalis Yannakakis

doi:r 10.4230/LIPIcs.ICALP.2019.115

Reachability for Branching Concurrent Stochastic Games

Kousha Etessami, Emanuel Martinov, Alistair Stewart, Mihalis Yannakakis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract / Description of output

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 language	English
Title of host publication	46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Editors	Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages	115:1–115:14
Number of pages	14
Volume	132
ISBN (Electronic)	978-3-95977-109-2
DOIs	https://doi.org/r 10.4230/LIPIcs.ICALP.2019.115
Publication status	E-pub ahead of print - 12 Jul 2019
Event	46th International Colloquium on Automata, Languages and Programming - Patras, Greece Duration: 8 Jul 2019 → 12 Jul 2019 https://icalp2019.upatras.gr/index.php#welcome

Publication series

Name	LIPICS
Publisher	Schloss Dagstuhl - Leibniz-Zentrum für Informatik
Volume	132
ISSN (Electronic)	1868-8969

Conference

Conference	46th International Colloquium on Automata, Languages and Programming
Abbreviated title	ICALP 2019
Country/Territory	Greece
City	Patras
Period	8/07/19 → 12/07/19
Internet address	https://icalp2019.upatras.gr/index.php#welcome

Keywords / Materials (for Non-textual outputs)

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

Access to Document

r 10.4230/LIPIcs.ICALP.2019.115

Reachability for Branching Concurrent_ETESSAMI_DoA190419_ArxivSubmitted manuscript, 489 KB
Reachability for Branching Concurrent_ETESSAMI_DoA190419_AFVAccepted author manuscript, 503 KBLicence: Creative Commons: Attribution (CC-BY)
Reachability for Branching_ETESSAMI_DoA190419_VoR_CC-BY
© Kousha Etessami, Emanuel Martinov, Alistair Stewart, and Mihalis Yannakakis; licensed under Creative Commons License CC-BY
Final published version, 501 KBLicence: Creative Commons: Attribution (CC-BY)

Cite this

Etessami, K., Martinov, E., Stewart, A., & Yannakakis, M. (2019). Reachability for Branching Concurrent Stochastic Games. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (Vol. 132, pp. 115:1–115:14). Article 115 (LIPICS; Vol. 132). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. Advance online publication. https://doi.org/r 10.4230/LIPIcs.ICALP.2019.115

Etessami, Kousha ; Martinov, Emanuel ; Stewart, Alistair et al. / Reachability for Branching Concurrent Stochastic Games. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). editor / Christel Baier ; Ioannis Chatzigiannakis ; Paola Flocchini ; Stefano Leonardi. Vol. 132 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2019. pp. 115:1–115:14 (LIPICS).

@inproceedings{b2f3a6e6bee24a74ac3d66833caac156,

title = "Reachability for Branching Concurrent Stochastic Games",

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]).",

keywords = "stochastic games, multi-type branching processes, concurrent games, minimaxpolynomial equations, reachability, almost-sure, limit-sure",

author = "Kousha Etessami and Emanuel Martinov and Alistair Stewart and Mihalis Yannakakis",

year = "2019",

month = jul,

day = "12",

doi = "r 10.4230/LIPIcs.ICALP.2019.115",

language = "English",

volume = "132",

series = "LIPICS",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany",

pages = "115:1–115:14",

editor = "Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi",

booktitle = "46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)",

note = "46th International Colloquium on Automata, Languages and Programming, ICALP 2019 ; Conference date: 08-07-2019 Through 12-07-2019",

url = "https://icalp2019.upatras.gr/index.php#welcome",

}

Etessami, K, Martinov, E, Stewart, A & Yannakakis, M 2019, Reachability for Branching Concurrent Stochastic Games. in C Baier, I Chatzigiannakis, P Flocchini & S Leonardi (eds), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). vol. 132, 115, LIPICS, vol. 132, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, pp. 115:1–115:14, 46th International Colloquium on Automata, Languages and Programming, Patras, Greece, 8/07/19. https://doi.org/r 10.4230/LIPIcs.ICALP.2019.115

Reachability for Branching Concurrent Stochastic Games. / Etessami, Kousha; Martinov, Emanuel; Stewart, Alistair et al.
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). ed. / Christel Baier; Ioannis Chatzigiannakis; Paola Flocchini; Stefano Leonardi. Vol. 132 Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2019. p. 115:1–115:14 115 (LIPICS; Vol. 132).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Reachability for Branching Concurrent Stochastic Games

AU - Etessami, Kousha

AU - Martinov, Emanuel

AU - Stewart, Alistair

AU - Yannakakis, Mihalis

PY - 2019/7/12

Y1 - 2019/7/12

N2 - 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]).

AB - 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]).

KW - stochastic games

KW - multi-type branching processes

KW - concurrent games

KW - minimaxpolynomial equations

KW - reachability

KW - almost-sure

KW - limit-sure

UR - https://icalp2019.upatras.gr/

U2 - r 10.4230/LIPIcs.ICALP.2019.115

DO - r 10.4230/LIPIcs.ICALP.2019.115

M3 - Conference contribution

VL - 132

T3 - LIPICS

SP - 115:1–115:14

BT - 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

A2 - Baier, Christel

A2 - Chatzigiannakis, Ioannis

A2 - Flocchini, Paola

A2 - Leonardi, Stefano

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany

T2 - 46th International Colloquium on Automata, Languages and Programming

Y2 - 8 July 2019 through 12 July 2019

ER -

Etessami K, Martinov E, Stewart A, Yannakakis M. Reachability for Branching Concurrent Stochastic Games. In Baier C, Chatzigiannakis I, Flocchini P, Leonardi S, editors, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Vol. 132. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2019. p. 115:1–115:14. 115. (LIPICS). Epub 2019 Jul 12. doi: r 10.4230/LIPIcs.ICALP.2019.115

Reachability for Branching Concurrent Stochastic Games

Abstract / Description of output

Publication series

Conference

Keywords / Materials (for Non-textual outputs)

Access to Document

Other files and links

Fingerprint

Cite this