Équilibre de Nash

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Le dilemme du prisonnier : chacun des deux joueurs a deux actions (C pour coopérer, D pour dénoncer). La matrice présente le gain des joueurs. Si les deux joueurs jouent D, aucun n'a intérêt à changer son choix car il deviendrait plus triste. C'est un équilibre de Nash.

En théorie des jeux, un équilibre de Nash est une situation où :

  1. Chaque joueur prévoit correctement le choix des autres
  2. Chaque joueur maximise son gain, compte tenu de cette prévision.

L'équilibre de Nash est donc tel qu'aucun joueur ne regrette son choix (il n'aurait pas pu faire mieux) au vu du choix des autres, les choix étant, comme toujours en théorie des jeux, simultanés[1].

Souvent l'équilibre de Nash est présenté comme une situation où chacun adopte la meilleure réponse "compte tenu" du choix des autres, ce qui peut laisser croire que ce choix est connu - alors qu'il n'en est rien, pour des raisons évidentes.

Les prévisions des joueurs sur ce que vont faire les autres sont donc un élément essentiel de l'équilibre de Nash. Elles en sont aussi le principal point faible, ces prévisions - élément essentiellement subjectif - n'ayant généralement pas de raison d'être correctes, comme c'est le cas dans les modèles du duopole de Cournot et de Bertrand.

L'équilibre de Nash peut donc être considéré comme une "solution" d'un jeu, au sens mathématique (résolution d'un système d'équations), sans en être une si on entend par "solution" une prédiction de ce que feront les joueurs placés dans la situation décrite par le jeu.

L'équilibre de Nash a été nommé d'après le mathématicien John Forbes Nash. Il lui a valu le « Prix Nobel » d'économie en 1994.

Description de la notion[modifier | modifier le code]

Un jeu est constitué d'individus, appelés "joueurs", qui doivent choisir un élément - appelé "stratégie" - dans un ensemble qui est donné par les règles du jeu. Celles-ci précisent aussi quel est les gain, en monnaie ou en "utilité", obtenu par chaque joueur dans toutes les éventualités possibles - pour toutes les "combinaisons de stratégies" envisageables. Si on note Si l'ensemble des stratégies du joueur i, alors une combinaison de stratégies est donnée par un élément de S1 x ... x Sm, où m est le nombre de joueur, les gains des joueurs qui lui sont associés sont donnés par un vecteurs de m nombres.

L'équilibre de Nash est un point fixe d'un processus où les joueurs, pris successivement, maximisent leur gain après avoir "observé" celui de leur prédécesseur - le "premier", quel qu'il soit, faisant d'abord son choix au hasard, puis quand son tour vient à nouveau, le fait après avoir observé celui du dernier de la "chaîne". Il y a point fixe, équilibre, quand le "premier", puis ceux qui le suivent, ne modifient pas leur choix au vu de celui fait par leur "prédécesseur".

Nash a démontré que sous certaines conditions - notamment en admettant l'existence de stratégies mixtes- tout jeu comportant un nombre fini de joueurs a au moins un point fixe, qu'il appelle "équilibre".

Théorème d'existence[modifier | modifier le code]

Théorème de Nash — Soit un jeu discret[à définir] est le nombre de joueurs et est l'ensemble des possibilités pour le joueur , et soit l'extension de aux stratégies mixtes. Alors le jeu admet au moins un point d'équilibre[à définir].

Explication[modifier | modifier le code]

Par exemple, le jeu pierre-papier-ciseaux n'admet pas d'équilibre avec des stratégies pures[2] (si on choisit à toutes les parties « pierre » par exemple, l'autre personne augmentera son gain (la fonction ) en choisissant « feuille ». Mais alors le premier joueur choisira ensuite « ciseau », etc. On n'arrivera jamais à un équilibre). En revanche, si on étend ce jeu aux stratégies mixtes, il y a un point d'équilibre d'après le théorème de Nash[3] (et on peut montrer qu'il est unique). Ce point est donné en choisissant 13 « pierre » + 13 « ciseau » + 13 « papier », c'est-à-dire, du point de vue probabiliste, de jouer l'une des trois possibilités, chacune avec une probabilité 13.

Optimalité[modifier | modifier le code]

L'existence d'un équilibre n'implique pas que celui-ci soit nécessairement optimal. Il peut en effet exister d'autres choix des joueurs qui conduisent, pour chacun, à un gain supérieur.

Ces choix peuvent, ou non, correspondre à un autre équilibre (le théorème de Nash dit qu'il existe au moins un équilibre, mais pas qu'il est unique).

Considérons, par exemple, un jeu où deux joueurs choisissent simultanément un nombre de 2 à 12. Le joueur qui a annoncé le plus petit nombre le remporte, l'autre joueur gagne la même chose moins deux. En cas d'égalité, les deux joueurs remportent leur nombre et subissent une pénalité de deux.

Les seuls équilibres de Nash de ce jeu sont quand les deux annoncent 2, ou quand l'un annonce 2 et l'autre 3. Dans le choix (2,2) si quelqu'un change il n'aura pas mieux que 0 de toute façon. Dans (2,3) si celui qui a choisi 3 change il n'aura pas mieux que 0, si celui qui a choisi 2 change il aura 1 au lieu de 2, donc ce sont des équilibres de Nash. Dans toutes les autres paires de stratégies si le plus petit est 3 ou plus, le joueur qui annonce plus ou autant peut améliorer son résultat en déclarant le plus petit moins un. Si le plus petit est 2 et l'autre est 4 ou plus, le joueur qui a choisi le plus petit peut améliorer son score en choisissant le plus grand moins un. Cependant, il est clair que le choix (12,12), rapportant 10 à chaque joueur, est bien meilleur pour les deux que les équilibres précédents.

D'autres exemples célèbres sont ceux du problème des marchands de glaces ou du dilemme du prisonnier.

Les exemples d'équilibre non-optimaux sont parfois évoqués pour montrer que si chaque acteur économique raisonne individuellement selon son intérêt, alors il peut en résulter une situation pire que si les acteurs se concertaient[4].

Unicité[modifier | modifier le code]

Tout jeu peut avoir de nombreux équilibres de Nash ou aucun (c'est le cas du jeu consistant à écrire simultanément un entier, le gagnant étant celui dont l'entier est le plus grand). Néanmoins, Nash est parvenu à démontrer que tout jeu avec un nombre fini de joueurs ayant un nombre fini de stratégies admet au moins un équilibre de Nash en stratégie mixte (c'est-à-dire si l'on considère comme une stratégie possible de tirer aléatoirement (avec des probabilités fixées) entre plusieurs stratégies).

Dans le cas d'un jeu à somme nulle à deux joueurs, c'est-à-dire où ce que gagne un joueur est nécessairement perdu par l'autre, ce résultat (c’est-à-dire l'utilité induite par tout équilibre) est nécessairement unique. Il a conduit à définir la valeur d'un jeu.

Équilibre évolutionnaire stable[modifier | modifier le code]

Les applications des jeux répétés et en particulier l'isolement d'un comportement altruiste optimal dans des cas particuliers de dilemme du prisonnier ont intéressé les biologistes. Ce résultat a permis de combler un trou conceptuel dans l'évolutionnisme, qui paraissait privilégier l'égoïsme.

Les théoriciens ont donc défini une forme plus exigeante d'équilibre pour des modèles répétés : un équilibre évolutionnaire stable reste stable même en cas de comportement légèrement perturbé. Cette stabilité vise à couvrir les situations d'apparition de nouveaux comportements dans une population, c'est-à-dire de dépasser l'immobilisme présumé par Nash.

Aspects calculatoires[modifier | modifier le code]

La théorie algorithmique des jeux étudie notamment les aspects calculatoires et quantitatifs des équilibres de Nash : sont-ils facile à calculer ou à approcher? Maximisent-ils certaines fonctions globales ?

La classe PPAD[modifier | modifier le code]

Calculer un équilibre de Nash peut s'avérer, pour certains jeux, extrêmement long. Cette approche est celle de la théorie de la complexité, qui étudie entre autres le temps nécessaire pour résoudre les problèmes algorithmiques. Le calcul d'un équilibre de Nash appartient à la classe de problème PPAD (en). C'est même un problème complet pour cette classe grâce au théorème du point fixe de Brouwer. PPAD est une sous-classe de la classe NP[5].

Algorithmes[modifier | modifier le code]

Plusieurs algorithmes de résolution ont été proposés depuis les années 1970, mais la plupart ont des complexités inconnues. C'est pourquoi désormais, les jeux sont séparés en "classe" de jeux pour étudier les différents cas et les différentes complexités. Principalement, les recherches espèrent trouver l'existence d'un algorithme sous-exponentiel - - où n est la taille du jeu.

Équilibres de Nash approchés[modifier | modifier le code]

Pour les jeux à deux joueurs, les mesures de l'équilibre de Nash sont des nombres rationnels (la distribution de leur stratégie mixte) et sa solution est donc claire. Mais, selon Nash, lorsque le nombre de joueur augmente, il ne peut y avoir que des solutions irrationnelles. Les calculs deviennent alors numériquement imprécis, c'est pourquoi on introduit le concept d'équilibre de Nash approché ou approximé.

Si un équilibre de Nash est une situation dans laquelle personne ne souhaite dévier de sa stratégie, un ϵ-équilibre de Nash est un ensemble de stratégies mixtes dans laquelle les joueurs peuvent espérer augmenter leurs gain d'au plus ϵ en changeant de stratégie. Un ϵ-équilibre de Nash n'est pertinent que si ϵ est petit.

La question se pose de savoir s'il existe un schéma d'approximation en temps polynomial pour les équilibres de Nash approximés, c'est-à-dire un algorithme qui tourne en temps polynomial en rapport à la taille du jeu, en acceptant des dépendances sur temps sur 1/ϵ.

Équilibre de Nash dans la culture[modifier | modifier le code]

Film biographique Un homme d'exception[modifier | modifier le code]

Dans l'adaptation au cinéma de la biographie de Nash, Un homme d'exception, la découverte de cet équilibre est mise en scène par une stratégie de séduction.

  1. Quatre camarades de Nash souhaitent séduire une fille parmi les 5 présentes.
  2. Nash leur explique que s'ils suivent individuellement leur intérêt, ils tenteront tous les 4 de séduire la plus belle. Ils vont alors se court-circuiter et essaieront, par la suite, de se reporter sur l'une des quatre restantes. Mais « personne n'aime être un second choix », leur stratégie est donc vouée à l'échec.
  3. La meilleure stratégie serait donc de s'entendre pour séduire chacun l'une des quatre autres filles évitant, de ce fait, tout court-circuit. Ils augmenteront ainsi considérablement leurs chances de succès.

Nash en déduit que la théorie de la main invisible de Smith est lacunaire. Ce à quoi ses camarades rétorquent qu'il ne s'agit là que d'une stratégie destinée à lui permettre de séduire la plus belle.

Cette situation ne semble pas être un exemple d'équilibre de Nash, puisque chaque individu est tenté de tricher pour avoir la plus belle à lui seul. Donc, il y a ici un point focal (la belle) qui empêche de garder l'équilibre en prétendant aller séduire seulement les autres filles. Cependant, si on suit le raisonnement de Nash à la lettre, et si toute tentative de conquérir la belle à deux amène à un échec total (perte de la belle et des « seconds choix »), alors, de fait, l'ensemble des stratégies qu'il propose est un équilibre ; il convient seulement de remarquer qu'il en existe quatre autres, tous aussi valables... D'autre part, on ne peut pas en déduire que la théorie de la main invisible est lacunaire dans ce cas précis, car bien que les 4 camarades vont se court-circuiter, ici la concurrence n'est un échec que parce que la belle peut n'en choisir aucun.

Notes et références[modifier | modifier le code]

  1. Autisme-Economie.org, « Le talon d'Achille de la théorie des jeux (Autisme-Economie.org) », sur www.autisme-economie.org (consulté le 19 mars 2017)
  2. Une stratégie pure est une stratégie où il n'y a pas de choix probabiliste. Ici, une stratégie pure consiste à choisir uniquement pierre, uniquement ciseaux ou uniquement papier. Une stratégie non pure est par exemple de choisir pierre avec probabilité 1/3 et ciseaux avec probabilité 2/3.
  3. En fait, ce résultat est déjà assuré par le théorème du minimax
  4. Bernard Maris, Anti-manuel d'économie, Bréal, 2003
  5. Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou (Massachusetts Institute of Technology), The Complexity of Computing a Nash Equilibrium, p. 3 et suivantes .

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Jeux types[modifier | modifier le code]

Extensions de la notion[modifier | modifier le code]

Lien externe[modifier | modifier le code]