Partager cette page :

Théorie des jeux sur les graphes

le 29 mars 2016

16h00

ENS Rennes, Salle du conseil
Plan d'accès

Intervention de Ocan Sankur (IRISA, CNRS) Séminaire du département Informatique et télécommunications.

Séminaire Informatique et télécommunications

Séminaire Informatique et télécommunications

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 ?
Thématique(s)
Formation, Recherche - Valorisation
Contact
David Cachera & François Schwarzentruber

Mise à jour le 22 mars 2016