Théorie des jeux - 2eme année d'économie et de gestion
Théorie des jeux. Introduction : Chapitre 1 : Notions de base. Section 1 :
Définitions préalables. A- Distinction entre jeux coopératifs et jeux non
coopératifs.
part of the document
Théorie des jeux
TOC \t "Titre de chapitre;1;Titre de section;2;Titre de paragraphe;3;Titre de paragraphe 2;4;Titre de paragraphe 3;5" Introduction : PAGEREF _Toc100684930 \h 1
Chapitre 1 : Notions de base PAGEREF _Toc100684931 \h 2
Section 1 : Définitions préalables. PAGEREF _Toc100684932 \h 2
A- Distinction entre jeux coopératifs et jeux non coopératifs. PAGEREF _Toc100684933 \h 2
B- Distinction entre jeux à information complète et jeux à information incomplète. PAGEREF _Toc100684934 \h 3
C- Distinction entre jeux à information parfaite et jeux à information imparfaite. PAGEREF _Toc100684935 \h 3
D- Distinction entre jeux dynamiques et jeux statiques. PAGEREF _Toc100684936 \h 3
Section 2 : Présentation des jeux sous forme normale (stratégique). PAGEREF _Toc100684937 \h 3
A- Définition initiale. PAGEREF _Toc100684938 \h 3
B- Définition stricte. PAGEREF _Toc100684939 \h 3
C- Exemples : jeux sous forme normale PAGEREF _Toc100684940 \h 4
1- Jeu du dilemme du prisonnier PAGEREF _Toc100684941 \h 4
2- Jeu bataille des sexes. PAGEREF _Toc100684942 \h 4
3- Jeux à trois stratégies et à somme nulle (papier, caillou, ciseaux). PAGEREF _Toc100684943 \h 5
4- Jeu pile ou face. PAGEREF _Toc100684944 \h 5
5- Jeu dit « poule mouillée ». PAGEREF _Toc100684945 \h 5
6- Jeu dentrée. PAGEREF _Toc100684946 \h 5
Section 3 : Forme extensive. PAGEREF _Toc100684947 \h 6
A- Présentation. PAGEREF _Toc100684948 \h 6
B- Ecriture stricte. PAGEREF _Toc100684949 \h 6
C- Exemples et passage de la forme normale à la forme extensive. PAGEREF _Toc100684950 \h 7
1- Réécriture pile face. PAGEREF _Toc100684951 \h 7
2- Récriture jeu pilote terroriste. PAGEREF _Toc100684952 \h 7
3- Autre cas : Elections ONU. PAGEREF _Toc100684953 \h 7
Section 4 : Stratégies pures / mixtes. PAGEREF _Toc100684954 \h 8
A- Définition : PAGEREF _Toc100684955 \h 8
B- Evaluation. PAGEREF _Toc100684956 \h 8
1- Jeu bataille des sexes. PAGEREF _Toc100684957 \h 8
2- Exemple 2 : PAGEREF _Toc100684958 \h 8
Chapitre 2 : Notions déquilibre PAGEREF _Toc100684959 \h 9
Section 1 : Equilibre en forme normale. PAGEREF _Toc100684960 \h 9
A- Dominance. PAGEREF _Toc100684961 \h 9
1- Stratégie dominante. PAGEREF _Toc100684962 \h 9
2- Equilibre en stratégie dominante. PAGEREF _Toc100684963 \h 10
3- Limites. PAGEREF _Toc100684964 \h 10
4- Passages à stratégies dominées. PAGEREF _Toc100684965 \h 11
5- Equilibre par élimination itératives stratégie dominées. PAGEREF _Toc100684966 \h 11
6- Limites. PAGEREF _Toc100684967 \h 12
7- Conclusion : PAGEREF _Toc100684968 \h 13
B- Equilibre de Nash. PAGEREF _Toc100684969 \h 13
a- Définition. PAGEREF _Toc100684970 \h 13
b- Exemples et intuition dun équilibre de Nash. PAGEREF _Toc100684971 \h 13
Introduction :
Définition générale : la théorie des jeux est un ensemble doutils ou de techniques pour prédire les résultats quun groupe dagents en interaction peut obtenir. Laction dun agent affecte directement les résultats ou les paiements des autres agents participant à laction globale. Le jeu est un conflit issu dune situation dinteractions. Outils signifie quil y a une dimension technique. Peut-on poser un cadre qui ait une reproductibilité ? La théorie des jeux fait suite logiquement à la théorie de la décision (Savage,
). Dans la théorie de la décision, les solutions analysées sont celles dun agent face à un ensemble de choix risqués ou non. En théorie des jeux, il y a plusieurs agents. Lidée de « jeu » est issue de la ressemblance formelle entre des problèmes de décision en situation dinteraction et les jeux au sens traditionnel (échecs, bridge). La théorie des jeux va sappliquer dans le cas où le nombre dagents est restreint, notamment en économie. Cest seulement dans ce cas que laction dun agent peut influencer laction et les résultats dun autre agent. Sinon, laction individuelle dun agent est considéré comme nulle (concurrence parfaite). La théorie des jeux pourra être utilisée dès quon aura un nombre restreint dagents : oligopole, duopole. On va avoir un traitement rationnel de linteraction.
Les applications sont très nombreuses, en économie, économie industrielle, économie internationale (USA, Europe, Japon), en économie du travail (patron, syndicat), en politique, jeux de partis ; en sciences naturelles, biologie (deux populations). On peut analyser toutes les questions liées aux conditions démergence dun accord (issus dune condition dinteraction). Aujourdhui, lagent peut être un agent humain, un animal, une machine.
Historique : Les ancêtres de la théorie des jeux étaient mathématiciens. On évoque Zermelo en 1913 qui a travaillé sur le jeu déchecs et émis le théorème selon lequel le jeu déchecs avait une solution. On considère que le rapport entre économie et théorie des jeux débute en 1944 avec le livre de V. Neumann et Morgenstein, Théorie des Jeux et Comportements Economiques. Cest la première fois quon montre que le conflit peut être mathématiquement analysé. En 1950-1951, John Nash fait apparaître léquilibre de Nash. On va avoir la théorie des jeux coopératifs et non coopératifs. Jusquen 1970, la théorie des jeux reste un domaine autonome avec peu dinfluence sur léconomie, mis à part dans le livre de T. Schelling, The Strategy of conflict. A partir des années 70, il y a un fort développement en économie car le problème de linformation des agents devient central. La confirmation de la réussite est le prix Nobel déconomie à Selten, Haisanyi et Nashen en 1994.
Importance économique : On a un renouvellement de la microéconomie, passage du monde walrassien au monde de linteraction entre agents. On passe dune concurrence parfaite à une concurrence imparfaite. On va avoir des situations déquilibre multiple. On va au lieu davoir une construction économique grandiose, léquilibre général, on a une série de cas-types, dhistoriettes.
Plan :
I- Notions de base
II- Recherche de solutions (équilibres)
III- Applications
Bibliographie :
Yildizoglu, Introduction à la théorie des jeux, Dunod 2004
Umbhaver, Théorie des jeux, Vuilbert 2004
Rasmusen, Jeux et info, De Boeck 2004
Chapitre 1 : Notions de base
Section 1 : Définitions préalables.
A- Distinction entre jeux coopératifs et jeux non coopératifs.
Aujourdhui, il y a deux branches distinctes en théorie des jeux.
Jeux coopératifsJeux non coopératifsUnité danalyse : coalition (groupes de joueurs agents individuels). La coopération résulte du fait que les agents sont tenus de signer des accords contraignant sur les stratégies mises en uvre. La coalition forme un but commun. Les firmes forment un cartel dans le but de maximiser leurs produits joints pratiquent un jeu coopératif.Unité danalyse : lagent individuel recherche à maximiser son intérêt, respect règles du jeu. Si il y a compétition entre agents, le jeu ne peut avoir lieu que si les intérêts les meilleurs de chaque individu pris séparément sont en uvre. Les firmes en situation de monopole à la Cournot sont dans un jeu non coopératif.
B- Distinction entre jeux à information complète et jeux à information incomplète.
Il faut introduire lidée de structure du jeu. Cest le nombre de joueurs, les actions ou stratégies possibles, les règles et les gains. Si il y a une information pour chacun des joueurs sur lensemble de la structure du jeu, on est dans un jeu à information complète. Si au moins un joueur na pas dinformations sur un élément de la structure du jeu, on est dans un jeu à informations incomplètes. Ici, on examine que des jeux dinformation complète.
C- Distinction entre jeux à information parfaite et jeux à information imparfaite.
La distinction repose sur un seul élément de la structure du jeu, linformation sur les décisions prises par les autres joueurs. Si chaque joueur au moment de jouer connaît les décisions que lautre joueur a prises antérieurement, on est dans un jeu à information parfaite. Si, au contraire, au moins un joueur na pas dinformation sur ce qua joué lautre joueur, on est dans un jeu à information imparfaite. Dans les jeux où il y a des décisions simultanées, on est dans des jeux à information imparfaite.
D- Distinction entre jeux dynamiques et jeux statiques.
Les jeux dynamiques sont les jeux dans lesquels linformation des joueurs évolue au cours du jeu (jeux séquentiels). Au contraire, les jeux dits statiques sont des jeux pour lesquels il ny a aucune évolution de linformation des joueurs au cours du temps.
Section 2 : Présentation des jeux sous forme normale (stratégique).
A- Définition initiale.
Un jeu sous forme normale ou stratégique est une présentation du jeu telle quon suppose que les joueurs jouent simultanément et disposent de la même information au moment où ils jouent. Ce sont donc des jeux à information imparfaite car les joueurs au moment où ils jouent ne savent pas où ils sont dans larbre de décision. Cest donc la caractéristique dinformation qui est importante ici.
B- Définition stricte.
Un jeu sous forme normale ou stratégique est défini par les éléments suivants :
EMBED Equation.3 = { N, S, EMBED Equation.3 }
Le jeu va être défini par un ensemble de joueurs dont les noms sont énumérés dans lensemble I.
I = { 1, 2,
, N }
Chaque joueur i, avec i EMBED Equation.3 N dispose dun ensemble de stratégies EMBED Equation.3 . EMBED Equation.3 est lensemble de toutes les stratégies disponibles de i. Si EMBED Equation.3 indique une stratégie particulière choisie par je joueur i. Alors, lensemble des stratégies du joueur i va être la liste de toutes les stratégies disponibles pour ce joueur.
EMBED Equation.3 = { EMBED Equation.3 }
où ni est le nombre de stratégies disponibles pour le joueur i.
On pose s = ( EMBED Equation.3 )
La liste des stratégies choisies par chaque joueur. Cette liste est appelée profil de stratégies. Chaque joueur a une fonction de paiement, EMBED Equation.3 , qui assigne à chaque profil de stratégies un nombre réel EMBED Equation.3 (s). Chaque fonction de paiement EMBED Equation.3 correspond à un vecteur à N dimensions.
S = ( EMBED Equation.3 )
Et lui assigne un nombre réel EMBED Equation.3 (s)
Précisions :
Bien distinguer lensemble des stratégies EMBED Equation.3 qui est lensemble des stratégies disponibles pour un joueur particulier i ; et un profil de stratégies s qui est une liste des stratégies particulières choisies par tous les joueurs. Normalement, on assure que chaque joueur a un nombre fini de stratégies mais cette hypothèse peut être levée, par exemple en économie industrielle quand on suppose que la firme a un choix de prix infini (non négatif). La notation { } indique un ensemble dans lequel lordre des éléments na aucune importance. La notation ( ) indique un ensemble où un vecteur dans lequel lordre des éléments importe. Dans un vecteur qui établira la liste des stratégies, la première stratégie sur la liste sera celle du joueur 1, puis du joueur 2,
On peut introduire dans le jeu un joueur quon peut appeler nature et qui sera un pseudo-joueur qui jouera aléatoirement (par exemple monopole). Dans la théorie des jeux sous forme normale ou autre, les joueurs sont rationnels, cest-à-dire respectent laxiomatique de la microéconomie en univers certain ou incertain. Les préférences des joueurs ont des propriétés qui permettent de traduire les issues, les solutions dun jeu en terme numérique. Un peut désigner un nombre appelé utilité à chaque solution du jeu.
C- Exemples : jeux sous forme normale
1- Jeu du dilemme du prisonnier
Joueur 1 Joueur 2DénonceSe taitDénonce(-10 ; -10)(0 ; -12)Se tait(-12 ; 0)(-1 ; -1)
On suppose que deux individus ont été arrêtés avec présomption davoir commis ensemble un crime. Ils sont placés séparément en cellules et la police donne à chacun deux loption de dénoncer lautre avec la règle suivante :
- Si seulement un des deux décide de dénoncer, il est libre alors que lautre prend douze ans.
- Si les deux se dénoncent, ils prennent dix ans chacun.
- Si aucun ne collabore avec la police, il y a peu de condamnation car il y a un manque de preuve.
Le dilemme réside dans le fait que les deux joueurs gagnent collectivement à se taire mais quindividuellement, ils ont intérêt à dénoncer quel que soit le comportement de lautre.
Joueur 1 Joueur 2PaixGuerrePaix(2 ; 2)(0 ; 3)Guerre(3 ; 0)(1 ; 1)
Remarque :
N = 2
EMBED Equation.3 = EMBED Equation.3 = { paix, guerre }
Quatre profils de stratégie : (P, P) , (P, G), (G, P), (G, G)
Les paiements EMBED Equation.3 = EMBED Equation.3 (p, p) = 2
Les joueurs doivent communiquer et pouvoir prendre des engagements formels.
Ici on a un jeu 2 * 2, chacun des deux joueurs a deux stratégies disponibles.
Le type de jeu dilemme du prisonnier suppose des conditions sur les paiements a < c , a > g > c, b < d et b > h > f
On peut transposer le jeu du dilemme du prisonnier sur les cas de course aux armements, de marchandage politique, de formation de prix doligopole, doffres denchères.
2- Jeu bataille des sexes.
Joueur 1 Joueur 2FootShoppingFoot(3 ; 2)(1 ; 1)Shopping(0 ; 0)(2 ; 3)
Cest aussi un jeu standard. Un jeune couple doit décider dune date où ils font une sortie ensemble. Ils ont déjà anticipé leurs possibilités, soit football, soit shopping. Si ils décident le premier choix, ils se rencontreront au stade à lheure de démarrage du match. Sils décident le second choix, ils se trouvent à lentrée des Nouvelles Galeries à une heure précise, on suppose quils nont pas de téléphone portable et que la décision doit être prise séparément au même moment. Les préférences de chacun des individus sont les suivantes ; la fille veut aller au match, et le garçon faire du shopping. Dans tous les cas, ils préfèrent faire quelque chose ensemble plutôt quêtre séparés. Les paiements sont liés à ces préférences. Ce qui caractérise le jeu cest que les situations où ils sont ensemble (F, F) et (S, S) sont les plus satisfaisantes. Ce jeu va être aisément transposable à des problèmes économiques de standard technologique.
Firme 1 A ou B Firme 2 A ou B EMBED Equation.3 Entente sur A ou sur B sinon coût important.
3- Jeux à trois stratégies et à somme nulle (papier, caillou, ciseaux).
Joueur 1 Joueur 2PapierCaillouCiseauxPapier(0 ; 0)(+1 ; -1)(-1 ; +1)Caillou(-1 ; +1)(0 ; 0)(+1 ; -1)Ciseaux(+1 ; -1)(-1 ; +1)(0 ; 0)
Si le joueur 1 gagne, le joueur 2 perd.
Si le joueur 1 nul, le joueur 2 nul.
Si le joueur 1 perd, le joueur 2 gagne.
4- Jeu pile ou face.
Joueur 1 Joueur 2PileFacePile(+1 ; -1)(-1 ; +1)Face(-1 ; +1)(+1 ; -1)
Chacun des joueurs écrit son choix sur on bout de papier. Si ils font la même chose 2 donne à 1. Sinon 1 donne à 2.
5- Jeu dit « poule mouillée ».
Joueur 1 Joueur 2RAR(1 ; 1)(0 ; 2)A(2 ; 0)(-1 ; -1)
Deux voitures se dirigent lune en direction de lautre à forte vitesse dans une rue trop étroite pour quelles se croisent sans être endommagées à moins quun des conducteurs ne ralentisse. Si un conducteur ralentit alors que lautre continue à la même vitesse, cest celui qui na pas ralenti qui gagne, si les deux ralentissent, le degré damour propre sera non modifié pour les deux joueurs et si aucun des deux ne ralentit, il y aura des conséquences négatives pour les deux.
6- Jeu dentrée.
Joueur 1 Joueur 2BatailleConcessionNentre pas(0 ; 2)(0 ; 2)Entre(-1 ; -1)(+1 ; +1)
On considère deux firmes qui veulent être présentes sur un marché. La firme 2 est déjà présente sur le marché alors que la firme 1 se demande si elle va rentrer ou pas face à la réaction de la firme 2 qui peut soit se battre (guerre des prix) ou au contraire faire des concessions.
Remarque :
Dans un jeu symétrique, les paiements des joueurs sont strictement équivalents le long de la diagonale du jeu. Quand on est dans un jeu symétrique, la stratégie rationnelle du joueur 1 est automatiquement celle du joueur 2.
Bien sur, un jeu de structure simple ne peut expliquer la complexité de la réalité économique mais le but de la théorie des jeux nest pas de remplacer le décideur et lui fournir la solution à son problème dinteraction, mais cest seulement indiquer que certains propriétés dun contexte stratégique, contrairement à dautres contextes, sont susceptibles davoir un impact sur les résultats. Il suffit denrichir la stratégie pour guider laction. Un langage strict existe dans la théorie des jeux pour décrire différents contextes stratégiques. On a donc une cohérence pour traiter des problèmes de nature différente mais identiques sur le plan stratégique. Il faut faire attention aux exigences de rigueur qui permettent de passer dun contexte économique à un jeu, et aux solutions éventuelles.
Section 3 : Forme extensive.
A- Présentation.
Cest la forme de présentation dun jeu la plus rigoureuse, dont la forme normale nest quun cas particulier. On présente le jeu comme si les joueurs choisissaient en même temps, donc disposent du même type dinformations. Dans la présentation sous forme extensive, les joueurs jouent à plusieurs étapes, le temps intervient ; les décisions sont donc séquentielles. Linformation est les actions jouées possibles à chaque étape sont alors plus précises. Cest la forme la plus fondamentale et la plus complète pour représenter le jeu. La forme normale est apparemment plus simple mais elle est trompeuse lorsque le jeu devient complexe et la spécification totale du jeu est seulement rendue par la forme extensible. Le jeu sous forme extensible va être représenté par un arbre avec un sommet initial, des sommets intermédiaires et des sommets terminaux, des arcs (branches) qui lient sommets de décision aux sommets terminaux pour décrire les actions dun joueur sur un sommet de décision précis.
Exemple :
Un avion doit aller à New York. Mais un terroriste est dans lavion pour le détourner à Cuba. La menace repose sur le fait quil peut faire sauter lavion avec une bombe. On suppose ici que chaque joueur sait ce que lautre va faire quand cest à son tour de jouer. On associe les gains sur les sommets terminaux. En dehors de ces arcs et de ces sommets, on va représenter lensemble des actions sous la forme suivante EMBED Equation.3 = {B, N, B} avec ici le fait que lensemble des actions est le même pour deux sommets pour le joueur terroriste mais ce nest pas obligatoire. Les paiements sont associés à chaque sommet terminal.
B- Ecriture stricte.
On va écrire le jeu sous une forme plus stricte avec six éléments :
- Une liste de N EMBED Equation.3 1 joueurs, indexés par i = 1, 2,
, n (0 si nature)
- Un ensemble de sommets formant une partition : V = { Vo } u V u Vt
Vo na pas de prédécesseur : sommet initial.
V \ Vt cest-à-dire V privé de Vt : ensemble des sommets de décision.
Vt ensemble des sommets terminaux.
EMBED Equation.3 Il y a un arbre déléments.
EMBED Equation.3 Un joueur est associé à chaque sommet V \ Vt. Il doit prendre alors une décision. Cest à son tour de jouer (un joueur peut être associé à plusieurs sommets). Il y a donc un ordre du jeu.
EMBED Equation.3 Pour chaque sommet de décision V, il y a un ensemble fini dactions A (V) (non de stratégies). Chaque action mène à un unique successeur immédiat de V. Ainsi, on donne un nom à chaque arbre de larc.
EMBED Equation.3 Des ensembles dinformations qui sont une partition des sommets de décision V \ Vt. On les introduit pour indiquer que le joueur peut être amené à jouer sans savoir les décisions prises aux étapes antérieures du jeu (alors jeu à information imparfaite). Dans ce cas, il ne sait distinguer entre deux sommets de larbre (ou lindique alors par un trait pointillé ou « patate » liant les deux sommets).
Donc un ensemble dinformations pour un joueur est une collection de sommets de décisions telle que :
- Cest à son tour de prendre sa décision.
- Si on est dans un jeu à information imparfaite, on est en présence de singleton. Sinon, ils peuvent grouper plusieurs sommets de décisions.
EMBED Equation.3 A chaque sommet terminal dans lensemble Vt, on associe des paiements EMBED Equation.3 pour chacun des joueurs.
Quelques précisions :
Différence entre actions et stratégies : on a employé dans la définition le terme action car dans un jeu à forme extensive, la définition dune stratégie est plus élaborée que dans la forme normale. En effet, dans la forme normale, chaque joueur possède un seul ensemble dinformations. Donc ce quon appelle stratégie pour le joueur i dans un jeu sous forme extensible va spécifier laction que prend le joueur i à tous les ensembles dinformation où cest à son tour de jouer. Ainsi dans notre jeu pilote terroriste, le joueur 1 pilote a deux stratégies New York ou Cuba. Dans ce cas, lensemble de ces actions est équivalent à lensemble de ses stratégies car il nest appelé à jouer quune seule fois au sommet initial. Par contre, le joueur 2 a quatre stratégies possibles à partir de deux actions St = { (B ; B) ; (B ; NB) ; (NB ; B) ; (NB ; NB)} dans lequel la stratégie (B ; NB) indique que le joueur 2 opte pour laction bombe si le joueur 1 va à New York et pour laction non bombe si le joueur 1 va à Cuba. Donc, dans la stratégie, le premier élément se réfère à laction du terroriste au sommet de EMBED Equation.3 c ; la deuxième à laction du terroriste au sommet de EMBED Equation.3 n. Une stratégie est une fonction qui associe à chaque ensemble dinformations une action.
Sous forme extensive, les sommets et les arcs dun jeu doivent respecter certaines conditions, par exemple, il faut une racine unique du jeu, on interdit les cycles (boucles), puisque, dans ce cas, il ny aura pas dissues au jeu. Donc cela veut dire que toute partie du jeu traverse un ensemble dinformations quune seule fois. Enfin, on exclut aussi les situations où il y a deux arcs ou plus conduisant au même sommet.
C- Exemples et passage de la forme normale à la forme extensive.
1- Réécriture pile face.
Joueur 1 Joueur 2PileFacePile(+1 ; -1)(-1 ; +1)Face(-1 ; +1)(+1 ; -1)
SHAPE \* MERGEFORMAT SHAPE \* MERGEFORMAT
On peut représenter le jeu sous forme extensive même si en général un jeu sous forme normale correspond à différents jeux sous forme extensive.
2- Récriture jeu pilote terroriste.
Pilote TerroristeB ; BB ; NBNB ; BNB ; NBNew York-1 ; -1-1 ; -12 ; 02 ; 0Cuba-1 ; -11 ; 1-1 ; -11 ; 1
3- Autre cas : Elections ONU.
On doit élire un secrétaire général de lONU sur la période 1997-2001. Il y a un premier candidat B et un deuxième candidat A. B était secrétaire général dans la période antérieure, mais fait face à lopposition américaine. Une candidate H, premier ministre finlandais a la faveur des Etats-Unis. Mais les pays africains souhaitent un membre issu de leur continent. Pour analyser lélection, on tente de construire un modèle simple de théorie des jeux. On considère quil y a seulement deux votants, USA et Afrique. On considère que les Etats-Unis votent dabord en émettant un veto sur un des trois candidats. LAfrique joue et émet un veto sur lun des deux candidats restants. On suppose que les préférences des joueurs sont les suivantes, pour les USA H > A > B ; pour lAfrique, B > A > H. On suppose les paiements suivants, on gagnera 1 si son meilleur candidat est élu, 0 si cest le deuxième choix, -1 si cest le troisième choix. Le problème est de représenter le jeu sous forme extensive et sous forme normale.
Section 4 : Stratégies pures / mixtes.
A- Définition :
Les stratégies mixtes sont une classe différente des stratégies pures. Pour le moment, nous navons eu à faire quà des stratégies pures. Une stratégie mixte, cest pour le joueur une distribution de probabilités sur ces stratégies pures. Si un joueur i a n stratégies pures, une stratégie mixte sera un vecteur de probabilités (p1, p2,
, pn) avec pk EMBED Equation.3 0, k = 1,
, M et EMBED Equation.3 .
Une stratégie pure est finalement aussi une stratégie mixte dans le sens où p1 = 1 et pk = 0. Tout type de jeu a des stratégies pures et des stratégies mixtes alors quil existe des stratégies spécifiques en jeux sous forme extensive.
B- Evaluation.
Comment évaluer des paiements associés à des stratégies mixtes ? On va utiliser le premier théorème de lutilité espérée. Une fonction dutilité sur une distribution de probabilités peut être décrite comme lutilité espérée du résultat issu de cette loterie (transitivité, complétude). Donc si on a une loterie avec n résultats possibles x1, x2,
, xn et une liste associée de probabilités pour chacun des résultats, alors le théorème nous dit que lutilité de cette loterie est égale à lutilité espérée. On retrouve les fonctions dutilité habituelles mais en univers incertain. Sous certaines restrictions, on peut représenter les fonctions dutilité sur les loteries par les fonctions dutilité sur les gains. Ceci permet une comparaison entre distribution de probabilités. Sur cette base, il faut donc deux opérations pour déterminer le paiement anticipé. On va pondérer le paiement de chaque stratégie pure par la probabilité avec laquelle elle est jouée, puis on ajoute les paiements par leur probabilité.
1- Jeu bataille des sexes.
Joueur 1 Joueur 2FootShoppingFoot(3 ; 2)(1 ; 1)Shopping(0 ; 0)(2 ; 3)
Supposons que lhomme fasse du shopping avec une probabilité 1/3 et aille voir un match avec une probabilité 2/3 ; et que la femme joue en stratégie pure football. La probabilité que les deux joueurs aillent voir un match est 2/3 ; la probabilité pour que lhomme soit seul pour faire du shopping est 1/3.
Paiement de lhomme = 2/3 * 2 + 1/3 * 1 = 5/3.
Si la femme joue en stratégie pure shopping
Paiement de lhomme = 1/3 * 3 = 1
2- Exemple 2 :
SHAPE \* MERGEFORMAT
On sait que le produit de la probabilité de chaque stratégie est la probabilité pour que les deux individus se retrouvent en un même lieu. Le paiement anticipé de lhomme sera (3 * 1/3) + (1 * 1/6) = 7/6.
A quoi ces résultats servent-ils ? Pourquoi un joueur raisonnerait-il en mixte plutôt quen pur ? Il y a deux raisons :
EMBED Equation.3 Dordre technique, parce quon peut montrer que les gains du joueur sont supérieurs parfois en mixte quen pur. En plus, on peut trouver en stratégie mixte des solutions quon ne trouve pas en stratégie pure. Dans le jeu pile face, il ny a pas de solutions en stratégie pure. Or ce jeu, en stratégie mixte, trouve une solution. Plus généralement, on vérifie que dans un jeu où le nombre de joueurs et de stratégies pour chacun des joueurs est fini, lensemble des stratégies mixtes garantit toujours, de par leurs propriétés mathématiques, des solutions.
EMBED Equation.3 Dordre économique. Elle peut se justifier par plusieurs concepts :
- En finances, par un choix aléatoire on obtenait des résultats supérieurs aux modèles élaborés par des choix en stratégie pure (exemple placement en A ou en B).
- Dans une entreprises, ouvriers dentretien / chef datelier. Il y a un conflit et les ouvriers dentretien cherchent à faire respecter certaines négligences aux chefs. Ils cherchent donc une stratégie, sils laissent passer des petites négligences nombreuses, ils vont se faire remarquer, de même que de grosses négligences ponctuelles. Selon Unbauer, le choix aléatoire est celui où ils risquent le moins de se faire remarquer.
Chapitre 2 : Notions déquilibre
Une X quon a défini le jeu (passage de la situation économique à une historiette qui détermine les règles du jeu), on peut chercher les différents profils de stratégie. Dans les jeux Z * Z, il y a quatre profils de stratégie, et on va faire une prévision de lissue du jeu.
Exemple : Est-ce que le jeu guerre / paix se finit-il ?
Donc la théorie des jeux prétend de plus en plus offrir une prévision de lissue du jeu. Pour faire ces prévisions on a besoin de méthodes et de définitions dalgorithmes pour rapprocher lensemble de tous les profils possibles vers un petit nombre de profils quon va appeler équilibre. Il va falloir spécifier les notions déquilibre et la théorie des jeux va prendre de nouvelles notions déquilibre.
Idéalement on aimerait trouver une méthode qui sélectionne un seul profil et non un seul équilibre, dans ce cas-là, le profil sera unique. Cependant, en théorie des jeux les équilibres ne sont pas uniques et parfois on ne trouve pas déquilibre.
On rappelle quon profil de jeux sécrit s = (s1, s2, s3,
, si,
, sn).
On notera s-i la liste de ce que tous les joueurs autre que i jouent.
Section 1 : Equilibre en forme normale.
Deux types :
- Notion de dominance.
- Notion déquilibre de Nash.
A- Dominance.
1- Stratégie dominante.
Une stratégie particulière EMBED Equation.3 est appelée stratégie strictement dominante par le joueur i si le paiement lié à cette stratégie est strictement supérieur au paiement de tout autre stratégie sans tenir compte de la stratégie choisie par les autres joueurs, ainsi :
EMBED Equation.3 pour tout si et tout s-i.
Exemple :
Jeux guerre / paix
Pays 1 Pays 2GuerrePaixGuerre(+1 ; +1)(+3 ; 0)Paix(+3 ; 0)(+2 ; +2)
On peut montrer que s1 = guerre est une stratégie dominante pour le joueur 1.
Preuve :
Recensons toutes les actions possibles jouées par le joueur 2
- Si le joueur 1 joue s1 = guerre alors EMBED Equation.3 (guerre, guerre) = 1 > 0 = EMBED Equation.3 (paix, guerre)
- Si le joueur 2 joue s2 = paix alors EMBED Equation.3 (guerre, paix) = 3 > 2 = EMBED Equation.3 (paix, paix)
Exemple :
LeftRightTop76Bottom73
La stratégie « top » est faiblement dominante pour le joueur 1 sur la stratégie « bottom ».
Une stratégie particulière EMBED Equation.3 est appelée stratégie faiblement dominante pour un joueur i sur une autre stratégie EMBED Equation.3 , si
EMBED Equation.3 pour tout s-i
EMBED Equation.3 pour tout EMBED Equation.3 -1.
La stratégie EMBED Equation.3 -1 fait au moins aussi bien que EMBED Equation.3 -1 contre chaque stratégie des autres joueurs et elle fait strictement mieux contre certaines dentre elles EMBED Equation.3 -1
2- Equilibre en stratégie dominante.
Le profil de stratégies EMBED Equation.3 où EMBED Equation.3 pour tout i = 1, 2,
, N est dite équilibre en stratégies dominantes si EMBED Equation.3 est une stratégie dominante pour chaque joueur i.
Exemple :
Jeu guerre / paix
- Si le joueur 2 joue s1 = guerre alors EMBED Equation.3 (guerre, guerre) = 1 > 0
- Si le joueur 2 joue s2 = paix alors EMBED Equation.3 (guerre, paix) = 3 > 2 = EMBED Equation.3 (paix, paix)
Dans ce cas là, la solution du joueur 2 cest (paix, paix)
Donc on peut montrer que dans le jeu droite / gauche, la stratégie faiblement dominante du joueur 1 « top » et pour le joueur 2 la stratégie faiblement dominante est « left ».
Le profil déquilibre en stratégie dominante sera (T, L) = (7, 3)
3- Limites.
Il existe des situations de jeu pour lesquelles on narrive pas à identifier un équilibre en stratégie dominante.
Exemple :
Jeu bataille des sexes
Jacob RachelOpéraFootOpéra(2 ; 1)(0 ; 0)Foot(0 ; 0)(1 ; 2)
On veut montrer quil ny a pas déquilibre en stratégie dominante dans certains jeux.
Preuve :
Il suffit pour montrer que lun des joueurs na pas de stratégie dominante alors il ny aura pas déquilibre en stratégie dominante.
Jacob : Si Jacob choisit sR = opéra, EMBED Equation.3 (w, w) = EMBED Equation.3
Si Rachel va au foot, sR = EMBED Equation.3 alors Jacob choisira EMBED Equation.3 car EMBED Equation.3 = 1 > 0 = EMBED Equation.3
Donc le joueur 1 na pas de stratégie dominante.
Labsence déquilibre en stratégie strictement dominante :
Joueur 1 Joueur 2121(1 ; -1)(-1 ; 1)2(-1 ; 1)(1 ; -1)3(-2 ; 5)(-3 ; 2)
Joueur 1 Joueur 2121(1 ; -1)-12(-1 ; 1)13(-2 ; 5)-3
4- Passages à stratégies dominées.
Définition : Une stratégie EMBED Equation.3 est strictement dominée par un joueur i par la stratégie EMBED Equation.3 si elle assure un paiement plus faible quune autre stratégie, quel que soit le comportement des joueurs autre que i.
EMBED Equation.3 pour tout EMBED Equation.3 quel que soit EMBED Equation.3 .
De même, on aura une stratégie faiblement dominée si une stratégie alternative fait au moins aussi bien quelle tout le temps et quelque fois strictement mieux.
5- Equilibre par élimination itératives stratégie dominées.
On peut obtenir un équilibre si en éliminant successivement les stratégies dominées dans le choix rationnel des agents, il subsiste un seul profil quon appellera équilibre par diminution itérative des stratégies dominées.
LeftRightUp(1 ; 1)(0 ; 1)Middle(0 ; 2)(1 ; 0)Down(0 ; -1)(0 ; 0)
Down est faiblement dominée par up. Il lenlève.
Rationnel donc on sait que 1 est rationnel et a viré down. Right est faiblement dominé donc il lenlève.
Rationnel donc on sait que 2 a viré right. Il choisit up.
Profil déquilibre : (UP, LEFT)
On a au moins une stratégie faiblement dominée par le joueur 1 down.
Pour le joueur 2, la stratégie right est dominée faiblement.
Up => (U, L)
Exemple : Elections ONU.
HAAHHAHABHHBBAABHABABBHBA(-1 ; 1)(-1 ; 1)(-1 ; 1)(1 ; -1)(1 ; -1)(1 ; -1)(1 ; -1)(1 ; -1)B(1 ; -1)(0 ; 0)(1 ; -1)(0 ; 0)(1 ; -1)(0 ; 0)(1 ; -1)(0 ; 0)H(-1 ; 1)(-1 ; 1)(0 ; 0)(0 ; 0)(-1 ; 1)(-1 ; 1)(0 ; 0)(0 ; 0)
USA : H > A > B
Afrique : B > A > H
Partons avec lAfrique :
Entre B et H, B est préféré
Entre A et H, A est préféré
Entre A et B, B est préféré
HHA domine toutes les autres stratégies.
Le jeu devient :
USAAfriqueA(-1 ; 1)B(0 ; 0)H(-1 ; 1)
A et H sont dominés par la stratégie B. La meilleure chose que les Etats-Unis puissent faire, cest user de leur veto pour B.
LAfrique met son veto sur A.
Kofi Annan est élu.
6- Limites.
La recherche déquilibre par élimination ditérations est simple mais elle présente trois problèmes :
-> Problème de la définition de la rationalité :
Aucun joueur ne joue une stratégie dominée, cest une hypothèse rationnelle.
Aucun joueur ne joue une stratégie dominée avant que les stratégies dominées des autres aient été éliminées est une hypothèse rationnelle.
Par contre, aucun joueur ne joue une stratégie qui devient dominée après cinquante coups délimination des stratégies dominées semblent moins rationnelles. Ceci suppose que chaque joueur saccorde à ce que les autres soient rationnels à chaque round dordre supérieur. Il ny a donc pas de droit à lerreur. Cette hypothèse est appelée hypothèse de « connaissances communes ». Un fait F est une connaissance commune de deux joueurs i et j si et seulement si i sait F, j sait F, i sait que j sait F, j sait que i sait F, i sait que j sait que i sait F
Les agents risquent de faire des erreurs. On retrouve le même problème quen microéconomie sur la rationalité des agents, et le problème de réalisme des hypothèses.
-> Dans le processus délimination itératif des stratégies dominées, lordre importe quand la domination est faible
Joueur 1 Joueur 2LeftRightTop(0 ; 0)(0 ; 1)Bottom(1 ; 0)(0 ; 0)
Le joueur 1 élimine top.
Le joueur 2 élimine left.
Le joueur 1 équilibre (B, R) = (0 ; 0).
-> Dans certains cas, il ny a pas de solutions.
Joueur 1 Joueur 2LeftRightTop(1 ; 1)(0 ; 0)Bottom(0 ; 0)(2 ; 2)
Il ny a pas de stratégie dominante ni de stratégie dominée.
7- Conclusion :
Il faut donc passer à une autre définition de léquilibre et donc évidemment à un autre algorithme.
Précision : stratégie dominante / dominée. On compare pour le joueur 1 les éléments de chaque ligne entre eux et pour le joueur 2 les éléments de chaque colonne entre eux.
B- Equilibre de Nash.
a- Définition.
En 1951, John Nash (matheux au départ) a fourni la preuve de lexistence dun concept déquilibre qui est devenu la notion la plus couramment utilisée pour analyser les jeux. Cette notion apparaissait implicitement chez Cournot dans léquilibre du duopole.
Un profil de stratégies EMBED Equation.3 , EMBED Equation.3 = ( EMBED Equation.3 où EMBED Equation.3 pour tout i = 1, 2,
, N est dit équilibre de Nash (NE) si aucun joueur ne trouve bénéfice à dévier, étant donné la non déviation de tous les autres de leur équilibre de Nash.
Pour tout i, i = 1, 2,
, n
EMBED Equation.3 pour tout EMBED Equation.3 ; EMBED Equation.3
Si on a inégalité strict, alors léquilibre de Nash est strict donc il y a une unique stratégie.
b- Exemples et intuition dun équilibre de Nash.
Joueur 1 Joueur 2GDH(3 ; 0)(0 ; 1)M(0 ; 0)(3 ; 1)B(1 ; 1)(1 ; 0)
Il ny a pas de dominance.
Lidée de Nash est de constituer une peine danticipation de stratégies telles que si chacun que son adversaire jouer la stratégie qui lui appartient alors il aura intérêt à jouer la stratégie que son adversaire anticipe. Si une telle situation existe, alors les anticipations des joueurs seraient auto-réalisées telles que aucun des deux naurait intérêt à ne pas se conformer à lanticipation de lautre.
Exemple :
Keynes, sur les marchés financiers parlait de « concours de beauté ». Le but du concours de beauté est de trouver la fille la plus belle. Keynes dit que ce nest pas vrai, il ne faut pas trouver la fille la plus belle mais la fille que les autres trouveront la plus belle. Il faut se caler sur lanticipation de lautre.
Le marché financier fonctionne sur lidée quil faut que je trouve la valeur sur laquelle les autres anticipent. On a toujours intérêt à se conformer à lidée de lautre. Chez Keynes, il ny a pas de jeu économique individuel du calcul strictement microéconomique.
Les équilibres en stratégie dominante ou dominée indiquent une solution dans laquelle peu importe ce que lautre fait. On sort de ce que fait lautre. Au contraire ici on se fait une certaine idée de ce que lautre fait. Ici je choisis la stratégie A sans avoir besoin de savoir que A fait mieux que contre toutes les autres stratégies de lautre joueur, jai juste besoin de savoir si a fait mieux contre la stratégie spécifique de mon adversaire. On dit dans ce cas que la stratégie a est une meilleure stratégie « best reply » contre la stratégie connue de lautre stratégie si elle fait mieux que les stratégies contre elle. La stratégie connue veut dire que lon ne sait pas ce que lautre veut jouer. Si deux joueurs jouent une meilleure réponse alors on aura un équilibre de Nash. En dautres termes, si chaque joueur joue un best reply et que les stratégies sont correctes, aucun joueur nest incité à dévier alors je suis en équilibre de Nash.