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 à Paris 7

Intervenants prévus pour 2018-2019

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.

Une partie centrale de ce 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).

Ce cours proposera également une étude approfondie de plusieurs classes de jeux (et de leurs combinaisons): jeux stochastiques, jeux muni de fonction de paiement, jeux à information imparfaite.

La théorie classique des jeux sera également abordée en donnant les grands principes des jeux sous forme normale (et des notions d'équilibre) ainsi qu'une introduction au mecanism design.

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.

Introduction à la théorie des jeux classique

Les points suivants seront abordés:

  • Jeux en forme stratégique et en forme extensive.
  • Existence d'un équilibre de Nash (théorème de Nash).
  • Jeux à deux joueurs à somme nulle avec un nombre fini de stratégies, théorème minimax de von Neumann.

Planning prévisionnel détaillé

Les séances d'une durée de trois heures.

  • 13/09 (Wieslaw Zielonka) perfect information games : finite games, combinatorial games, reachability games, Buchi games
  • 20/09 (Wieslaw Zielonka) multi-player games and Nash equilibria, backward induction
  • 27/09 (Dietmar Berwanger) vérification and synthesis, parity games
  • 04/10 (Dietmar Berwanger) parity games : application to automata theory, energy games
  • 11/10 (Dietmar Berwanger) mean-payoff games
  • 18/10 (Wieslaw Zielonka) simple stochastic games
  • 25/10 (Wieslaw Zielonka) matrix games, concurrent reachability games
  • 08/11 (Dietmar Berwanger) imperfect information games

Langues du cours

Dietmar Berwanger donnera le cours en anglais. Wieslaw Zielonka donnera le cours en français.

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-2 Modèles des langages de programmation: domaines, catégories, jeux.
  • 2-8 Fondements pour la vérification des systèmes temps-réel.
  • 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

  • Roger B. Myerson, Game theory. Analysis of Conflict,Harvard University Press.
  • Michael Maschler, Eilon Solan, Shmuel Zamir, Game theory,Cambridge University Press
  • Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory,The MIT Press.
  • Drew Fudenberg and Jean Tirole, Game theory,The MIT Press.
  • Erich Grädel, Wolfgang Thomas, Thomas Wilke (eds.), Automata, Logics, and Infinite Games: A Guide to Current Research[outcome of a Dagstuhl seminar, February 2001], Lecture Notes in Computer Science 2500, Springer 2002.
  • Erich Grädel et al., Finite Model Theory and Its Applications,EATCS Texts in Theoretical Computer Science, Springer 2007.

É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