Théorie des jeux sur les graphes

On s'intéresse aux jeux joués sur des graphes. Dans ces jeux, un jeton est posé initialement sur un sommet. A chaque tour, un joueur déplace le jeton vers un autre sommet en suivant une arrête. Les joueurs jouent à tour de rôle. Chaque joueur a un objectif précis, par exemple éviter de visiter un certain sommet.

Dans cet exposé, on présentera les résultats classiques sur ces jeux. Comment calculer une stratégie gagnante pour un joueur s'il en existe, autrement dit, une stratégie qui assure l'objectif du joueur quelque soit le comportement des autres joueurs. Quelle est la complexité de ce problème ? Quelle est la complexité de la stratégie; que doit retenir le joueur pendant le jeu pour pouvoir appliquer sa stratégie ? On s'intéressera ensuite aux équilibres de Nash dans ces jeux : il s'agit des profils de stratégies pour tous les joueurs qui assurent qu'aucun d'entre eux n'a intérêt à changer de stratégie. Enfin, on considérera la domination entre les stratégies d'un joueur : une stratégie donnée est-elle toujours un meilleur choix qu'une autre ?