title:
Algorithms for Stochastic Games
Algorithmes pour les jeux stochastiques
manager:
Stéphane Le Roux
ects:
3
period:
2
hours:
24
weeks:
8
hours-per-week:
3
lang:
themes:
Automata/Games, Verification, Algorithms
year:
2025

Lecturers for 2025-2026

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

Objective of the course

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

Contents

First term

Von Neumann minimax theorem (quickly), Martin's Borel determinacy, Martin's Blackwell determinacy, positional and finite-memory strategies for turn-based and concurrent games on graph.

Second term

Schedule

Full lecturing team