会议介绍及日程：
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.
===========================
Invited Lecturers
Marcin Jurdzinski, University of Warwick
Peter Bro Miltersen, Aarhus University
Uri Zwick, Tel Aviv University
Tentative Program
Monday, October 31, 2011
08:00-09:00 Registration
09:00-09:50 Turn-based (perfect information) stochastic games I
Uri Zwick
10:00-10:50 Turn-based (perfect information) stochastic games II
Uri Zwick
10:50-11:10 Break
11:10-12:00 Assignment Session 1
12:00-14:00 Lunch Break
14:00-14:50 Lower bounds for policy iteration and LP pivoting rules
Uri Zwick
14:50-15:10 Break
15:10-16:00 Assignment Session 2
Tuesday, November 1, 2011
08:00-09:00 Registration
09:00-09:50 Parity games
Marcin Jurdzinski
10:00-10:50 Efficient algorithms for parity games 1
Marcin Jurdzinski
10:50-11:10 Break
11:10-12:00 Assignment Session 3
12:00-14:00 Lunch Break
14:00-14:50 Efficient algorithms for parity games 2
Marcin Jurdzinski
14:50-15:10 Break
15:10-16:00 Assignment Session 4
Wednesday, November 2, 2011
08:00-09:00 Registration
09:00-09:50 Stochastic Games of Imperfect Information I
Peter Miltersen
10:00-10:50 Stochastic Games of Imperfect Information II
Peter Miltersen
10:50-11:10 Break
11:10-12:00 Assignment Session 5
12:00-14:00 Lunch Break
14:00-14:50 A glimpse beyond
Peter Miltersen
14:50-15:10 Break
15:10-16:00 Assignment Session 6
