Étude et implémentation du Fictitious Play alterné

Auteurs

Antoine Leblanc

Type

techreport

Année

2008

Numéro

0826

Résumé

Le calcul d'un équilibre de Nash dans un jeu fini est un problème démontré PPAD-complet, ce qui signifie qu'il paraît impossible de trouver une méthode de calcul efficace ; la complexité en pire cas des algorithmes usuels est 2^O(n) pour un jeu de taille n . La recherche en ce domaine s'oriente donc vers le calcul d'équilibres approchés, à savoir des situations vérifiant les conditions d'un équilibre de Nash à ɛ près. L'algorithme du emphFictitious Play s'inscrit dans cette démarche de recherche. 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. Pour cette raison, il est intéressant d'étudier d'autres algorithmes basés sur le Fictitious Play, afin de trouver d'autres cas de convergence. Nous allons étudier ici le Fictitious Play alterné, dans lequel seul le joueur le plus “éloigné” de son gain optimal renforce sa stratégie la plus efficace.