Programme de l’UE

La théorie des jeux est aujourd’hui un outil indispensable pour comprendre l’évolution de domaines aussi divers que l’apprentissage, la tarification, l’optimisation distribuée ou l’algorithmique des réseaux de communications.

Plan général:

  • En introduction, nous allons introduire les concepts principaux de la théorie des jeux (définition, matrice de gain, équilibre de Nash, de Wardrop, notions d’équité, mesure d’efficacité).
  • Dans un deuxième temps, nous allons étudier plus précisément certains types de jeux: jeux à somme nulle, jeux de potentiel, jeux super-additifs.
  • Une troisième partie présentera les mécanismes d’enchères et les coalitions qui donnent lieu à des notions d’équilibres légèrement différentes.
  • Une quatrième partie sera consacrée à quelques applications dans le domaine des réseaux de communication (on montrera en particulier que TCP est équitable au sens de l’équité proportionnelle), et des méthodes de résolution de routage optimal.

Le deuxième volet du cours sera consacré aux algorithmes de calcul des équilibres dans les contextes présentés précédemment.

  • On présentera la dynamique de meilleure réponse, de réplication,… et on montrera leurs propriétés de convergence vers les équilibres de Nash.
  • Nous étudierons ensuite des versions algorithmiques distribuées de ces dynamiques en mettant en évidence les difficultés qui apparaissent alors.
  • Une dernière partie sera consacrée à étudier les liens avec les dynamiques d’apprentissages (recuit simulé, méthode de Monte Carlo et plus généralement, les méthodes d’approximations stochastiques)

Dates des cours :

Liens sur des transparents.

Intervenants

  • Bruno Gaujal, DR INRIA
  • Corinne Touati, CR INRIA