Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

THÉORIE DES JEUX : ÉQUILIBRES DE NASH INDEX 1) INTRODUCTION 1.1)Définition d'un

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'ils ne 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 nupplet (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 ce que 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 uis1 ,.. ,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*(BA), et u2=1/2*(AB) Il est parfois pratique de considérer un pseudojoueur P0 qui représente les événements aléatoires (jets de dés par 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'être trop 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 mupplet x1,.. , xn∈ℝ m dans le (m1)simplexe, i.e. tel que ∀i∈{1 , ..,m}, xi≥0 et∑ i=1 m xi=1 . on interprète alors xi comme la probabilité que le joueur choisisse le coup i. On obtient alors une stratégie mixte. La straté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 xi×ukS ,ioù S est le nupplet 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 une probabilité p (et donc la seconde avec une probabilité(1p)) si P1 parie sur 1 avec une probabilité de x et P2 avec une 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+(1x)*(1p)*By*p*A(1y)*(1p)*A=(2p1)(BxAy)+(1p)(BA) 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 à une ré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 fini d'alternatives défini par les règles du jeu, chacun ignorant le choix de l'autre. Le choix d'une alternative par chacun 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 parmi n 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 luimê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≤m 1≤j≤n xiai , 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 si P2 joue  Y il est protégé contre une perte supérieure à E X ,  Y (éventuellement négative). C'est une maniè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 sousespace 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 plus grande coordonnée du point ( ||.||∞). Cette fonction est continue donc admet un minimum sur C, et la straté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 est infé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 (m1) et (n1)simplexe dans luimême : X=x1 , .. xm,Y=y1 , .. ynX '=xi'= xiaiX ,Y  1 ∑ k akX ,Y   1≤i≤m ,Y '=y j'= y jb 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 Brouwer assure 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 nupplet des stratégies de tous les joueurs. Chaque nupplet de stratégies pure rapporte un certain gain à chaque joueur, les fonctions utilité u des joueurs sont leurs espérances en fonction des distributions de probabilité. On dit que S1 contre S2 si et seulement si : ∀i∈{1 , .. ,n},uiX 1,1 ,.. , X i−1,1 , X i,2 , X i1,1 ,.. , X n,1= max X stratégiedei {uiX1,1 ,.. , X i−1,1 , X , X i1,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 luimême est appelé équilibre.  uploads/Marketing/ nash-tipe2005.pdf