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.) Feb 06 2018 13.00 - 14.00 Lab Lunch: 6 February 2018 - Kousha Etessami Speaker: Kousha Etessami MF2 level 4
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.) Feb 06 2018 13.00 - 14.00 Lab Lunch: 6 February 2018 - Kousha Etessami Speaker: Kousha Etessami MF2 level 4
