Jeux Stochastiques à Deux Joueurs à Information Parfaite et Zéro

Abstract

On considère des jeux stochastiques joués sur un graphe fini. La première partie s’intéresse aux jeux stochastiques à deux joueurs et information parfaite. Dans de tels jeux, les joueurs choisissent des actions dans ensemble fini, tour à tour, pour une durée infinie, produisant une histoire infinie. Le but du jeu est donné par une fonction d’utilité qui associe un réel à chaque histoire, la fonction est bornée et Borel-mesurable. Le premier joueur veut maximiser l’utilité espérée, et le deuxième joueur veut la minimiser. On démontre que si la fonction d’utilité est à la fois shift-invariant et submixing alors le jeu est semi-positionnel. C’est-à-dire le premier joueur a une stratégie optimale qui est déterministe et sans mémoire. Les deux joueurs ont information parfaite: ils choisissent leurs actions en ayant une connaissance parfaite de toute l’histoire. Dans la deuxième partie, on étudie des jeux de durée fini où le joueur protagoniste a zéro information. C’est-à-dire qu’il ne reçoit aucune information sur le déroulement du jeu, par conséquent sa stratégie est un mot fini sur l’ensemble des actions. Un automates probabiliste peut être considéré comme un tel jeu qui a un seul joueur. Tout d’abord, on compare deux classes d’automates probabilistes pour lesquelles le problème de valeur 1 est décidable: les automates leaktight et les automates simples. On prouve que la classe des automates simples est un sous-ensemble strict de la classe des automates leaktight. Puis, on considère des jeux semi-aveugles, qui sont des jeux à deux joueurs où le maximiseur a zéro information, et le minimiseur est parfaitement informé. On définit la classe des jeux semi-aveugles leaktight et on montre que le problème d’accessibilité maxmin est décidable sur cette classe.