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
  • Algorithms for Stochastic Games
    Algorithmes pour les jeux stochastiques
  • Language:
  • Period:
  • 2.
  • Duration:
  • 24h (3h/week).
  • ECTS:
  • 3.
  • Manager:
  • Stéphane Le Roux.

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

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