Antoine Leblanc. Efficiency comparison between Fictitious Play and Alternate Fictitious Play algorithms on the restricted set of zero-sum games. CSI Seminar 0837 January 2009

English:

The Fictitious Play algorithm is an iterate learning process created to compute Nash equilibria. At each iteration of this algorithm, each of the players "strengthens" the strategy that has the highest utility in the current context. For some specific game classes this algorithm converges to a Nash equilibrium, therefore providing an efficient approximation method. However, convergence can only be proved for a small amount of game classes.

The Alternate Fictitious Play algorithm (introduced last year) is a variant in which only one player at a time strengthens one of his strategies : the player which is the "further" from his maximum payoff.

This study will focus on a comparison of these two approaches on the restricted set of zero-sum games. It will also present the notions of game classification used for this comparison.

Français:

L'algorithme du Fictitious Play est un procédé d'apprentissage itéré utilisé dans le cadre de la recherche des équilibres de Nash. Son principe est simple : à chaque itération, chacun des joueurs "renforce" celle de ses stratégies pures qui est la plus efficace face à ses adversaires. Pour certains jeux, cet algorithme converge vers un équilibre de Nash, fournissant ainsi un algorithme d'approximation efficace. La convergence ne peut toutefois être prouvée que pour un nombre limité de cas.

L'algorithme du Fictitious Play Alterné (présenté l'année dernière) en est une variante dans lequel seul le joueur le plus "éloigné" de son gain optimal renforce sa stratégie la plus efficace.

Cette étude se focalisera sur une comparaison de l'efficacité de ces deux algorithmes dans le cadre des jeux à somme nulle et abordera également les notions de classification des jeux nécessaires à la réalisation de cet objectif.
to top