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.
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 ?
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