UIC Graduate Student Seminar
Friday January 19, January 26
3:00 pm
636 SEO
Speaker: T.E.S. Raghavan
Title: Stochastic Games I
Abstract:
A two person stochastic game is one where the two players play one of several games each day. It results in immediate rewards for the two players. A well defined law of motion tells the players what game is to be played tomorrow. The law of motion depends only on what game they played today and what actions they took in the current game. Players continue to play everyday and collect the rewards. The stream of rewards are evaluated by an overall payoff. This could be either a net present value, based on a discout factor, or a long run average reward, by taking a suitable limiting average concept. The main problem is to look for optimal strategies or equilibrium strategies for the stochastic game. In general they exist for discounted games. For zero-sum two person stochastic games with limiting average payoff, in general no optimal strategies exist but only, almost optimal strategies. Further for such payoffs any almost optimal strategy could be quite complicated and might involve a complete knowledge of the past moves and games visited. The first talk will introduce models of ordinary games and motivate the notion of mixed and optimal strategies in one shot games. In the second talk we will discuss, the main theorems and special computational aspects of solving structured classes of stochastic games. We will look for optimal strategies among simple subclasses of the set of all possible strategies. The talk will stress on specific examples and specific algorithms to handle these subclasses.