Personal tools
You are here: Home Events Title: Reachability for Branching Concurrent Stochastic Games

Title: Reachability for Branching Concurrent Stochastic Games

— filed under:

Speaker: Kousha Etessami

  • Lab Lunch
When Feb 06, 2018
from 01:00 PM to 02:00 PM
Where Mini Forum 2 (MF2) Level 4
Add event to calendar vCal



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.)
Document Actions