A Simple Stochastic Game is 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 players 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, then 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 token to. Player 1 wins if the token ever reaches the target vertex and Player 0 wins otherwise.
Given an SSG, we would like to find out which player has a greater probability of winning the game. Condon (1992) showed that 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 today's talk, we discuss proofs of the same.
Link to paper: https://doi.org/10.1016/0890-5401(92)90048-K
Zoom Link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09
