4) L'équilibre de Nash

Durant la partie précédente nous avons définis des stratégies sur une manche c'est l'ensemble . De plus on peut répéter les manches, donc itérer le jeu ainsi des stratégies sur plusieurs manches émergent. Durant le reste du rapport nous allons voir comment peut t'on comparer plusieurs stratégies (sur plusieurs manches) et quelles sont les meilleur sur un exemple typique de la théorie des jeux : le dilemme du prisonnier.

Tout d'abord on peut comparer des stratégies sur plusieurs manches en terme de victoires par rapport à d'autres stratégies, c'est l'idée la plus répandue dans notre société: faire mieux que les autres. Mais on peut aussi les comparer sur les gains obtenus après quelques confrontations c'est basé sur l'axiome principale de la théorie des jeux: la rationalité des joueurs. Il y a un autre critère intéressant que nous pouvons observer : l'idée de regret. L'équilibre de Nash ce base sur cette idée : l'absence de regrets.

4.1) L'équilibre de Nash en stratégies pures

a) Origine :

En 1776 l'économiste Adam Smith publie :Recherche sur la nature et les causes de la richesse des nations dans lequel il écrit «(...) chaque individu qui emploie son capital à faire valoir l'industrie nationale, tâche nécessairement de diriger cette industrie de manière que le produit qu'elle donne ait la plus grande valeur possible.» ainsi selon lui il énonce que chaque participant ne doit s'occuper que de ses intérêts pour maximiser ses gains . On pourrait reprendre cela sous la forme de "chacun pour soi".

Si nous prenons un exemple de jeux suivant: La bataille des sexes dont voici un énoncer:

Une femme et son mari cherchent une idée de sortie, le mari propose d'aller à un match de foot de son équipe préférée et la femme propose elle d'aller à un concert de son chanteur préféré. Chacun essai donc de convaincre son partenaire mais il est sûr que aucun des deux n'a intérêt d'aller à sa sortie non accompagné de son époux ou de son épouse. On peut donc représenter ce jeu sous la forme de la matrice suivante:

Si chacun pense a son propre intérêt d'après Adam Smith on abouti à la situation (Foot,Concert) qui nous donne comme gain (1,1) . Mais si chacun pense à la fois à son intérêt et à l'intérêt du couple, on aboutirait à un gain de (4,2) ou (2,4) (cela dépend de la personne qui "céderait" la première). Ces deux situations sont des équilibres de Nash.

b) Définition :

Voici une définition de l'équilibre de Nash :

Situation où aucun joueur n'a intérêt a dévier individuellement de sa stratégie

On pourrait de définir aussi de la façon suivante ce qui revient au même:

Situation dans laquelle les joueurs n'ont pas de regrets après avoir vu les stratégies des autres joueurs

Dans l'exemple précédant on voit bien le risque que prendrait une des deux personne a changer d'avis au dernier moment soit il irait à une sortie qu'il n'apprécierait pas soit il se retrouverait tout seul à sa sortie.

Une remarque intéressante viens du fait que lors d'un équilibre de Nash aucun des participants n'a de regrets donc tout le monde est gagnant alors que l'on pourrai penser que dans un conflits entre 2 personnes il y a toujours un gagnant et un perdant.

Nous allons maintenant formaliser tout cela de façon à l'appliquer à des cas plus complexes.

L'équilibre de Nash en stratégies pures:

Soit un jeu en stratégie pures et sous forme stratégique suivant:

Si tel que:

alors s* est un équilibre de Nash du jeu

avec:

* S : l'ensemble des règlements possibles

*

Remarque:

Si un a une inégalité stricte on dit que s* est un équilibre de Nash strict.

4.2) Quelques exemples d'équilibre de Nash en stratégies pures

a)Un jeu avec un unique équilibre de Nash :

Soit le jeu sous forme normale en stratégies pures dont la matrice des gains est la suivante:

* si s* = (S1,S1) était un équilibre de Nash on aurait:

ET

 5 ≥ 5 et 5 ≥ 3 ET 2 ≥ 2 et 2 ≥ 4 et 2 ≥ 4 absurde

donc s* = (S1,S1) n'est pas un équilibre de Nash

on fait de même avec les autres règlements pour arriver au règlement s* = (S2,S3)

* Si s* = (S2,S3) était un équilibre de Nash on aurait:

≡ET

≡ 6 ≥ 5 et 6 ≥ 6 ET 2 ≥ 1 et 2 ≥ 0 et 2 ≥ 0 vrai

donc s* = (S2,S3) est un équilibre de Nash

b) Un jeu sans équilibre de Nash :

Il existe des jeux où il n'y a pas d'équilibre de Nash, c'est à dire que quoi qu'il en soit un des participants regrettera son choix. Prenons un exemple:

Soit le jeu sous forme normale en stratégies pures dont la matrice des gains est la suivante:

Si J1 joue S1:

- Et J2 joue S1 gain: (1;0) J2 regrettera son choix il aurait dû jouer S2 gain:(0;1)

- Et J2 joue S2 gain: (0;1) J1 regrettera son choix il aurait dû jouer S2 gain:(1;0)

Si J1 joue S2:

- Et J2 joue S1 gain: (0;1) J1 regrettera son choix il aurait dû jouer S1 gain:(1;0)

- Et J2 joue S2 gain: (1;0) J2 regrettera son choix il aurait dû jouer S1 gain:(0;1)

Ainsi ce jeu n'a pas d'équilibre de Nash en stratégies pures.

c) Un jeu avec de multiples équilibres de Nash:

Si on reprend la bataille des sexes suivant:

(Foot,Foot) et (Concert,Concert) sont deux équilibres de Nash aucun des époux n'aura intérêt a quitter le spectacle sous peine de se retrouver seul et au pire dans un spectacle qu'il n'apprécierai pas.

4.3)L'équilibre de Nash en stratégies mixtes

a) Origine :

Lorsque nous participons à un jeux il arrive que nous ne savons pas exactement quelle carte jouer, la même stratégie dans le cas général. Par contre s'il s'avère que nous jouons avec des préférences par exemple au jeu pierre feuille ciseaux il se peut que quelqu'un joue sur un coup de préférence pierre . Nous avons donc introduit les jeux en stratégies mixtes lors du dernier exposé et nous allons donc nous pencher sur l'équilibre de Nash en stratégies mixtes.

b) Définition et rappels :

On peut reprendre la même définition que celle d'un équilibre de Nash en stratégies mixtes:

Situation où aucun joueur n'a intérêt a dévier individuellement de sa stratégie

On pourrait de définir aussi de la façon suivante ce qui revient au même:

Situation dans laquelle les joueurs n'ont pas de regrets après avoir vu les stratégies des autres joueurs

Par contre puisque nous somme en stratégies mixtes il est important de souligner que les stratégies ne sont plus du type "jouer pierre", "aller au foot"... mais sont des distributions de probabilité sur les stratégies pures (On dit qu'un jeu en stratégies mixtes est une extension mixte d'un jeu en stratégies pures sous forme normale ).

Ce schéma rappel les principales notations utilisées en stratégies mixtes. Cette présentation complète ce schéma.

Pi,Fe,Ci représente chacun une stratégie (respectivement pierre, feuille et ciseaux)

σ₁ représente une stratégie mixte du joueur 1 pour distinguer les stratégies mixtes on met une astérisque ce qui donne ₁^*

Σ₁ représente l'ensemble des stratégies mixtes du joueur 1

σ représente un règlement

Σ représente l'ensemble des règlements possibles

Nous allons maintenant formaliser tout cela de façon à l'appliquer à des cas plus complexes.

L'équilibre de Nash en stratégies mixtes:

Soit le jeu en stratégies mixtes et sont forme normale suivant:

Si tel que:

alors o* est un équilibre de Nash du jeu

avec:

*  l'ensemble formé de toutes les stratégies mixtes de chaque joueur.

*

* l'utilité espéré du joueur i lorsqu'il joue la stratégie pure s_i et lorsque les autres joueurs jouent le profit de stratégies mixte o_-i.

c) Un petit exemple :

Nous pouvons reprendre l'exemple du B.b.2: Mais cette fois en l'étendant aux stratégies mixtes.

Voici la représentation du jeu sous forme stratégique:

Maintenant étendons le en stratégies mixtes:

On a donc

• σ₁=(p,1-p) la stratégie du joueur 1 c'est-à-dire il joue S1 avec une probabilité p et S2 avec une probabilité 1-p.

• σ₂=(q,1-q) la stratégie du joueur 2 c'est-à-dire il joue S1 avec une probabilité q et S2 avec une probabilité 1-q.

On peut calculer l'espérance de gains anticipés pour J1

E₁(S1) =u₁(S1,σ₂)= q.1+(1-q).0=q

E₁(S2)=u₁(S2,σ₂)=q.0+(1-q).1=1-q

Or J1 doit être indifférent d'où: 1-q=q donc q=1/2

De même pour J2:

E₂(S1) = u₂(S1 , σ₁) = p.1 + (1-p).0 = p

E₂(S2) = u₂(S2 , σ₁) = p.0 + (1-p).1 = 1-p

Or J2 doit être indifférent d'où: p=1-p donc p=1/2

Ainsi l'équilibre de Nash en stratégies mixtes est le suivant: ((1/2,1/2),(1/2,1/2)).

Il est intéressant de noter que nous n'avons pas trouvé d'équilibre de Nash en stratégies pures pour ce jeu mais nous en avons en stratégies mixtes cette remarque introduit donc le théorème suivant.

d) Le théorème de Nash :

Tout jeu sous forme normale fini possède au moins

un équilibre de Nash en stratégies mixtes

Nous admettons ce théorème puisque la démonstration fait intervenir la notion de continuité de fonctions multilinéaires, de fonctions quasi concaves d'ensembles convexe…

Dans cette partie nous avons vu les conditions pour qu'un profil de stratégies soit un équilibre de Nash , mais nous ne savons pas comment trouver un équilibre de Nash c'est l'objet de la partie suivante.

4.4) Recherche d'équilibre de Nash

Dans la sous partie précédente nous avons vu le critère pour qu'un règlements soit un équilibre de Nash mais nous n'avons toujours pas vu un algorithme permettant de le trouver (hormis celui de vérifier règlement par règlements si on a un équilibre de Nash ce qui est fastidieux).

Nous allons donc voir un algorithme de recherche d'un équilibre de Nash et stratégie pure et sous forme stratégique.

a) Stratégies dominées et dominantes :

Voici la définition d'une stratégie dominante:

On dit qu'une stratégiedomine faiblement une stratégie≡

quelque soit la réponse des adversaires on obtient des gains supérieurs en jouantplutôt que

En formalisant on a:

domine faiblement ≡

Remarque:

- Si on a une inégalité stricte on a une dominance stricte

- Si domine faiblement (respectivement strictement) on dit queest faiblement (respectivement strictement) dominante

b) Méthode des stratégies dominantes :

Un algorithme de recherche d'un équilibre de Nash est celui des stratégies dominantes. Dont voici l'algorithme:

Algorithme :

- On barre les stratégies dominées

- On recommence avec les cases non barrées

- La dernière case non barrée est l'équilibre de Nash du jeu

Cet algorithme s'explique par le fait qu'un joueur regrettera d'avoir prix une stratégie dominée par une autre car ses gains seront alors moins importants.

c) Exemple :

Reprenons l'exemple du B.a.3):

Soit le jeu sous forme normale en stratégies pures dont la matrice des gains est la suivante:

Pour J2 , S1 est (strictement) dominée par S3 on barre S1 (en bleu)

Pour J2 , S2 est (faiblement) dominée par S3 on barre S2 (en rouge)

Pour J1 , S1 est (strictement) dominée par S2 on barre S1 (en vert)

donc (S2,S3) est l'équilibre de Nash du jeu.

d) Une remarque :

Malheureusement cet algorithme ne permet pas de déterminer les équilibres de Nash de n'importe quel jeu puisqu'en effet le jeu de la guerre des sexes a bien deux équilibres de Nash , mais n'a par contre pas de stratégies dominantes.

Voici une de ses représentations sous forme stratégiques:

Foot ou concert ne constituent pas de stratégies dominantes aussi bien pour l'homme que pour la femme alors que ce jeu a deux équilibres de Nash comme nous l'avons montré précédemment.