L’équilibre de Nash : pourquoi personne ne veut bouger le premier

Théorie des jeux, partie 5 sur 9

Princeton, 1949. John Nash, doctorant de 21 ans, obtient un rendez-vous avec John von Neumann, l’un des mathématiciens les plus célèbres du monde et l’auteur du théorème du minimax. Nash veut lui montrer une idée sur laquelle il travaille.

D’après sa biographe, Sylvia Nasar, von Neumann l’a interrompu presque aussitôt : « C’est trivial, vous savez. Ce n’est qu’un théorème du point fixe. »

Nash n’a pas abandonné l’idée. En novembre 1949, sa courte note est transmise à la revue Proceedings of the National Academy of Sciences. Elle tient sur deux pages. En 1950, Nash soutient une thèse de doctorat sur le même sujet, et en 1994 elle lui vaut le prix Nobel d’économie, partagé avec John Harsanyi et Reinhard Selten.

Que contenait donc cette idée « triviale » ?

Une seule question

On vérifie un équilibre de Nash avec une seule question, posée tour à tour à chaque joueur :

« Sachant ce qu’ont fait les autres, changeriez-vous votre choix ? »

Si personne ne veut changer seul son choix, c’est un équilibre. Si un seul joueur le veut, ce n’en est pas un.

Posons cette question au tableau du volet précédent, celui des deux prisonniers.

Les deux se taisent. Quelqu’un veut-il changer ? Oui : si votre complice se tait, avouer vous rend la liberté au lieu d’un an. Pas d’équilibre.

Les deux avouent. Quelqu’un veut-il changer ? Non : si votre complice a avoué, vous taire vous coûterait dix ans au lieu de cinq. C’est un équilibre.

Voici l’essentiel à retenir : un équilibre n’est pas le meilleur résultat. Un an chacun vaut mieux que cinq. Mais tout le monde veut fuir le « meilleur » résultat, et personne ne veut quitter le mauvais. Un équilibre ne décrit pas ce qui est bon, mais ce qui est stable.

Pour tout tableau à deux joueurs, il existe une manière rapide de trouver les équilibres sans longs raisonnements. Parcourez chaque colonne et marquez la case où votre résultat est le meilleur : c’est votre meilleure réponse à ce coup de l’adversaire. Puis parcourez chaque ligne et marquez la case la meilleure pour l’adversaire.

Les cases marquées deux fois sont les équilibres. S’il n’y en a aucune, l’équilibre n’existe qu’avec des coups joués au hasard — mais nous y reviendrons.

Ce que Nash a démontré

Dans le troisième volet, nous avons vu le théorème de von Neumann : un jeu à somme nulle entre deux joueurs a une valeur. Mais la plupart des situations réelles sont différentes : il y a souvent plus de deux joueurs, et leurs intérêts ne sont pas toujours opposés.

Nash a démontré qu’un équilibre existe dans tout jeu fini, quel que soit le nombre de joueurs et quels que soient les gains. Une condition : il faut parfois que les joueurs choisissent leurs coups au hasard, selon certaines probabilités, comme à pierre-feuille-ciseaux. Ces stratégies mixtes feront l’objet du septième volet.

Pour les échecs, rien ne change. Dans les jeux à somme nulle, un équilibre de Nash est la même chose que le minimax : aucun camp ne peut améliorer le résultat en changeant seulement son propre jeu. Le « jeu parfait » du deuxième volet de la série est donc lui aussi un équilibre de Nash.

Quand il y en a plusieurs

Voici un jeu auquel des millions de personnes jouent chaque jour. Deux conducteurs roulent l’un vers l’autre. Chacun choisit de quel côté de la route se tenir (gains indicatifs) :

Il y a ici deux équilibres : « les deux à gauche » et « les deux à droite ». Aucun n’est meilleur que l’autre. Seul compte que tout le monde choisisse la même chose.

Mais sortir de l’équilibre dans lequel tout le monde se trouve est très difficile. Un conducteur qui déciderait d’être le premier à rouler à droite dans un pays où l’on roule à gauche ne changerait rien — sauf à provoquer un accident.

C’était précisément le piège de la Suède. Le pays roulait à gauche, alors que ses voisins nordiques et la majeure partie de l’Europe continentale roulaient à droite. Lors d’un référendum en 1955, 82,9 % des votants ont rejeté le changement. Le Parlement a pourtant adopté la réforme en 1963.

Le basculement a été fixé au dimanche 3 septembre 1967. À 4 h 50, toute la circulation s’est arrêtée. À 5 h, elle a repris — à droite.

En termes de théorie des jeux, c’était le passage d’un équilibre à un autre. Personne ne l’aurait fait seul. Il a donc fallu changer le comportement de tout le monde, en même temps.

Comment on choisit un équilibre

S’il existe plusieurs équilibres, comment les joueurs s’accordent-ils sur l’un d’eux sans se parler ?

Dans un livre de 1960, l’économiste Thomas Schelling décrit une question qu’il posait à ses étudiants : vous devez retrouver un inconnu à New York, mais vous n’avez convenu ni d’un lieu ni d’une heure. Où et quand allez-vous ? Réponse la plus fréquente : à midi, au guichet d’information de la gare Grand Central.

En théorie, n’importe quel lieu et n’importe quelle heure sont un équilibre : si vous y allez tous les deux, aucun n’a intérêt à aller ailleurs. Mais les gens choisissent ce qui ressort, ce que chacun s’attend à ce que les autres attendent. Schelling a appelé cela un point focal. Dans le jeu de la route, le point focal, c’est l’habitude, la loi ou ce que font les voisins.

L’erreur d’Un homme d’exception

Dans le film Un homme d’exception (A Beautiful Mind, 2001), une scène montre le jeune Nash qui découvrirait son idée. Une bande d’amis est assise dans un bar. Tous ont remarqué la même jeune femme et s’apprêtent à l’aborder.

Nash explique : s’ils vont tous vers elle, ils se gêneront mutuellement. Et ensuite, ses amies les éconduiront aussi, car personne n’aime être un second choix. Donc personne ne doit l’aborder, et tous doivent aller vers ses amies.

La scène est réussie, mais ce n’est pas un équilibre de Nash. Posons notre question. Tous sont allés vers les amies.

Quelqu’un veut-il changer ? Oui : chacun, seul, préférerait maintenant aborder la jeune femme que personne n’a abordée. Le plan ne tient que grâce à un accord.

L’équilibre de cette histoire est autre : un seul d’entre eux l’aborde, et les autres vont vers ses amies. Alors personne n’a intérêt à changer son choix. Le mathématicien José-Manuel Rey l’a souligné dès 2008 dans le magazine Plus.

L’ironie, c’est que la scène du film montre plutôt un accord collectif. Or ce sont justement ces accords — les coalitions — que Nash a délibérément écartés dans son article de 1951. Sa théorie porte sur des joueurs qui décident chacun pour soi.

Ce qu’il faut en retenir

La question de Nash est utile bien au-delà des tableaux.

• Stable ne veut pas dire bon. Si tout le monde est mal loti mais que personne ne change de comportement, vous avez sans doute affaire à un mauvais équilibre. Dire à une seule personne de « simplement faire autrement » ne suffit pas : seule, elle n’y a pas intérêt.
• On sort d’un équilibre ensemble. Comme en Suède, il faut un changement de règles, un accord ou un signal commun à partir duquel le nouveau comportement profite à chacun.
• Quand il y a plusieurs équilibres, ce que tout le monde remarque décide. L’habitude, la tradition, un repère évident. Qui fixe le point focal décide souvent où le groupe aboutira.

Devant l’échiquier, la même question est la base de l’analyse d’une partie. En la repassant, vérifiez : sachant comment l’adversaire a répondu, changeriez-vous votre coup ? Les coups pour lesquels la réponse est « oui » sont les endroits où votre jeu n’était pas un équilibre.

Exercice

1. Deux amis ont prévu de passer la soirée ensemble, mais ne peuvent plus se joindre. L’un préférerait aller au cinéma, l’autre à un concert. Mais tous deux veulent avant tout être ensemble. Gains : les deux au cinéma — 2 et 1 ; les deux au concert — 1 et 2 ; à des endroits différents — 0 et 0. Trouvez tous les équilibres.
2. Revenons à la scène du film. Est-ce un équilibre si deux des amis abordent la même jeune femme ?

Les réponses sont à la fin.

Questions pour la discussion

• Citez un mauvais équilibre de votre vie ou de votre travail dont personne ne veut sortir le premier. Quel pourrait être son « Dagen H », le jour du basculement suédois ?
• Un point focal vous a-t-il déjà aidé à retrouver quelqu’un ou à vous accorder sans un mot ?
• Von Neumann a jugé triviale l’idée de Nash. Une de vos idées « évidentes » s’est-elle déjà révélée précieuse pour d’autres ?

Prochainement dans la série : « Œil pour œil, mais avec pardon », sur les tournois de Robert Axelrod, où des programmes informatiques ont joué encore et encore au dilemme du prisonnier — et sur la stratégie qui l’a emporté.

Réponses. 1) Il y a deux équilibres : les deux au cinéma et les deux au concert. Dans les deux cas, celui qui irait seul ailleurs obtiendrait 0 au lieu de 1 ou 2. Il existe aussi un troisième équilibre, mixte, où chacun choisit au hasard. Nous y reviendrons dans le septième volet. 2) Non. Tous les deux essuient un refus, parce qu’ils se gênent. Chacun d’eux aurait donc intérêt à aller vers les amies. L’équilibre, c’est qu’un seul l’aborde.

Discutez-en ci-dessous