The complexity issues on stochastic games

2015/04/21 Tue 16:30 - 18:00
牧野 和久

Stochastic games were introduced in 1953 by Shapley for the discounted case, and extended to the undiscounted case in 1957 by Gillette. Each such game is a dynamic game with probabilistic transitions played by two players on a finite set of states. The game is played in the infinite sequence of rounds. In the round, the game is in some state. The players choose actions. Then they receive payoffs and the game moves to a new random state, where the payoffs and the transition probability depend on the previous state and the actions chosen by the players. The procedure is repeated at the new state. Stochastic games generalize parity games, cyclic games, simple stochastic games, and BWR games, which all belong to NP and coNP, but are not known to be solved in polynomial time. In this talk, I briefly survey the algorithmic issues on these games, as well as the properties on the optimal strategies for them. I also discuss recent works obtained with Endre Boros, Khaled Elbassioni, and Vladimir Gurvich.