Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Techniques de théorie des jeux en informatique / Game theory in computer science (24h, 3 ECTS)

Responsable / Course supervisor

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

Intervenants en 2021-2022 / Teachers in 2021-2022

Contexte scientifique / Scientific context

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.

Description détaillée du cours / Course outline

Jeux oméga réguliers sur des graphes / Omega regular games on graphs

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.

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.

Jeux à paiement / Payoff games

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.

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.

Jeux à information imparfaite et à coups simultanés / Imperfect information games and concurrent games

Les jeux à information imparfaite modélisent des situations dans lesquelles les preneurs de décision sont incertains quant aux événements qui ont eu lieu dans le système global. Des cas particuliers importants sont les jeux concurrents où les joueurs agissent simultanément. Nous parcourons plusieurs critères de comportement optimal dans ces jeux et les questions algorithmiques associées.

Imperfect information games model situations in which decision-makers are uncertain about the events that are uncertain about the events that have taken place in the overall system. Important special cases are concurrent games where players act simultaneously. We review several criteria for optimal behaviour in these games and the associated algorithmic issues.

Processus de décisions Markoviens et jeux stochastiques / Markov decision processes and stochastic games

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.

Calendrier / Calendar

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

  • 20/09 (Nathanaël Fijalkow) Introduction: reachability games, Büchi games, parity games
  • 27/09 (Dietmar Berwanger) Mean-payoff, simple stochastic games
  • 04/10 (Dietmar Berwanger) Imperfect information I
  • 11/10 (Dietmar Berwanger) Imperfect information II
  • 18/10 (Nathanaël Fijalkow) A quasipolynomial time algorithm for parity games
  • 25/10 (Dietmar Berwanger) Games for verification and synthesis
  • 08/11 (Nathanaël Fijalkow) Markov decision processes: value iteration, strategy improvement
  • 15/11 (Nathanaël Fijalkow) Monte Carlo tree search for Markov decision processes

Langues du cours / Spoken language

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.

Support de cours / Lecture notes

Des supports de cours seront accessibles en ligne. Lecture notes will be made available online.

Cours liés au MPRI / Related courses in MPRI

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

Pré-requis / Prerequisites

  • théorie classique des automates / classic automata theory
  • notions de probabilités discrètes / discrete probability theory

Bibliographie / References

  • 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.
  • Uri Zwick and Mike Paterson, The Complexity of Mean Payoff Games on Graphs, Theoretical Computer Science 158, no. 1–2: 343–59. Springer 1996.
 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA