The universe of 2-player zero-sum stochastic games: Discounted vs. undiscounted (mean payoff) games, turn-based vs. concurrent games, Markov decision processes, Reachability games, Stochastic shortest path problems, parity games, energy games. Abstract models; LP-like problems and Acyclic Sink Orientations.
The universe of algorithms for solving them: Value and Strategy iteration, LP-based approaches, recent alternatives, hierarchies and reductions.
The course will feature lectures and tutorials with problem solving. The prerequisites is an understanding of basic linear programming (the simplex algorithm, duality, and the notion of matrix games) and complexity analysis of algorithms (Asymptotic complexity, and the notions of poly time and polynomial time reductions).
Program at a glance
| Oct. 31 (Mon.) | Nov. 1 (Tue.) | Nov. 2 (Wed.) | |
| 09:00-09:50 | Lecture 1 | Lecture 4 | Lecture 7 |
| 10:00-10:50 | Lecture 2 | Lecture 5 | Lecture 8 |
| 10:50-11:10 | Break | ||
| 11:10-12:00 | Assignment Session 1 | Assignment Session 3 | Assignment Session 5 |
| 12:00-14:00 | Lunch Break | ||
| 14:00-14:50 | Lecture 3 | Lecture 6 | Lecture 9 |
| 14:50-15:10 | Break | ||
| 15:10-16:00 | Assignment Session 2 | Assignment Session 4 | Assignment Session 6 |
Detail
| Venue: Room 1-312, FIT Building, Tsinghua University | ||
| Monday, October 31 | ||
| Time | Speaker/Lecturer | Title/Topic |
| 08:00-09:00 | Registration | |
| 09:00-09:50 | Uri Zwick | Turn-based (perfect information) stochastic games I |
| 10:00-10:50 | Turn-based (perfect information) stochastic games II | |
| 10:50-11:10 | Group Photo & Break | |
| 11:10-12:00 | Assignment Session 1 | |
| 12:00-14:00 | Lunch Break | |
| 14:00-14:50 | Uri Zwick | Lower bounds for policy iteration and LP pivoting rules |
| 14:50-15:10 | Break | |
| 15:10-16:00 | Assignment Session 2 | |
| Tuesday, November 1 | ||
| Time | Speaker/Lecturer | Title/Topic |
| 08:00-09:00 | Registration | |
| 09:00-09:50 | Marcin Jurdzinski | Parity games |
| 10:00-10:50 | Efficient algorithms for parity games 1 | |
| 10:50-11:10 | Break | |
| 11:10-12:00 | Assignment Session 3 | |
| 12:00-14:00 | Lunch Break | |
| 14:00-14:50 | Marcin Jurdzinski | Efficient algorithms for parity games 2 |
| 14:50-15:10 | Break | |
| 15:10-16:00 | Assignment Session 4 | |
| Wednesday, November 2 | ||
| Time | Speaker/Lecturer | Title/Topic |
| 08:00-09:00 | Registration | |
| 09:00-09:50 | Peter Miltersen | Stochastic Games of Imperfect Information I |
| 10:00-10:50 | Stochastic Games of Imperfect Information II | |
| 10:50-11:10 | Break | |
| 11:10-12:00 | Assignment Session 5 | |
| 12:00-14:00 | Lunch Break | |
| 14:00-14:50 | Peter Miltersen | A glimpse beyond |
| 14:50-15:10 | Break | |
| 15:10-16:00 | Assignment Session 6 | |