Théorie des jeux

Apprendre à jouer : jeu fictif, regret et équilibre corrélé

L'équilibre de Nash suppose des joueurs qui savent déjà comment jouer. Mais comment y arrivent-ils ? Une autre réponse consiste à les faire apprendre, coup après coup, à partir de ce qu'ils ont observé. En 1951, George Brown propose le jeu fictif : chacun suppose que l'autre va continuer à jouer comme il l'a fait jusqu'ici, et répond au mieux. En 2000, Sergiu Hart et Andreu Mas-Colell proposent l'apprentissage par regret : on joue plus souvent ce qu'on regrette de ne pas avoir joué. Cette page fait apprendre des joueurs, montre où mènent ces règles, et finit par un jeu inventé par Lloyd Shapley en 1964, où le jeu fictif tourne en rond pour toujours.

Vocabulaire

Les mots de l'apprentissage

Mot	Sens
Fréquences empiriques	La part des tours où un joueur a joué chaque action jusqu'ici.
Meilleure réponse	L'action qui rapporte le plus face à une croyance sur ce que joue l'autre.
Regret	Ce qu'on aurait gagné en plus, en moyenne, si l'on avait toujours joué une autre action à la place de ses choix passés.
Équilibre corrélé	Une loi de probabilité sur les profils d'actions telle que, si un arbitre tire un profil et souffle à chacun son action, personne n'a intérêt à désobéir (Aumann, 1974).
Convergence	Les fréquences se rapprochent d'un point (ou d'un ensemble) et y restent à mesure que le nombre de tours grandit.

Planche 1

Le jeu fictif : répondre au passé

À chaque tour, chaque joueur compte ce que l'autre a joué jusqu'ici, en déduit des fréquences, et joue sa meilleure réponse comme si l'autre allait continuer ainsi. Le nom vient de l'idée de Brown : un joueur « joue fictivement » contre l'histoire. Julia Robinson démontre en 1951 que, dans tout jeu à somme nulle, les fréquences convergent vers un équilibre de Nash. Dans un jeu de coordination, l'apprentissage se fixe sur une convention. Dans la poule mouillée, les fréquences convergent elles aussi vers l'équilibre… mais les joueurs se ratent à chaque tour.

Le carré des fréquences : en abscisse, part des tours où le joueur 1 a joué sa première action ; en ordonnée, même chose pour le joueur 2. Le point suit l'apprentissage ; la croix marque l'équilibre de Nash mixte. Les traits pointillés séparent les zones où chaque meilleure réponse change.

En haut, les coups joués lors des derniers tours. En bas, la fréquence de la première action de chaque joueur, avec le nombre de tours en échelle logarithmique.

Jeu

Tours joués

—

Fréquences de la première action (joueur 1, joueur 2)

—

Gain moyen obtenu (joueur 1, joueur 2)

—

Contrôle : écart à l'équilibre de Nash

—

Converger n'est pas se coordonner. Dans la poule mouillée, les deux joueurs partent du même coup et raisonnent de la même façon : ils foncent ensemble, puis cèdent ensemble, puis recommencent. Les fréquences tendent vers l'équilibre mixte (foncer un tour sur trois), mais ils ne se croisent jamais comme le voudrait cet équilibre : leurs choix restent parfaitement corrélés, et chacun gagne en moyenne 4 au lieu de 4,67. Les fréquences ne disent pas tout de ce qui se passe.

Planche 2

Apprendre par le regret

Après chaque tour de pierre-feuille-ciseaux, le joueur se demande : « combien aurais-je gagné de plus si j'avais toujours joué pierre ? et feuille ? et ciseaux ? ». Ces regrets cumulés guident le tour suivant : il choisit chaque action avec une probabilité proportionnelle à son regret positif. C'est l'appariement des regrets de Hart et Mas-Colell (2000). Il garantit que le regret moyen tend vers zéro, quel que soit l'adversaire : à long terme, on ne regrette rien. Dans un jeu à somme nulle, les fréquences convergent alors vers l'équilibre (1/3, 1/3, 1/3).

Le triangle des stratégies du joueur 1 : chaque sommet est une action pure, le centre l'équilibre. La trajectoire suit ses fréquences cumulées ; le petit point gris montre sa stratégie du moment, qui continue de tourner.

En haut, les regrets cumulés du joueur 1 pour chaque action (barres) ; seuls les regrets positifs comptent pour le choix suivant. En bas, le plus grand regret moyen par tour, en échelles logarithmiques : il décroît à peu près comme 1/√t (droite grise).

Tours joués

—

Fréquences pierre / feuille / ciseaux

—

Plus grand regret moyen par tour

—

Contrôle : regret moyen × √t reste borné

—

Une règle sans modèle de l'autre. Le joueur qui apprend par le regret n'a besoin ni de connaître les gains de son adversaire, ni de deviner sa stratégie : il suffit de savoir ce que chaque action aurait rapporté. C'est une idée proche du « plus jamais ça » de la vie courante. Sa stratégie du moment ne se stabilise pas : elle tourne autour du centre. Ce sont ses fréquences cumulées qui convergent.

Planche 3

L'équilibre corrélé : le feu de circulation

Dans la poule mouillée, deux conducteurs foncent (F) ou cèdent (C) : s'ils foncent tous deux, accident (0 chacun) ; si l'un cède, il gagne 2 et l'autre 7 ; s'ils cèdent tous deux, 6 chacun. Robert Aumann (1974) imagine un arbitre, comme un feu de circulation, qui tire au sort une recommandation pour chacun. Si personne n'a intérêt à désobéir à sa recommandation, la loi de tirage est un équilibre corrélé. Avec un tiers de chances pour (C, C), (C, F) et (F, C), chacun gagne 5, plus que les 4,67 de l'équilibre de Nash mixte. Hart et Mas-Colell montrent qu'avec le regret conditionnel (« j'aurais dû jouer B chaque fois que j'ai joué A »), les fréquences des profils joués convergent vers l'ensemble des équilibres corrélés.

Le plan des gains : en bleu, tous les gains moyens des équilibres corrélés ; les points marquent les équilibres de Nash. Le point noir est la loi choisie avec les curseurs, vert si c'est un équilibre corrélé, rouge sinon. En orange, les gains moyens d'un apprentissage par regret conditionnel.

En haut, les quatre contraintes de l'arbitre : le gain d'obéir moins le gain de désobéir, pour chaque joueur et chaque recommandation (elles doivent toutes être positives). En bas, la plus grande violation au fil de l'apprentissage, qui tombe à zéro.

Probabilité de (C, C) en %

Probabilité de (C, F) en %

Probabilité de (F, C) en %

Loi choisie : (C, C) / (C, F) / (F, C) / (F, F)

—

Gains moyens (joueur 1, joueur 2)

—

Est-ce un équilibre corrélé ?

—

Contrôle : l'apprentissage finit dans l'ensemble des équilibres corrélés

—

Mieux que Nash, grâce à un signal. L'arbitre ne force personne : il donne seulement une information. Celui à qui l'on dit « foncez » sait que l'autre cède, et n'a donc aucune raison de céder. Celui à qui l'on dit « cédez » sait que l'autre cède ou fonce avec des chances égales : céder lui rapporte en moyenne 4, foncer 3,5. Le meilleur équilibre corrélé symétrique donne 5,25 à chacun. L'apprentissage par regret, lui, ne choisit pas : il garantit seulement d'arriver dans l'ensemble, et dans la poule mouillée il se fixe souvent sur un équilibre pur, où l'un cède toujours.

Planche 4

La course des apprentis à pierre-feuille-ciseaux

Dans pierre-feuille-ciseaux, jeu à somme nulle, les deux règles d'apprentissage finissent à l'équilibre, mais par des chemins très différents. Le jeu fictif est déterministe : chaque joueur garde la même action pendant des séquences de plus en plus longues, et ses fréquences tournent en spirale vers le centre. L'appariement des regrets est aléatoire et ses fréquences approchent le centre en tremblant. La page fait jouer les deux, face à elles-mêmes, et mesure leur distance à l'équilibre.

Les fréquences du joueur 1 dans le triangle des stratégies : jeu fictif en bleu, appariement des regrets en orange.

Distance à l'équilibre (plus grand écart d'une fréquence à 1/3) selon le nombre de tours, en échelles logarithmiques. La droite grise a la pente de 1/√t.

Tours joués

—

Distance du jeu fictif

—

Distance du regret

—

Contrôle : la dernière séquence du jeu fictif est la plus longue

—

Le théorème de Robinson. Julia Robinson a démontré en 1951 la convergence du jeu fictif pour tous les jeux à somme nulle ; c'est l'un des premiers résultats sur l'apprentissage dans les jeux. Sa preuve ne dit rien de la vitesse, et l'on sait aujourd'hui que, dans certains jeux, la convergence peut être très lente. Hors de la somme nulle, rien n'est garanti : c'est ce que montre la planche suivante.

Signature

Le jeu de Shapley : le jeu fictif ne converge pas

En 1964, Lloyd Shapley construit un jeu à trois actions, proche de pierre-feuille-ciseaux mais sans somme nulle. Le joueur 1 gagne 1 s'il joue la même action que le joueur 2 ; le joueur 2 gagne 1 s'il joue l'action « suivante » (1 contre 2, 2 contre 3, 3 contre 1). Le seul équilibre de Nash est que chacun joue au hasard, un tiers par action. Pourtant, le jeu fictif ne s'en approche jamais : les joueurs parcourent sans fin un cycle de six profils, et chaque étape dure environ 1,47 fois plus longtemps que la précédente. Les fréquences tournent sur un triangle, le « triangle de Shapley », sans jamais rejoindre le centre.

Les fréquences du joueur 1 dans le triangle des stratégies. Jeu fictif en bleu : la trajectoire tourne sans se rapprocher du centre (l'équilibre). Regret conditionnel en orange, si on le lance.

En haut, la durée de chaque séquence pendant laquelle les deux joueurs gardent les mêmes actions, en échelle logarithmique : une droite signifie une croissance géométrique. En bas, la violation des contraintes d'équilibre corrélé au fil des tours, pour les deux règles.

Tours joués

—

Séquences du cycle / rapport entre deux séquences

—

Distance à l'équilibre : jeu fictif / regret conditionnel

—

Contrôle : violation corrélée, jeu fictif / regret conditionnel

—

Apprendre n'est pas trouver Nash. L'exemple de Shapley a montré que le jeu fictif ne mène pas toujours à l'équilibre de Nash. Hart et Mas-Colell ont montré en 2003 qu'aucune règle « découplée », où chacun n'utilise que ses propres gains, ne garantit d'y arriver dans tous les jeux. L'équilibre corrélé, en revanche, s'apprend : le regret conditionnel y conduit toujours. Dans le jeu de Shapley, nos essais le mènent à des lois corrélées où chacun gagne en moyenne plus que le 1/3 de l'équilibre de Nash. L'équilibre corrélé apparaît ainsi comme le point d'arrivée naturel de l'apprentissage.

Synthèse

Ce qu'il faut retenir

Le jeu fictif

Répondre au mieux aux fréquences passées de l'autre. Converge dans les jeux à somme nulle (Robinson, 1951), pas toujours ailleurs (Shapley, 1964).

Le regret

Jouer davantage ce qu'on regrette de ne pas avoir joué : le regret moyen tend vers zéro, quel que soit l'adversaire.

L'équilibre corrélé

Avec le regret conditionnel, les fréquences des profils joués convergent vers l'ensemble des équilibres corrélés, dans tous les jeux finis.

Pour aller plus loin

Les conventions de la page. Jeu fictif : les deux joueurs mettent à jour en même temps ; en cas d'égalité, un joueur garde son action précédente si elle fait partie des meilleures, sinon il prend la première. Regret conditionnel : après avoir joué j, le joueur passe à k avec une probabilité égale à son regret conditionnel positif divisé par μ fois le nombre de tours, μ étant choisi assez grand (Hart et Mas-Colell, 2000). Les distances sont mesurées par le plus grand écart d'une fréquence à sa valeur d'équilibre ; la violation corrélée est le plus grand gain moyen qu'un joueur obtiendrait en remplaçant systématiquement une action par une autre.

Références. G. W. Brown, « Iterative solution of games by fictitious play » (1951) ; J. Robinson, « An iterative method of solving a game » (1951) ; L. S. Shapley, « Some topics in two-person games » (1964) ; R. Aumann, « Subjectivity and correlation in randomized strategies » (1974) ; S. Hart et A. Mas-Colell, « A simple adaptive procedure leading to correlated equilibrium » (2000) et « Uncoupled dynamics do not lead to Nash equilibrium » (2003) ; D. Fudenberg et D. Levine, The Theory of Learning in Games (1998).

Pages voisines. Les jeux répétés et le folk theorem, l'équilibre de Nash, le dilemme du prisonnier.