Détermination et décidabilité des jeux stochastiques à observation partielle

Hugo Gimbert
Labri, Bordeaux
Thursday, 18 December, 2008 (All day)
NO

Nous considérons les jeux d'accessibilité à deux joueurs à observation partielle, avec un nombre fini d'états et d'actions.
Les valeurs de ces jeux étant non-calculables, nous nous intéressons à l'existence de stratégies positivement ou presque-sûrement gagnantes pour chacun des joueurs. Nous montrons le résultat de détermination suivant:
- soit le joueur 1 peut gagner presque sûrement,
- soit le joueur 2 peut gagner sûrement,
- soit les deux joueurs peuvent gagner positivement.
La mémoire nécessaire aux joueurs pour implémenter leurs stratégies varie selon les cas: doublement-exponentielle, exponentielle voire sans-mémoire. Du point de vue algorithmique, nous montrons qu'en temps doublement exponentiel, on peut décider dans laquelle de ces trois situations on se trouve, et calculer les stratégies correspondantes des deux joueurs. Ce travail est le fruit d'une collaboration avec Blaise Genest et Nathalie Bertrand de l'IRISA.