THÉORIE DES JEUX : ÉQUILIBRES DE NASH

INDEX

1) INTRODUCTION

1.1)Définition d'un jeu

1.2)Historique et applications

2)LES JEUX MATRICIELS

2.1)Définition

2.2)Le Théorème fondamental

2.3)Principe de la preuve

3)UN PREMIER EQUILIBRE DE NASH

3.1)Hypothèses

3.2)L'équilibre

3.3)Principe de la preuve

3.4)Applications

4)EQUILIBRE DE NASH, GENERALISATION

4.1)Hypothèses

4.2)L'équilibre

4.3)Principe de la preuve

4.4)Applications

5)RECHERCHE EFFECTIVE DES EQUILIRBES

5.1)Algorithme de résolution des jeux matriciels

5.2)Approche différentielle

5.3)Limites des équilibres de Nash

6)BIBLIOGRAPIE

7)ANNEXE : ILLUSTRATIONS

1)        INTRODUCTION   

1.        définition d'un jeu :   

définition courante : 

Des joueurs obtiennent des bénéfices en fonction de leurs choix, qui se font selon des règles.exemples : un jeu de carte, jouer en bourse...

en    mathématiques    :    

Quelques hypothèses : les joueurs sont rationnels, ils cherchent uniquement à maximiser leurs gains,indépendamment de toute autre considération.  Ils sont supposés ''suffisamment intelligents'', c'est­à­dire qu'ilsne feront pas d'erreurs de jugement ou de calcul.

Les règles permettent aux joueurs des stratégies. On appelle P1 , ..,  Pn les n joueurs.On appelle Si l'ensemble des stratégies du joueur Pi.

exemple : jeu de pile ou face :il s'agit d'un jeu à deux joueurs.  Chacun parie sur ''pile'' ou sur ''face'' : S1=S2={pile , face}.

Chaque n­upplet (s1,..,sn) donne lieu à une attente pour chaque joueur, selon le cas appelée espérance, gain,satisfaction ou utilité. il s'agira d'un nombre réel représentant son gain (ou son espérance de gain) à la fin du jeu(ou d'un tour du jeu). l'espérance de Pi sera représentée par une fonction  ui : S1×...×Snℝ : elle indique ceque peut espérer gagner le joueur i quand chaque joueur k joue la stratégie sk : le gain de i est le nombre réel

uis1 , .. , sn .

Dans le cas du jeu de pile ou face : si P1 parie sur pile et P2 sur face (stratégies pures)u1=Probabilité de pile*Montant parié par P2 ­ Probabilité de face*Montant parié par P1 u2=Probabilité de face*Montant parié par P1 ­ Probabilité de pile*Montant parié par P2

donc si le jeu n'est pas truqué, si P1 parie A et P2 parie B :u1=1/2*(B­A), et u2=1/2*(A­B)

Il est parfois pratique de considérer un pseudo­joueur P0 qui représente les événements aléatoires (jets de déspar exemple).  La stratégie de P0 est alors la distribution de probabilité des issues possibles.

De même les joueurs peuvent donner à leurs choix un caractère aléatoire, afin de se protéger du risque d'êtretrop prévisibles par leurs adversaires. Si chaque joueur a le choix parmi un ensemble fini d'alternatives {c1 , .. ,cm }, cela se fait en attribuant à chaque coup une probabilité, i.e. en choisissant un m­upplet

x1 , .. , xn ∈ ℝm  dans le (m­1)­simplexe, i.e. tel que  ∀ i∈{1 ,  .. , m}, x i≥0 et∑i=1

m

x i=1  . on interprète

alors xi comme la probabilité que le joueur choisisse le coup i.  On obtient alors une stratégie mixte.  Lastratégie consistant à toujours choisir un certain cj (où j est fixé) est appelée stratégie pure.

l'espérance du joueur est alors :  E k S =∑i=0 

m

x i×uk S , i où S est le n­upplet des stratégies des n joueurs, et

uk( (S,i) ) représente son gain (ou son espérance) s'il joue sa ieme alternative, les stratégies des autres joueursétant fixées.

Un exemple toujours inspiré du jeu de pile ou face : si deux issues sont possibles, la première avec uneprobabilité p (et donc la seconde avec une probabilité(1­p)) si P1 parie sur 1 avec une probabilité de x et P2 avecune probabilité de y : on suppose que si le pari d'un joueur se réalise, l'autre lui donne le montant parié (quitte àfaire des ''échanges'') :u1(x,y)=x*p*B+(1­x)*(1­p)*B­y*p*A­(1­y)*(1­p)*A=(2p­1)(Bx­Ay)+(1­p)(B­A)

2.        historique et application   

Acte de naissance de la théorie des jeux : thèse de Louis Bachelier, 1900 : Théorie de la Spéculation Ouvrage clef :  Theory of Games and Economic Behavior (1944, John von Neumann et Oskar Morgenstern).John Forbes Nash : de grandes avancées dans les années 50 (Nobel Prize in Economic Sciences, 1994).

La théorie des jeux est particulièrement utile pour donner un cadre mathématique rigoureux aux étudeséconomique ou sociologique, même si la plupart des cas concrets sont trop complexes pour se prêter à unerésolution formelle.

2) LES JEUX MATRICIELS : A DEUX JOUEURS ET A SOMME NULLE   

1. définition   

Un type courant de jeux : deux joueurs s'affrontent.  Ils font chacun des choix dans un ensemble finid'alternatives défini par les règles du jeu, chacun ignorant le choix de l'autre.  Le choix d'une alternative parchacun des joueurs entraîne un gain pour chacun d'eux, et la somme de leurs gains est nulle (ce qui est gagnépar l'un est perdu par l'autre).

Soient les joueurs P1 et P2. P1 peut choisir parmi m alternatives que nous désignerons par {1, .. , m} et P2 parmin alternatives, {1, .. , n}.Si P1 choisit sa ieme alternative et P2 sa jeme, P1 gagne le montant ai,j (donc P2 perd cette même somme).Le jeu peut être représenté par la matrice suivante :

par exemple, le jeu bien connu de ''pierre, ciseaux, papier'' : on rappelle que ''pierre'' l'emporte sur''ciseaux'', qui lui­même l'emporte sur ''papier'', qui a sont tour vainc ''pierre''.  Si le joueur gagnant empoche 1€,qui est déboursé par le perdant, la matrice du jeu est :

0  1  −1 −1  0  1 1  −1  0

a1,1 .. a1, n

.. .. ..am ,1 .. am , n

Soient  X=x1 ,  .. , xm une stratégie mixte de P1 et  Y=y1 ,  .. , yn une stratégie mixte de P2.Alors l'espérance de P1 est  E X ,Y = ∑

1≤i≤m1≤ j≤n

x i ai , j y j  et celle de P2 en est l'opposé puisque le jeu est à somme

nulle.Donc P1 va chercher à maximiser E et P2 à la minimiser.

2.        le théorème fondamental (   von    Neumann)   

Il existe un couple de stratégies mixtes  X , Y tel que que :∀X ,Y couple de stratégies mixtes , E X , Y ≤E X , Y ≤E X ,Y

Ce qui signifie que si P1 joue  X il s'assure une certain gain (éventuellement négatif) quoi que je joue P2, et siP2 joue  Y il est protégé contre une perte supérieure à  E X , Y (éventuellement négative).  C'est unemanière de ''jouer sûr'', en évitant les mauvaises surprises.

3.        principe de la preuve :   

Preuve inspirée de John von Neumann :Cette preuve repose sur la géométrie euclidienne en dimension n.

On se place dans l'espace C des espérances de P2 en fonction des choix de P1 (c'est donc un sous­espace deℝm ).  C'est un ensemble fermé, borné et convexe (c'est l'enveloppe convexe des espérances de P2 s'il jouait

ses stratégies pures).On considère la fonction qui à un point de cet ensemble associe la pire des pertes possibles pour P2, i.e. la plusgrande coordonnée du point ( || . ||

∞ ).  Cette fonction est continue donc admet un minimum sur C, et lastratégie correspondante Y est optimale.  Soit v ce minimum.On considère l'ensemble D des points dont la plus grande coordonnée est v (points où la perte de P2 estinférieure ou égale à v).  On montre qu'il existe un hyperplan affine H(X,a)  séparant C et D, et que V=(v,..,v)est dans H.  On montre qu'en normalisant X on obtient une stratégie optimale  X .

Preuve de John Nash : par le    théorème    du point fixe de    Brouwer    :   

Si on désigne par i la ieme stratégie pure de P1 et par j la jeme stratégie pure de P2 :On considère les fonctions :  ai(X,Y)=max(0,E(i,Y)­E(X,Y))

bj(X,Y)=max(0,E(X,Y)­E(X,j))et on considère l'application continue du produit des (m­1) et (n­1)­simplexe dans lui­même :

X=x1 ,  .. xm ,Y=y1 ,  .. ynX '=x i '=x iai X ,Y

1 ∑k

ak X ,Y 1≤i≤m

,Y '=y j '=y jb j X ,Y

1 ∑k

bk X ,Y 1≤ j≤n

On vérifie que les équilibres sont exactement les points fixes de cette application, le théorème de Brouwerassure l'existence d'un point fixe.

3)        UN PREMIER    ÉQUILIBRE    DE NASH :   

1.        pour quels jeux ?   

On considère un jeu à n personnes.  Chacun des joueurs a ni stratégies pures,  ni∈ℕ* .

On note Xi la stratégie du joueur i.  On note S=(X1 , .. , Xn) le n­upplet des stratégies de tous les joueurs.Chaque n­upplet de stratégies pure rapporte un certain gain à chaque joueur, les fonctions utilité u des joueurssont leurs espérances en fonction des distributions de probabilité.On dit que S1 contre S2 si et seulement si :∀ i∈{1 ,  .. , n},uiX 1,1 , .. , X i−1,1 , X i ,2 , X i1,1 , .. , X n ,1= max

X stratégie de i{uiX1,1 , .. , X i−1,1 , X , X i1,1 , .. , X n ,2}

Ce qui signifie que dans la situation 1, chacun a intérêt à passer à la situation 2.

2.        l'équilibre :   

Un S qui se contre lui­même est appelé équilibre.S= s1 , .. , sn  est un équilibre si et seulement si :

  ∀ i∈{1,  .. , n},ui s1 , .. , sn= maxs stratégie de i

s1 , .. , si−1 , s , si1 , .. , sn

Cela signifie que dans la situation d'équilibre, chacun gagne le maximum de ce qu'il peut attendre étant donnéesles stratégies des autres joueurs.  C'est­à­dire que personne n'a intérêt à changer de stratégie unilatéralement.

Tout jeu vérifiant les hypothèses ci­dessus admet un équilibre.

3.        principe de la preuve :   

On remarque d'abord que l'ensemble des stratégies contrant une stratégie donnée est convexe.On considère la correspondance qui à un n­upplet de stratégie associe l'ensemble des n­upplets qui le contre :l'image de tout point est convexe.On remarque ensuite que les fonctions gains sont continues, donc l'image de la correspondance précédente estfermée.Le théorème de Kakutani assure alors qu'il existe un point fixe, i.e. un point contenu dans son image, c'est­à­dire un équilibre.

4.        application :   

application aux jeux matriciels (le théorème fondamental est un cas particulier du théorème de Nash).

4)        ÉQUILIBRE    DE NASH : GÉNÉRALISATION :   

1.        hypothèses :   

Jeu non­coopératif à n joueurs.L'ensemble des stratégies du joueur i est un compact convexe Ki dans un espace euclidien.La fonction satisfaction ui du joueur Pi vérifie :∀x1 ,  .. , x i−1 , x i1 , .. , xn ∈K 1 ×..×K i−1×K i1 ..×K n , x∈K iuix1 ,  .. , x i−1 , x , x i1 , .. , xnest concave

i.e. la fonction qui, étant données les stratégies de n­1 joueurs, donne le gain du dernier en fonction de sastratégie, est concave pour tout joueur et pour tout (n­1)­upplet de stratégies ;

par exemple en dimension 2 : 

2.        l'équilibre :   

Il existe alors un équilibre, i.e. un n­upplet de stratégies  x1 ,  .. , xn tel que  ∀ i∈{1,  .. , n},∀ x∈K i ,u x1 , .. , xn≥u x1 , .. , x i−1 , x , x i1 , .. , xn

Ainsi personne n'a intérêt à changer unilatéralement de stratégie.

On remarque que le théorème précédent est un cas particulier de celui­ci en considérant que l'ensemble desstratégies est l'ensemble des distributions de probabilité, et les fonctions utilités sont les espérances.

3.        principe    de la preuve :   

Cette preuve repose sur le théorème du point fixe de Brouwer.

Si les fonctions gains sont strictement concaves (sinon, on les approche par des fonctions strictementconcaves) : alors la fonction

x1 ,  .. , x i−1 , x i1 , .. , xn ∈K 1 ×..×K i−1×K i1 ..×K n , x∈K iuix1 ,  .. , x i−1 , x , x i1 , .. , xn

admet un maximum en un unique point Mi(x1,..,xi­1,xi+1,..,xn).  On définit ainsi les fonctions Mi de.

On vérifie que le graphe de Mi est compact et que Mi est continue.On considère alors l'application de  K 1 ×..×K n dans lui même qui à (x1,..,xn) associe( M1(x2,..,xn) , .. , Mn(x1,..,xn­1) ).On vérifie que ses points fixes sont des équilibres, et le théorème de Brouwer assure l'existence d'un équilibre.

4.        applications :   

Tous les théorèmes précédents peuvent être vus comme des cas particuliers de celui­ci.

5)        RECHERCHE DES ÉQUILIBRES DE NASH DANS DES SITUATIONS   EFFECTIVES

Les théorèmes précédents donnent l'existence des équilibres, mais sont impuissants quant à leurdétermination effective.

On s'intéresse à la manière dont les joueurs peuvent déterminer l'équilibre de Nash du jeu et/ou lameilleure stratégie en fonction de ce qu'il savent du jeu.

∏j≠i

K jK j

1.        algorithme de résolution des jeux matriciels   

Il existe un algorithme de résolution des jeux matriciels, basé sur le même principe que la preuve, maissa complexité le rend inapplicable dans la plupart des cas concrets.

2.        si les fonctions utilité sont C   1  , avec les    hypothèses      précédentes    :   

Que personne n'ait intérêt à changer de stratégie unilatéralement implique que :

∀ i∈{1 ,  .. , n}, si X i=x i ,1 , .. , x i , ni

,∀ j∈{1 ,  .. , ni},∂ui

∂ x i , j

X 1 , .. , X n=0

Donc on peut chercher les équilibres parmi les points vérifiant cette propriété mais on n'obtiendra pasforcément les éventuels équilibres qui seraient dans la frontière des ensembles de stratégie.

Cette méthode est applicable par exemple aux jeux matriciels.

Si les joueurs connaissent uniquement, à un instant donné, dans quelle ''direction'' ils doivent faire évoluer leurstratégie pour augmenter leur espérance de gain, on obtient des équations différentielles où les solutionsconstantes sont ces équilibres.Les simulations donnent une idée de l'évolution du jeu, et montrent que l'on peut parfois s'approcher del'équilibre.

Illustration : dans le cas d'un jeu matriciel, avec deux choix par joueur (leurs stratégies sont donc déterminéespar un seul paramètre chacun) :

3.        les limites :   

(1)        cycle autour de l'équilibre   

Dans le cas des jeux matriciels, les joueurs peuvent, selon le cas, converger vers l'équilibre, ou tourner autour.dans ce cas ils n'appliquent jamais la ''bonne'' stratégie .Par exemple :

(2)        équilibres sous­optimaux :   

L'exemple connu du dilemme du prisonnier montre que les équilibres de Nash ne sont pas forcément lesmeilleurs solutions.  D'où l'importance de la collaboration.

Autre exemple :  3 joueurs, chacun choisit X ou Y. gains :

nombre de X et Y : 3 X, 0 Y 2 X, 1 Y 1 X, 2 Y 0 X, 3 Yjoueurs X : +1 ­3 ­1 0joueurs Y : 0 +6 +1 ­2

Avec cet exemple, par les méthodes précédentes, on obtient un ''équilibre'' où l'espérance de chacun est prochede ­0.7, alors qu'il est clair que la stratégie pure consistant à toujours jouer X assure un gain de +1 à chaquetour.  Mais elle n'est pas un équilibre de Nash, et pour l'appliquer, les joueurs doivent  a priori se mettred'accord et se faire confiance.

6)        BIBLIOGRAPHIE   

Lectures on the Theory of Games (Harold W. Kuhn, ed. Princeton University Press)Essays on Game Theory (John Forbes Nash, Jr, ed. Edward Elgar)Théorie des Jeux (Xavier Caruso, inspiré du cours d'Ivar Ekeland)www.wikipedia.org (encyclopédie libre sur internet)www.mathworld.wolfram.com

7)ANNEXE : ILLUSTRATIONS

voici diverses évolutions obtenues par simulation :

un cycle assez chaotique :

les cycles peuvent prendre divers aspects enfonction des paramètres

ici l'équilibre est presque atteint :