Calculer tous les équilibres de Nash d'un jeu 3 × 3

Une stratégie mixte de Ligne est un point du triangle de gauche : plus le point est proche d'un sommet, plus la stratégie correspondante est jouée souvent. Chaque point du triangle est colorié selon la meilleure réponse de l'adversaire à ce mélange. À droite, même chose pour Colonne. On attache à chaque point des étiquettes numérotées de 1 à 6 : les étiquettes 1, 2, 3 désignent Haut, Milieu, Bas, et 4, 5, 6 désignent Gauche, Centre, Droite. Un point de Ligne porte l'étiquette d'une de ses stratégies s'il ne la joue pas (il est sur le côté opposé au sommet), et l'étiquette d'une stratégie de Colonne si celle-ci est une meilleure réponse (il est dans la zone de cette couleur). Le critère d'équilibre devient alors visuel : un couple de points est un équilibre exactement quand, à eux deux, ils portent les six étiquettes.

Chaque joueur a 7 supports possibles : trois stratégies seules, trois paires, et le trio. Cela fait 7 × 7 = 49 combinaisons. Pour chacune, on applique le principe d'indifférence : si Ligne mélange plusieurs stratégies, c'est qu'elles lui rapportent autant ; on écrit donc que le mélange de Colonne rend ces stratégies de Ligne également rentables, ce qui donne un système d'équations, et inversement. On résout, puis on vérifie trois choses : les probabilités sont positives, aucune stratégie hors du support ne rapporte davantage, et le système avait une solution.

Un jeu est dégénéré quand un mélange de k stratégies admet plus de k meilleures réponses : par exemple, une stratégie pure à laquelle l'adversaire a deux réponses également bonnes. Cela arrive dès que deux gains sont égaux au mauvais endroit, ce qui est fréquent avec des petits nombres entiers. Alors des équilibres peuvent former un segment entier, et leur nombre peut devenir pair. La page trouve ici les équilibres « extrêmes » (les sommets) et relie ceux qui forment un ensemble continu. Le curseur ajoute ensuite à tous les gains une petite perturbation au hasard, multipliée par ε.

L'argument tient en une image. Ajoutons aux équilibres un point fictif, le point artificiel : « personne ne joue rien » (x = 0, y = 0). Il porte lui aussi les six étiquettes — 1, 2, 3 parce que Ligne ne joue aucune ligne, 4, 5, 6 parce que Colonne ne joue aucune colonne — mais ce n'est pas un vrai couple de stratégies. Choisissons une étiquette, disons 2, et acceptons de la perdre : à partir de chacun de ces points, il part un unique chemin le long duquel il manque exactement l'étiquette 2 (c'est l'algorithme de la planche 5). Ce chemin ne peut s'arrêter que sur un autre point portant les six étiquettes. Les points se rangent donc par paires, reliées par des chemins. Puisque le point artificiel est dans une paire, il reste un nombre impair de vrais équilibres.

Et sur des milliers de jeux ?

Tirons des jeux 3 × 3 dont les gains sont des nombres réels au hasard entre 0 et 10 (ils sont alors non dégénérés presque sûrement) et comptons leurs équilibres.

En 1964, Carlton Lemke et Joseph Howson donnent la première méthode qui trouve à coup sûr un équilibre d'un jeu à deux joueurs. Partons du point artificiel, qui a toutes les étiquettes, et décidons d'en lâcher une, par exemple l'étiquette 1 (Haut). Ligne se met à jouer Haut : son point quitte le côté 1 et file vers le sommet Haut. Il s'arrête dès qu'il gagne une nouvelle étiquette — mais celle-ci, l'autre joueur l'avait déjà : elle est maintenant en double. C'est donc à l'autre joueur de bouger pour s'en débarrasser, jusqu'à gagner une nouvelle étiquette, et ainsi de suite. À chaque pas, une seule étiquette manque (celle lâchée au départ) et une seule est en double. Le jeu de relais s'arrête quand l'étiquette gagnée est justement celle qui manquait : les six sont réunies, c'est un équilibre.