Shapley’s stochastic games and related models, such as Markov decision processes and parity games play a central role in various disciplines, including game theory, operations research and computer science. Within computer science, the models are of interest to a wide range of subcommunities, including formal methods, artificial intelligence, theory of algorithms and computational complexity. Studying variations of the model and its associated algorithms have recently led to significant and unexpected new discoveries, including a much improved understanding of the simplex algorithm for linear programs. The purpose of this mini-course is to lead the participants to the research frontier of this exciting topic.

The course is held as an activity within the Sino-Danish Center for the Theory of Interactive Computation, supported by the Danish National Research Foundation and The National Science Foundation of China (under the grant61061130540). It will take place at Room 1-312, FIT Building, Tsinghua University during October 31-November 2. 2011

Visit the course webpage