L'équilibre corrélé : quand un conseil change le jeu

Chaque conducteur peut passer ou s'arrêter. Passer seul rapporte 1 (du temps gagné), s'arrêter 0, et si les deux passent, l'accident coûte c à chacun. Sans aide, il y a trois équilibres de Nash : l'un passe toujours et l'autre s'arrête toujours (deux équilibres injustes), ou chacun passe au hasard avec une probabilité 1/(1 + c), ce qui provoque des accidents et ne rapporte rien en moyenne. Le feu tire au sort qui a le vert : celui qui a le vert sait que l'autre a le rouge et passe ; celui qui a le rouge sait que l'autre passe et s'arrête. Personne n'a intérêt à désobéir, et chacun gagne 1/2 en moyenne, sans aucun accident.

Deux conducteurs foncent l'un vers l'autre : chacun peut foncer (F) ou céder (C). Si les deux foncent, accident (0 chacun) ; si l'un cède, il gagne 2 et l'autre 7 ; si les deux cèdent, 6 chacun. Les équilibres de Nash donnent (7, 2), (2, 7) ou, en mélangeant, 4,67 chacun. Un signal public, comme une pièce lancée devant les deux, ne peut que tirer au sort entre ces équilibres : ses gains restent dans le triangle violet. Aumann remarque qu'avec des conseils privés on peut faire mieux : si le médiateur tire (C, C), (C, F) et (F, C) avec un tiers de chances chacun, celui à qui l'on dit « céder » ne sait pas si l'autre cède ou fonce, et céder reste son meilleur choix. Chacun gagne alors 5.

Regardons le médiateur à l'œuvre dans la poule mouillée. À chaque partie, il tire un profil selon sa loi, glisse à chaque joueur une enveloppe qui ne contient que son action, et les joueurs jouent. Le joueur 2 obéit toujours. Le joueur 1 peut obéir, ou essayer de tricher : foncer quoi qu'on lui dise, foncer quand on lui dit de céder, ou céder quand on lui dit de foncer. Si la loi est un équilibre corrélé, aucune triche ne lui rapporte plus que l'obéissance.

Les contraintes d'obéissance sont des inégalités linéaires en les probabilités de la loi. L'ensemble des équilibres corrélés est donc un polyèdre, et chercher le meilleur conseil, par exemple celui qui maximise une moyenne pondérée des gains, est un programme linéaire, que l'algorithme du simplexe résout en quelques étapes. C'est un grand avantage sur les équilibres de Nash, beaucoup plus difficiles à calculer. En faisant tourner la direction à maximiser, on dessine toute la région des gains corrélés. Selon le jeu, elle peut être bien plus grande que l'enveloppe des équilibres de Nash, ou se réduire à elle.

Dans la poule mouillée, le meilleur conseil donne 5,25 à chacun, mais l'équilibre de Nash (7, 2) reste meilleur pour le joueur 1. Peut-on faire mieux pour les deux joueurs que tous les équilibres de Nash ? Oui. Dans ce jeu à trois actions, proposé par Hervé Moulin et Jean-Philippe Vial en 1978, les deux joueurs veulent surtout ne pas jouer la même action (gain nul pour les deux). Le seul équilibre de Nash est de jouer chaque action au hasard, ce qui rapporte 1 à chacun. Un médiateur qui tire au hasard une des six cases hors de la diagonale donne 1,5 à chacun, et personne n'a intérêt à désobéir.