Équilibre de Nash

Dans la théorie des jeux , l'équilibre de Nash (nommé d'après John Forbes Nash, qui l'a proposée) est un concept de solution d'un jeu impliquant deux joueurs ou plus, dans lequel aucun joueur n'a rien à gagner en changeant seulement son propre stratégie unilatéralement. Si chaque joueur a choisi une stratégie et aucun joueur ne peut bénéficier en modifiant sa stratégie alors que les autres joueurs gardent leur inchangée, alors l'ensemble actuel de choix stratégiques et les gains correspondants constitue un équilibre de Nash.

En termes simples, Amy et le projet de loi sont en équilibre de Nash si Amy fait la meilleure décision qu'elle peut, en tenant compte de la décision du projet de loi, et le projet de loi fait la meilleure décision qu'il peut, en tenant compte de la décision de Amy. De même, beaucoup de joueurs sont en équilibre de Nash si chacun fait la meilleure décision qu'ils peuvent, en tenant compte des décisions des autres. Cependant, l'équilibre de Nash ne signifie pas nécessairement le meilleur gain cumulé pour tous les acteurs concernés; dans de nombreux cas, tous les joueurs peuvent améliorer leurs gains se ils étaient en accord sur des stratégies différentes de l'équilibre de Nash (par exemple, les hommes d'affaires. concurrentes formant une entente afin d'augmenter leurs profits).

Histoire

Le concept de l'équilibre de Nash (NE) ne est pas tout à fait originale de Nash (par exemple, Antoine Augustin Cournot a montré comment trouver ce que nous appelons maintenant l'équilibre de Nash de la Cournot jeu de duopole). Par conséquent, certains auteurs se réfèrent à lui comme un «équilibre de Cournot-Nash" (ou comme un «équilibre de Nash-Cournot"). Cependant, Nash a montré pour la première fois dans sa thèse, des jeux non-coopératifs (1950), que les équilibres de Nash (en stratégies mixtes) doit exister pour tous les jeux finis avec ne importe quel nombre de joueurs. Avant les travaux de Nash, ce ne avait été prouvée pour deux joueurs jeux à somme nulle (par John von Neumann et Oskar Morgenstern en 1947).

Définitions

Définition informelle

Officieusement, un ensemble de stratégies est un équilibre de Nash si aucun joueur ne peut faire mieux en changeant unilatéralement sa stratégie. Comme une heuristique, on peut imaginer que chaque joueur est dit les stratégies des autres joueurs. Si ne importe quel joueur voudrait faire quelque chose de différent après avoir été informé sur les stratégies des autres, alors ce jeu de stratégies ne est pas un équilibre de Nash. Si, toutefois, le joueur ne veut pas passer (ou est indifférent entre commutation et pas), puis l'ensemble des stratégies est un équilibre de Nash.

Cela peut avoir des conséquences contre-intuitives. Depuis l'équilibre de Nash se concentre sur les préférences d'un individu, étant donné que les autres gardent leurs choix fixés, il peut y avoir des équilibres de Nash où, si les joueurs pourraient coordonner, ils seraient tous veulent passer. Le chasse cerf présente un exemple de ce phénomène.

Définition formelle

Soit (S, F) est un jeu, où S est l'ensemble des profils de stratégies et F est l'ensemble des profils de gain. Laisser un profil de stratégies de tous les joueurs, sauf pour le joueur . Lorsque chaque joueur choisit la stratégie résultant du profil de stratégie alors le joueur obtient gain . Notez que le gain dépend du profil de stratégie choisie, ce est à dire sur la stratégie choisie par le joueur ainsi que les stratégies choisies par tous les autres joueurs. Un profil de la stratégie est un équilibre de Nash (NE) si aucune déviation dans la stratégie unilatérale par un seul joueur est rentable, ce est-

Un jeu peut avoir un NE pur de stratégie ou un NE dans son l'extension mixte (celui de choisir une stratégie pure stochastique avec un fixe fréquence). Nash a prouvé que, si nous permettons stratégies mixtes (les joueurs choisissent des stratégies au hasard, selon les probabilités pré-attribué), puis tous les n-joueur jeu dans lequel chaque joueur peut choisir parmi un nombre fini de stratégies admet au moins un équilibre de Nash.

Exemples

jeu de la concurrence

Ceci peut être illustré par un jeu à deux joueurs dans lequel les deux joueurs choisissent simultanément un nombre entier de 0 à 3 et ils ont tous deux gagner le plus petit des deux nombres en points. En outre, si un joueur choisit un nombre plus grand que l'autre, alors il / elle doit abandonner deux points à l'autre. Ce jeu a un unique équilibre de Nash: les deux joueurs choisissent 0 (surligné en rouge clair). Tout autre choix de stratégies peut être améliorée si l'un des joueurs abaisse son numéro à un de moins que le numéro de l'autre joueur. Dans le tableau à gauche, par exemple, lorsque commence sur la place verte, il est dans l'intérêt du joueur 1 pour passer au carré violet en choisissant un plus petit nombre, et il est dans l'intérêt du joueur 2 pour passer à la carré bleu en choisissant un plus petit nombre. Si le jeu est modifiée de sorte que les deux joueurs gagnent le montant indiqué si les deux choisissent le même nombre, et sinon rien gagner, alors il ya 4 équilibres de Nash (0,0 ... 1,1 ... 2,2. ..et 3,3).

jeu de coordination

Le jeu de coordination est un classique ( symétrique) deux joueurs, deux jeu de stratégie, avec le matrice des gains indiqué à droite, où les gains satisfont A> C et D> B. Les joueurs doivent donc coordonner, soit sur A ou sur D, pour recevoir une rentabilité élevée. Si les choix des joueurs ne coïncident pas, un paiement inférieur est récompensé. Un exemple d'un jeu de coordination est le milieu où deux technologies sont disponibles pour deux entreprises avec des produits compatibles, et ils doivent élire une stratégie visant à devenir le standard du marché. Si les deux entreprises se entendent sur la technologie choisie, les ventes élevés sont attendus pour les deux entreprises. Si les entreprises ne se entendent pas sur la technologie standard, le résultat de quelques ventes. Les deux stratégies sont équilibres de Nash du jeu.

Sur une route, et d'avoir à choisir soit de conduire sur la gauche ou de conduire sur le droit de la route, est aussi un jeu de coordination. Par exemple, avec 100 gains sens pas de crash et 0 signifie un accident, le jeu de coordination peut être définie avec la matrice de gain suivante:

Dans ce cas il ya deux équilibres de Nash de stratégie pure, lorsque les deux choisir de conduire sur la gauche ou sur la droite. Si nous admettons stratégies mixtes (où une stratégie pure est choisi au hasard, sous réserve de certaine probabilité fixe), puis il ya trois équilibres de Nash pour le même cas: deux nous avons vu de la forme pure stratégie, où les probabilités sont (0%, 100 %) pour le joueur un, (0%, 100%) pour deux joueurs; et (100%, 0%) pour une joueur, (100%, 0%) respectivement pour deux joueurs. Nous ajoutons une autre où les probabilités pour chaque joueur est (50%, 50%).

Dilemme du prisonnier

(Mais attention aux différences dans l'orientation de la matrice de gain)

Le dilemme du prisonnier a la même matrice de paiement comme représenté pour le jeu de coordination, mais maintenant C> A> D> B. Parce que C> A et D> B, chaque joueur améliore sa situation en passant de la stratégie n ° 1 à la stratégie n ° 2, peu importe ce que l'autre joueur décide. Le dilemme du prisonnier a ainsi un seul équilibre de Nash: les deux joueurs choisissent la stratégie n ° 2 ("trahir"). Ce qui a longtemps fait de ce un cas intéressant à étudier est le fait que D <A ("trahissent la fois") est globalement inférieur à "deux restent fidèles". La stratégie optimale à l'échelle mondiale est instable; ce ne est pas un équilibre.

Comme Ian Stewart a dit, "parfois des décisions rationnelles ne sont pas sensibles!".

Équilibres de Nash dans une matrice de paiement

Il ya une manière numérique facile d'identifier des équilibres de Nash sur une matrice Payoff. Il est particulièrement utile dans les deux jeux de personne où les joueurs ont plus de deux stratégies. Dans ce cas, l'analyse formelle peut devenir trop longtemps. Cette règle ne se applique pas au cas où (stochastiques) stratégies mixtes sont d'intérêt. La règle est la suivante: si le premier numéro de gain, dans le doublet de la cellule, est le maximum de la colonne de la cellule et si le second nombre est le maximum de la ligne de la cellule - alors la cellule représente un équilibre de Nash .

Nous pouvons appliquer cette règle à une matrice 3x3:

En utilisant la règle, nous pouvons très rapidement (beaucoup plus rapide que l'analyse formelle) voir que les cellules sont Equlibria Nash (B, A), (a, b) et (C, C). En effet, pour les cellules (B, A) 40 est le maximum de la première colonne et 25 est le maximum de la deuxième rangée. Pour (A, B) 25 est le maximum de la deuxième colonne et 40 est le maximum de la première rangée. Idem pour la cellule (C, C). Pour les autres cellules, l'un ou les deux éléments ne sont pas Duplet le maximum des lignes et des colonnes correspondantes.

Cela dit, la mécanique même de trouver des cellules d'équilibre est évidente: trouver le maximum d'une colonne et vérifier si le second membre de la paire est le maximum de la rangée. Si ces conditions sont remplies, la cellule représente un équilibre de Nash. Consultez toutes les colonnes de cette façon de trouver toutes les cellules de NE. Une matrice NxN peut avoir entre 0 et NxN stratégie pure équilibres de Nash.

Stabilité

Le concept de stabilité, utile dans l'analyse de nombreux types de équilibre, peut également être appliquée à des équilibres Nash.

Un équilibre de Nash pour un jeu de stratégie mixte est stable si une faible variation (en particulier, une variation infinitésimale) dans les probabilités pour un joueur conduit à une situation où deux conditions sont réunies:

1. le joueur qui n'a pas changé a pas de meilleure stratégie dans la nouvelle circonstance
2. le joueur qui a fait le changement est maintenant jouer avec une stratégie strictement pire

Si ces cas sont à la fois remplies, un joueur avec le petit changement dans sa stratégie mixte reviendra immédiatement à l'équilibre de Nash. L'équilibre est dite stable. Si la condition on ne tient pas alors l'équilibre est instable. Si une seule condition détient alors il ya probablement un nombre infini de stratégies optimales pour le joueur qui a changé. John Nash a montré que cette dernière situation ne pouvait pas se produire dans une gamme de jeux bien définies.

Dans l'exemple "de jeu de conduite" ci-dessus il ya deux équilibres stables et instables. Les équilibres impliquant mixtes stratégies avec 100% probabilités sont stables. Si un joueur change légèrement ses probabilités, ils seront à la fois dans une situation désavantageuse, et son adversaire ne auront aucune raison de modifier sa stratégie à son tour. La (50%, 50%) équilibre est instable. Si un joueur change ses probabilités, puis l'autre joueur a immédiatement une meilleure stratégie soit au (0%, 100%) ou (100%, 0%).

La stabilité est cruciale dans les applications pratiques des équilibres de Nash, depuis la stratégie mixte de chaque joueur ne est pas parfaitement connu, mais doit être déduite de distribution statistique de ses actions dans le jeu. Dans ce cas équilibres instables sont très peu probables dans la pratique, car tout changement de minute dans les proportions de chaque stratégie vu conduira à un changement de stratégie et la rupture de l'équilibre.

Notez que la stabilité de l'équilibre est liée à, mais distincte de la stabilité d'une stratégie.

Une Coalition-Proof équilibre de Nash (CPNE) (semblable à un solide équilibre de Nash) se produit lorsque les joueurs ne peuvent pas faire mieux, même se ils sont autorisés à communiquer et collaborer avant le match. Chaque stratégie corrélation soutenue par réitéré domination stricte et sur le Pareto frontière est un CPNE. En outre, il est possible pour un jeu d'avoir un équilibre de Nash capable de résister aux coalitions moins d'une taille spécifiée, k. CPNE est liée à la théorie du noyau.

Occurrence

Si un jeu a un équilibre de Nash unique et est joué entre les acteurs, sous certaines conditions, alors l'ensemble de la stratégie de NE seront adoptées. Des conditions suffisantes pour garantir que l'équilibre de Nash est joué sont:

1. Les joueurs seront tous faire tout leur possible pour maximiser leur gain espéré comme décrit par le jeu.
2. Les joueurs sont dans l'exécution sans faille.
3. Les joueurs ont une intelligence suffisante pour en déduire la solution.
4. Il est de notoriété publique que tous les joueurs remplissent ces conditions, y compris celui-ci. Ainsi, non seulement chaque joueur doit connaître les autres joueurs remplissent les conditions, mais aussi ils doivent savoir que tous savent qu'ils les rencontrent, et nous savons qu'ils savent qu'ils savent qu'ils les rencontrent, et ainsi de suite.

Lorsque les conditions ne sont pas remplies

Exemples de problèmes de la théorie des jeux dans lesquels ces conditions ne sont pas remplies:

1. La première condition ne est pas remplie si le jeu ne décrit pas correctement les quantités un joueur souhaite maximiser. Dans ce cas, il n'y a pas de raison particulière pour ce joueur à adopter une stratégie d'équilibre. Par exemple, le dilemme du prisonnier ne est pas un dilemme Si un joueur est heureux d'être emprisonnés indéfiniment.
2. Imperfection intentionnelle ou accidentelle dans l'exécution. Par exemple, un ordinateur capable de jouer logique sans défaut faisant face à un second ordinateur sans défaut entraîne l'équilibre. Introduction d'imperfection conduire à sa rupture, soit par perte pour le joueur qui commet l'erreur, ou par la négation de la 4e critère «connaissance commune» conduisant à la victoire possible pour le joueur. (Un exemple serait un joueur mettant soudainement la voiture en marche arrière dans le jeu de «poulet», assurant un ni perte scénario sans victoire). Un exemple notable de cette situation dans la fiction est la série Doctor Who Destiny of the Daleks
3. Dans de nombreux cas, la troisième condition ne est pas remplie car, même si l'équilibre doit exister, il ne est pas connu à cause de la complexité du jeu, par exemple dans Échecs chinois. Ou, se il est connu, il peut ne pas être connu de tous les joueurs, comme lors de la lecture tic-tac-toe avec un petit enfant qui veut désespérément gagner (les autres critères).
4. Le quatrième critère de la connaissance commune ne peut pas être respectée, même si tous les joueurs ne, en fait, répondent à tous les autres critères. Joueurs méfiant tort la rationalité de l'autre peut adopter des contre-stratégies pour attendre jeu irrationnelle pour le compte de leurs adversaires. Ce est un facteur important dans " Poulet "ou un course aux armements, par exemple.

Lorsque les conditions sont remplies

En raison des conditions limitées dans lesquelles NE peut effectivement être observé, ils sont rarement traités comme un guide pour le comportement au jour le jour, ou observées dans la pratique dans les négociations humains. Cependant, comme un concept théorique dans l'économie et la biologie évolutive du NE a pouvoir explicatif. Le gain en économie est de l'argent, et dans la transmission de gènes de la biologie évolutive, les deux sont la ligne de fond fondamentale de la survie. Les chercheurs qui se appliquent la théorie des jeux dans ces domaines que les agents affirment ne pas maximiser ces pour une raison quelconque seront en concurrence sur le marché ou de l'environnement, qui sont attribué la possibilité de tester toutes les stratégies. Cette conclusion est tirée de la " stabilité théorie "ci-dessus. Dans ces situations, l'hypothèse que la stratégie observé est en fait un NE a souvent été confirmée par la recherche.

Preuve de l'existence

Comme ci-dessus, laissez- un profil de stratégie mixte de tous les joueurs, sauf pour le joueur . Nous pouvons définir une meilleure réponse la correspondance pour le joueur , . est une relation de l'ensemble de toutes les distributions de probabilités sur les profils de joueurs adversaire à un ensemble de lecteur 'de stratégies, de telle sorte que chaque élément de

est une meilleure réponse à . Définir

.

On peut utiliser le Kakutani théorème du point fixe de prouver que a un point fixe. Autrement dit, il se agit d'un tel que . Depuis représente la meilleure réponse pour tous les joueurs à , L'existence du point fixe prouve qu'il ya un certain ensemble de la stratégie qui est une meilleure réponse à lui-même. Aucun joueur ne peut faire mieux en se écartant, et il est donc un équilibre de Nash.

Lorsque Nash a fait ce point à John von Neumann en 1949, von Neumann célèbre rejeté par les mots: «Ce est trivial, vous savez. Ce est juste un théorème du point fixe." (Voir Nasar, 1998, p. 94.)