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

Techniques de théorie des jeux en informatique (24h, 3 ECTS)

Responsable: W. Zielonka, professeur à l'Université Paris-Diderot

Intervenants prévus pour 2019-2020

  • Dietmar Berwanger chargé de recherche CNRS, LSV (ENS Paris-Saclay) [12h],
  • Olivier Serre directeur de recherche CNRS, IRIF (Université Paris Diderot) [12h].

Objectifs

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.

Le cours portera sur des jeux infinis sur des graphes finis ou infinis. Cette théorie possède des applications pour la théorie des automates (automates d'arbre), la vérification de programme (mu-calcul ou autres logiques).

Nous proposerons une étude approfondie de plusieurs classes de jeux (et de leurs combinaisons): jeux stochastiques, jeux muni de fonction de paiement, jeux à information imparfaite.

Description détaillée du cours

Jeux à information parfaite sur des graphes:

L'étude des jeux infinis sur des graphes finis ou infinis est motivée par ses applications à la vérification de programme et à la théorie des automates.

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

  • jeux oméga-réguliers et stratégies d'état fini,
  • détermination positionnelle des jeux de parité, et
  • algorithmes de synthèse de stratégies optimales.

Par extension, nous considérons les jeux à gain moyen. Dans ces jeux quantitatifs, chaque coup induit un gain local et les joueurs tentent de maximiser le gain cumulé à la longue.

Simple stochastic games

C'est la classe la plus simple de jeux stochastiques à information parfaite. Nous étudions surtout l'aspect l'algorithmique de ces jeux (calcul de valeurs et de stratégies optimales).

Jeux à information imparfaite, coups concurrents:

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.

Planning prévisionnel détaillé

Les séances auront une durée de trois heures.

  • 10/09 (Olivier Serre) Introduction, reachability games
  • 17/09 (Olivier Serre) Büchi games, parity games
  • 24/09 (Olivier Serre) Tree automata
  • 1/10 (Nathanael Fijalkow: guest lecture) Quasipolynomial time algorithms for parity games
  • 8/10 (Dietmar Berwanger) Mean-payoff, simple stochastic games
  • 22/10 (Dietmar Berwanger) Games for verification and synthesis
  • 29/10 (Dietmar Berwanger) Imperfect information I
  • 5/11 (Dietmar Berwanger) Imperfect information II

Langues du cours

Dietmar Berwanger donnera le cours en anglais. Olivier Serre et Nathana&etrema;l Fijalkow donneront le cours en français ou anglais.

Les étudiants seront autorisés à rédiger leur examen en anglais ou en français.

Support de cours

Des supports de cours seront accessibles depuis les pages suivantes :

Cela dit, il s'agira plus de notes ou de copies de transparents que d'un polycopié détaillé.

Des exercices seront également proposés à la fin de certaines séances et seront corrigés pour les étudiants qui le souhaiteront.

Cours liés

Les cours suivants, sans être indispensables, offrent une ouverture intéressante:

  • 2-8-1 Fondements pour la vérification des systèmes en temps-réel et hybrides
  • 2-8-2 Théorie non-séquentielle des systèmes distribués
  • 2-9 Vérification de systèmes dynamiques et paramétrés
  • 2-20-2 Fondations mathématiques de la théorie des automates
  • 2-29-1 Algorithmique des graphes

Pré-requis

Une connaissance de la théorie classique des automates finis sur les mots finis (voire infini) est recommandée pour ce cours.

Des connaissances élémentaires en probabilité seront utiles (notion d'espérance).

Bibliographie

  • 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.

Équipe pédagogique

 
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