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.
La partie centrale de ce cours portera sur des jeux infinis sur des graphes finis ou infinis. Cette théorie possède des applications pour les automates sur des objets infinis (mots, arbres) et pour la vérification de programme. On s'intéressera également à des extensions récentes des jeux infinis aux systèmes stochastiques.
La théorie des automates et la vérification ne sont pas les seuls domaines d'application des jeux en informatique. En effet, le domaine d'application le plus émergeant est sans doute celui qui est lié à l'Internet: la théorie des jeux étant appliquée à l'étude des équilibres du traffic de l'Internet, et ce afin d'établir des politiques de routage ou de proposer des shémas efficaces pour les enchères combinatoire. La seconde partie de ce cours proposera une introduction à ces nouveaux domaines.
Description détaillée du cours
Jeux infinis déterministes sur des graphes
L'étude des jeux infinis sur des graphes finis ou infinis est motivée par ses applications à la théorie des automates (complémentation des automates non-déterministes sur les arbres infinis), à la logique et à la vérification.
Nous étudierons les points suivants:
Jeux à stratégies optimales sans mémoire: jeux d'accessibilité, de Büchi et de parité sur des graphes finis. Cas général des jeux à mémoire finie pour les conditions de Muller
Algorithmes pour les jeux de parité.
Jeux de parité sur des graphes infinis.
Lien entre le mu-calcul et les jeux de parité.
Rudiments de théorie des automates sur les mots infinis et les arbres infinis. Applications des jeux aux automates d'arbres infinis.
Jeux sur des graphes d'automates à pile.
Introduction aux jeux boréliens. Théorème de Gale-Stewart, théorème de Martin (sans preuve).
Introduction à la théorie des jeux classique
Les points suivants seront abordés:
Jeux en forme stratégique.
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 Min-Max de John von Neuman.
Jeux en forme extensive.
Jeux stochastiques à nombre d'états fini
Les jeux stochastiques permettent de modéliser des systèmes possèdant une part d'incertitude, due par exemple à des erreurs aléatoires ou à un hasard explicite comme dans les algorithmes randomisés.
Les points suivants seront abordés:
Jeux stochastiques à un joueur (processus de décisions markoviens) avec des objectifs d'accessibilité, de Büchi ou de parité.
Algorithmes pour les jeux stochastiques simples.
Jeux stochastiques à information parfaite à deux joueurs.
Jeux stochastiques concurrents à deux joueurs.
Analyse qualitative des jeux stochastiques.
Algorithmes pour les jeux stochastiques.
Remarques sur les jeux infinis stochastiques sur des graphes d'automate à pile.
Routage égoïste
Le terme de "routage égoïste" désigne le routage sans coordination des réseaux de transport, et dans lequel chaque agent n'est intéressé que par minimiser son propre coût. La question principale est de savoir à quel point le routage égoïste réduit la performance globale du réseau.
Il existe actuellement deux modèles pour étudier ce problème:
le modèle de flot dans lequel le traffic est infiniment divisible et où chacun des agents (en nombre infini) contrôle seulement une quantité négligeable du traffic total;
un modèle discret dû à Koutsoupias et Papdimitriou dans lequel chaque agent contrôle une quantité fixe et finie du traffic total.
Nous étudierons le "prix de l'anarchie", c'est à dire la pire perte possible du bien être social dans les deux modèles.
"Mechanism design" algorithmique
L'approche traditionnelle pour les systèmes multi-agents ou distribués est de considérer que les agents suivent l'algorithme donné, i.e. sont obéissants, ou qu'ils sont hostiles et "jouent" les uns contre les autres.
Les systèmes multi-agents sont également étudiés par les économistes, mais les agents dans ce contexte ne sont sûrement pas obéissants et ne sont adversaires qu'en de rares occasions, lorsque lors objectifs sont exactement opposés. Cependant, ce qui différencie principalement les ordinateurs des acteurs économiques est le fait que ces derniers réagissent aux encouragements. C'est dans ce contexte que le problème du "mechanism design" se pose. Etant donné un objectif global donné par un concepteur de système (bien être social), comment concevoir un système d'encouragements qui ne garde que les comportements compatibles avec l'objectif du concepteur?
Ainsi le mechanism design consiste plus à concevoir un jeu satisfaisant certaines propriétés qu'à le résoudre. Il faut noter que les questions de complexité, si importante en informatique, sont négligées en économie.
L'émergence de l'Internet a changé cette problématique, la possibilité computationnelle et la compatibilité par encouragements étant tous deux importants pour l'étude d'agents indépendants intéragissant sur l'Internet. Un article fondamental de Nisan et Ronen a été le premier à considérer simultanément ces deux aspects, donnant naissance au mechanism design algorithmique.
Dans cette partie du cours nous présenterons:
une introduction au mechanism design, Vickrey-Clarke-Groves mechanism;
quelques résultats classiques d'indécidabilité (théorème de Gibbard-Sattertwaite), et
des exemples de méchanism design algorithmique.
Planning prévisionnel détaillé
Les séances d'une durée d'une heure et demi auront lieu tous les mardi de 12h45 à 14h15 sur le site de Chevaleret.
Le planning suivant est donné à titre indicatif.
Le cours sera donné en français.
Cependant, s'il est suivi par des étudiants non francophones et si tous les étudiants qui le suivent donnent leur accord, ce cours pourra être en anglais.
Le sujet d'examen sera en français et en anglais (s'il y a des étudiants qui le réclament).
Les étudiants seront autorisés à rédiger leur examen en français ou anglais.
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és 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 Modélisation et vérification des systèmes temporisés, hybrides ou concurrents.
2-9 Vérification de systèmes dynamiques et paramétrés.
2-20-2 Fondations mathématiques de la théorie des automate.
Une connaissance de la théorie classique des automates finis et des automates à pile sur les mots finis est recommandée pour ce cours. Les étudiants peu familiers avec ce domaine sont encouragés à suivre en tout début d'année le cours de remise à niveau Automates donné par Olivier Carton.
Dans une moindre mesure des connaissances en probabilité peuvent être utiles pour la partie sur les jeux stochastiques. Cependant, toutes les notions utiles seront introduites au fur et à mesure du cours. Les élèves désireux d'en savoir plus dès le départ pourront suivre le cours de remise à niveau Probabilités s'ils le jugent utile.
Bibliographie
Roger B. Myerson, Game theory. Analysis of Conflict, Harvard 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.
Tim Roughgarden, Selfish Routing and the Price of Anarchy. The MIT Press (avec google on peut trouver la thèse de Roughgarden qui couvre une grande partie de ce livre).
Roger B. Myerson, Game theory. Analysis of Conflict, Harvard University 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.
![[arobase]](./commercial_at.png){kind=small}
mpri![[point]](./full_stop.png){kind=small}
master![[English version]](./english_flag.png)