Responsable : Olivier Serre, directeur de recherche au CNRS, chercheur à l'IRIF

• Nathanaël Fijalkow chargé de recherche CNRS, LaBRI (Université de Bordeaux) [9h]
• Dietmar Berwanger chargé de recherche CNRS, LMF (ENS Paris-Saclay) [9h]
• Laurent Doyen chargé de recherche CNRS, LMF (ENS Paris-Saclay) [6h]

Suite à la publication en 1944 de l'ouvrage “Theory of Games and Economic Behavior” par John von Neumann et Oskar Mergenstern, et aux travaux conséquents de John Nash au début des années 1950, la théorie des jeux a été utilisée principalement comme un modèle pour les intéractions économiques et sociales. Cependant, depuis le début des années 1980, la théorie des jeux occupe une place de plus en plus importante en informatique et l'objectif de ce cours est de présenter divers modèles de jeux ainsi que des applications de cette théorie dans plusieurs domaines de l'informatique : théorie des automates, logique, vérification de programmes, optimisation, et apprentissage par renforcement.

Following the publication in 1944 of the book “Theory of Games and Economic Behavior” by John von Neumann and Oskar Mergenstern, and the consequent work of John Nash in the early 1950s, game theory has been used mainly as a model for economic and social interactions. However, since the early 1980s, game theory has become increasingly important in computer science and the aim of this course is to present various game models and applications of game theory in several areas of computer science: automata theory, logic, program verification, optimization, and reinforcement learning.

Nous étudions l'aspect l'algorithmique de ces jeux (calcul de valeurs et de stratégies optimales), et leurs applications en apprentissage par renforcement et en intelligence artificielle.

We study the algorithmic aspect of these games (computation of optimal values and strategies), and their applications in reinforcement learning and artificial intelligence.

L'étude des jeux de durée infinie sur des graphes est motivée entre autre par ses applications à la vérification de programme et à la théorie des automates.

Comme cas de base, nous étudions les jeux avec gains qualitatifs (gagne ou perd). Les points principaux sont :

• jeux oméga-réguliers et stratégies à mémoire finie,
• détermination positionnelle des jeux de parité, et
• algorithmes de synthèse de stratégies optimales.

Nous considérons une extension quantitative : les jeux à gain moyen. Dans ces jeux quantitatifs, chaque coup induit un gain local et les joueurs tentent de maximiser le gain cumulé à la limite.

The study of infinite duration games on graphs is motivated by its applications to program verification and automata theory.

As a basic case, we study games with qualitative payoffs (win or lose). The main points are :

• omega-regular games and finite memory strategies,
• positional determinnacy of parity games, and
• algorithms for synthesising optimal strategies.

We consider a quantitative extension: payoff games. In these quantitative games, each move induces a local payoff and players try to maximize the cumulative payoff at the limit.

Les séances auront une durée de trois heures (avec une pause). Lectures are three hours long (with a break).

Cours en présentiel. In-person lectures.

• 17/09 NO LECTURE: conference Highlights of Logic, Games, and Automata
• 24/09 (Nathanaël Fijalkow) Introduction to Stochastic Games Multi-armed bandits, Markov decision processes, Policy and value iteration algorithms
• 01/10 (Nathanaël Fijalkow) Pure and positional determinacy and value iteration
• 08/10 (Nathanaël Fijalkow) Subexponential algorithm using LP-type problems
• 15/10 (Dietmar Berwanger) Reachability, Safety games
• 22/10 (Dietmar Berwanger) Parity games
• 29/10 (Dietmar Berwanger) Game-based verification and synthesis
• 05/11 NO LECTURE
• 12/11 (Laurent Doyen) Mean payoff games
• 19/11 (Laurent Doyen) Energy games
• 26/11 Exam session

Homework 2024

Previous exams:

• Mean-payoff games Exam 2019, Solution 2019
• Reachability games in linear time Exam 2020, Solution 2020
• Weak Parity and generalized CoBüchi games Exam 2021, Solution 2021
• Rabin games and submixing property Exam 2022, Solution 2022
• Finitary parity games Exam 2023

Les cours seront en anglais. Lectures will be in English.

Les étudiants seront autorisés à rédiger leur examen en anglais ou en français. Exams papers can be written in English or in French.

This recent textbook includes all materials presented in the course: https://arxiv.org/abs/2305.10546

Exams and solutions from the past years will be shared

Les cours suivants, sans être indispensables, offrent une ouverture intéressante. The following courses, without being required to follow this course, are complementary:

• 2-8-1 Théorie non-séquentielle des systèmes distribués / Non-sequential theory of distributed systems
• 2-8-2 Fondements des systèmes temps-réel et hybrides / Foundations of real-time and hybrid systems
• 2-9-1 Aspects algorithmiques de la théorie des beaux préordres / Algorithmic Aspects of Well Quasi-Order Theory
• 2-9-2 Vérification algorithmique des programmes / Algorithmic verification of programs
• 2-16 Modélisation par automates finis / Finite automata modelling
• 2-20-2 Dynamique symbolique / Symbolic dynamics
• 2-24-1 Algorithmes et incertitude / Algorithms and Uncertainty
• 2-26-1 Logique, complexité descriptive et théorie des bases de données / Logic, descriptive complexity and database theory
• 2-29-1 Algorithmique des graphes / Graph algorithms

• Krzysztof R Apt and Erich Grädel, Lectures in Game Theory for Computer Scientists, Cambridge University Press, 2011.
• Roger B. Myerson, Game theory. Analysis of Conflict, Harvard University Press, 1991.
• Michael Maschler, Eilon Solan, Shmuel Zamir, Game theory, Cambridge University Press, 2013.
• Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory, The MIT Press, 1994
• Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.), Automata, Logics, and Infinite Games: A Guide to Current Research, LNCS 2500, Springer 2002.
• Nathanaël Fijalkow et al, Games on Graphs, 2023, https://arxiv.org/abs/2305.10546.
• Uri Zwick and Mike Paterson, The Complexity of Mean Payoff Games on Graphs, Theoretical Computer Science 158, no. 1–2: 343–59. Springer 1996.