BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1168
DTSTAMP:20230914T125953Z
SUMMARY:The Complexity of Simple Stochastic Games
DESCRIPTION:Speaker: Pranshu Gaba\n\nAbstract: \nA Simple Stochastic Game i
s a game with a reachability objective played by two players on a directed
graph. Each vertex of the graph is either controlled by one of the player
s or is a probabilistic vertex. The game begins by placing a token on the
start vertex. In each turn\, if the token is on a probabilistic vertex\, t
hen the token moves to one of its out-neighbours uniformly at random. Else
\, the player controlling the vertex chooses an out-neigbour to move the t
oken to. Player 1 wins if the token ever reaches the target vertex and Pla
yer 0 wins otherwise.\nGiven an SSG\, we would like to find out which play
er has a greater probability of winning the game. Condon (1992) showed tha
t this problem is in NP \\intersection coNP. There are some special cases
of the game for which the problem can be solved in polynomial time. In tod
ay's talk\, we discuss proofs of the same.\nLink to paper: https://doi.org
/10.1016/0890-5401(92)90048-K\nZoom Link: https://zoom.us/j/93889521556?
pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1168
DTSTART;TZID=Asia/Kolkata:20211029T171500
DTEND;TZID=Asia/Kolkata:20211029T181500
END:VEVENT
END:VCALENDAR