Fictious Play

From LRDE

Abstract

Le fictitious play, en théorie des jeux, est une règle d'apprentissage dans laquelle chaque joueur suppose que ses adversaires jouent une stratégie fixe (potentiellement mixte, c'est-à-dire une distribution de probabilité sur un ensemble de stratégies). À chaque tour, chaque joueur joue ainsi le meilleur coup contre la stratégie de ses adversaires, déterminée de manière empirique à partir de leurs coups précédents. La convergence de telles stratégies n'est pas assurée, mais on sait que si il y a convergence, alors les stratégies jouées correspondront statistiquement à un équilibre de Nash. Il est donc très intéressant de connaître les critères de convergence. Nous nous intéresserons pour cette présentation au cas des jeux où les fonctions d'utilité (le gain d'un joueur en fonction des stratégies jouées) de chaque joueur sont identiques. Nous étudierons d'abord des résultats de convergence dans ce cas particulier. Afin de réduire la complexité en temps, nous verrons une variante de cet algorithme, qui consiste à autoriser une erreur dans la meilleure réponse des joueurs. Nous présenterons enfin un exemple d'application du fictitious play pour résoudre un problème a priori non lié à la théorie des jeux : un problème d'optimisation, c'est-à-dire calculer le maximum des valeurs prises par une fonction.