École Nationale Supérieure de
Techniques Avancées

Résumé

Ce stage a eu pour objet de développer un algorithme décentralisé de planification dans un jeu stochastique fini non escompté à horizon fini à deux joueurs, problématique non encore traitée dans la littérature. L'objectif de cet algorithme est de coordonner deux agents sur un équilibre de Nash du jeu stochastique, non dominé au sens de Pareto par aucun autre équilibre de Nash du jeu. Un équilibre de Nash est un but souvent recherché dans le cas non coopératif car il contente les deux agents dans le sens où aucun des deux n'a intérêt à dévier de sa politique. Le non dominé au sens de Pareto permet d'assurer que les agents ne peuvent pas profiter tous les deux d'un choix d'un autre équilibre de Nash. Dans ce rapport sera présenté le test d'un algorithme de planification centralisé existant sur le- quel notre travail se base (section 4). L'algorithme sera ensuite modifie en vue de calculer tous les équilibres de Nash non dominés au sens de Pareto par un autre équilibre de Nash (section 5), ceci étant une phase préliminaire à de la communication entre les deux agents servant à les coordonner sur le même équilibre. Deux méthodes basées sur la technique de montée de gradient (section 6) seront expérimentées. Les deux méthodes précédentes ont été mise en commun afin d'obtenir le résultat final, à savoir un algorithme de planification décentralisé dans les jeux stochastiques finis non escomptés à deux joueurs à horizon fini (section 7).