Stéphane Durand

En théorie des jeux, les équilibres de Nash sont des points d’intérêt car ce sont les points d'équilibre d'un système, permettant de prédire son comportement ou de mettre en place des situations stables dans lesquelles aucun acteur ne gagne à dévier du choix suggéré. Dans les jeux de grande taille dont le comportement n'est pas soluble analytiquement, échantillonner quelques équilibres permet d'obtenir des informations importantes sur le système. Il existe des algorithmes pour obtenir des équilibres, mais ces algorithmes semblent inefficaces lorsqu'ils sont analysés selon le critère de complexité en pire cas (l'approche classique en informatique consistant à considérer le temps d'exécution le plus long). À l'aide d'un critère de complexité statistique, couplé à une approche analytique utilisant des chaînes de Markov, je vais montrer qu'un de ces algorithmes est en pratique efficace et peut s'appliquer dans des cas plus généraux que ceux auxquels le limite l'approche en pire cas.