Lab Lunch: 6 February 2018 - Kousha Etessami

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 form a class of infinite-state imperfect-information stochastic games that generalize both finite-state concurrent stochastic reachability games ([de Alfaro-Henzinger-Kupferman'98]), as well as branching simple stochastic reachability games ([Etessami-Stewart-Yannakakis'15]). We also show that approximating the reachability game value for BCSGs is in the complexity class FIXP, and thus is reducible to computing any Nash equilibrium for a 3-player normal form game to within desired accuracy. (Joint work with Emanuel Martinov, Alistair Stewart, and Mihalis Yannakakis.)