1. Stéphane Le Roux, first term
2. Xavier Allamigeon, second term

To survey stochastic games (the notion of value, complexity classes, strategy implementation, etc) and to cover some recent advances with algorithmic flavor.

1. Zero-sum two-player games, mixed strategies, optimal strategies
2. multi-player games, Nash equilibrium, Subgame perfect equilibrium
3. Infinite turn-based games on well-founded trees

1. Zero-sum two-player games and optimal strategies
2. The von Neumann minimax theorem
3. Multi-player games, Nash equilibrium
4. Nash theorem

1. Some properties of infinite trees
2. The notion of Borel set
3. Turn-based games on infinite trees
4. Representation of strategies
5. Statement of Borel determinacy
6. Part of the proof

1. The notion of Borel-measurable map
2. Blackwell games
3. Statement of Blackwell determinacy
4. Part of the proof

1. Turn-based games
2. Concurrent games

1. The one-player case: Markov decision processes.
2. Problems in finite horizon, discounted, with stopping time, and with mean-payoff.
3. Bellman’s dynamic programming equation. Positional strategies versus history-dependent strategies.
4. The zero-sum two-player case: Shapley’s extension of Bellman equation.
5. Miscellaneous examples, some being unexpected: risk-sensitive problems, log-glasses transform positive linear dynamics (population dynamics) to games, matrix scaling problems, nonnegative tensors.

1. The operator approach. The ergodic equation (additive eigenproblem). When it is solvable, the value of the mean-payoff game does exist, and coincides with the limit value of finite horizon games and discounted games.
2. Ergodicity notions for Markov decision processes. Bather’s theorem on communicating Markov decision processes.
3. Extensions of Bather’s theorem to the two-player case. Ergodicity notions for stochastic games. The role of dominions.
4. Non-ergodic turn-based games. Kohlberg’s theorem on the existence of invariant half-lines.
5. Blackwell optimal policies (optimal for all discount rates close enough to zero) do exist for turn-based game.
6. Non-ergodic concurrent games. Existence of the uniform value. Approach by Bewley, Kohlberg, Mertens and Neyman, using the semialgebraic character of the discounted value. Generalization to games definable in o-minimal structures.

1. Value iteration and relative value iteration. Contraction properties in various norms and seminorms. Dobrushin ergodicity coefficient and Birkhoff’s contraction theorem. Example of the stochastic shortest path problem (contraction theorem of Bertsekas and Tsitsiklis). Parameterized complexity bounds for ergodic games.
2. The theorem of Ye, Hansen, Miltersen and Zwick: policy iteration with a fixed discount factor is strongly polynomial for zero-sum two-player turn-based games.
3. Reduction of the mean-payoff problem to the discounted problem with small discount rate. Bounds on the Blackwell threshold.
4. The complexity of concurrent games.
5. Mean-payoff games and tropical geometry. Embedding mean-payoff games in nonarchimedean linear programs. Link between the complexity of mean-payoff games and the complexity of linear programming

• Stéphane Le Roux
• Xavier Allamigeon
• Nathanaël Fijalkow
• Stéphane Gaubert