Chapitre 2 Théorie Des Jeux [PDF]

Zitiervorschau

Chapitre II La Théorie des Jeux Introduction I. Jeux à deux personnes et à somme nulle II. Jeux à deux personnes et à somme constante III.Jeux à deux personnes et à stratégie mixte Page 70

Cours TQG-Aïda Kharrat

Introduction Dans le premier chapitre, nous avons traité la théorie statistique de la décision, où le décideur prend une décision sans tenir compte ni de l’effet de cette décision sur les autres ni de l’effet des décisions des autres sur lui. Or, en réalité, le décideur est supposé agir en concurrence avec d’autres agents et chaque décision prise par une partie (un joueur) influe sur le résultat des autres. Décision en situation de conflit (les intérêts d’un joueur s’opposent à ceux des autres. La théorie des jeux fournit un cadre pour l’analyse des situations concurrentielles où les joueurs utilisent des techniques mathématiques pour déterminer une stratégie optimale de gain. Cours TQG-Aïda Kharrat

Page 71

1. Définition: La théorie des jeux est la discipline mathématique qui étudie les situations où le sort de chaque décideur dépend non seulement des décisions qu’il prend mais également des décisions prises par d’autres décideurs (appelés agents en économie et joueurs en théorie des jeux). En conséquence, le choix “optimal” pour un décideur dépend généralement de ce que font les autres. Parce que chacun n’est pas totalement maître de son sort, on dit que les décideurs se trouvent en situation d’interaction stratégique. En d’autres termes, les agents prennent une décision qui tient compte du fait que les autres vont y réagir. Ces autres prennent en retour en considération la réaction de l’agent dans leurs décisions.

Cours TQG-Aïda Kharrat

Page 72

2. Objectif : L'objectif fondamental de la théorie des jeux est d'expliquer comment chacun des acteurs détermine sa stratégie (aspect positif), ou devrait la déterminer (aspect normatif), en fonction des "règles du jeu", de l'information dont il dispose, et plus généralement des idées qu'il se fait des choix du ou/et des autres joueurs et de leurs conséquences.

Cours TQG-Aïda Kharrat

Page 73

3. Typologie des jeux

Jeux coopératifs et non coopératifs

Jeux simultanés et jeux séquentiels

Jeux finis et jeux infinis

Jeux répétés et jeux instantanées

Jeux à inf parfaite et jeux à inf imparfaite

Jeux à somme nulle et à somme non nulle

Cours TQG-Aïda Kharrat

Page 74

 Jeux coopératifs et jeux non coopératifs L'entité de base de la théorie des jeux est le joueur. Un joueur peut être interprété comme un individu seul ou un groupe d'individus prenant une décision. Une fois que nous avons défini l'ensemble des joueurs, nous pouvons distinguer deux types de modèles : les jeux dont les éléments de base sont les actions des joueurs individuels et ceux basés sur les actions jointes d'un groupe de joueurs. Les modèles du premier type sont appelés les jeux non coopératifs et ceux de second type, les jeux coopératifs. Cours TQG-Aïda Kharrat

Page 75

 Jeux simultanés et jeux séquentiels Un jeu simultané (ou stratégique) est le modèle d'une situation où chaque joueur choisit son plan d'action complet une fois pour toutes au début du jeu. Par conséquent les choix de tous les joueurs sont simultanés. Ainsi, au moment de faire son choix, le joueur n'est pas informé des choix des autres. Exemple: C'est le cas d'une entreprise qui passe un appel d'offre. Les sociétés qui y répondent donnent leurs réponses en même temps sans savoir ce que les autres ont fait. Un jeu séquentiel, au contraire, spécifie le déroulement exact du jeu; chaque joueur considère son plan d'action non seulement au début du jeu mais aussi chaque fois qu'il doit effectivement prendre une décision pendant le déroulement du jeu. Exemple: Le jeu d’échec.

Cours TQG-Aïda Kharrat

Page 76

 Jeux finis et jeux infinis: On dit qu’un jeu est fini lorsque l’ensemble des stratégies de chacun des joueurs est fini. Le dilemme du prisonnier est un jeu fini car chacun des joueurs n’a que deux stratégies possibles. En revanche, le jeu du duopole de Cournot n’est pas un jeu fini, car chaque entreprise choisie la quantité de bien qu’elle produit dans l’ensemble des réels positifs.

Les entreprises sont en concurrence par rapport à leurs volumes de production

Cours TQG-Aïda Kharrat

Page 77

Exemple: dilemme du prisonnier  

Deux prisonniers interrogés séparément Deux possibilités: parler (accuser l’autre) ou se taire. – Si les deux se taisent (S,S), pas de preuve, peine minimale d’un an chacun – Si un des deux accuse l’autre, il est libéré et l’autre a la peine maximum (8 ans) – Si les deux s’accusent, peine moyenne pour les deux (5 ans)

Cours TQG-Aïda Kharrat

Parle

Silence

Parle

(-5, -5)

(0, -8)

Silence

(-8, 0)

(-1, -1) Page 78

 Jeux répétés et jeux instantanées Jeu instantané : Ce type de jeu ne se joue qu'une fois ou un nombre limité de coups. Il n'y a donc pas, de la part des participants, un apprentissage des finesses du jeu.

Jeu répété: Dans la réalité, afin de mettre en pratique la théorie des jeux, les joueurs jouent le même jeu de nombreuses fois. Malgré le changement des conditions du jeu (gain, joueurs), on considère que c'est le même jeu.

Cours TQG-Aïda Kharrat

Page 79

 Jeux à information parfaite et jeux à information imparfaite  Si, lors d'une étape du jeu, le joueur connaît tous les choix

entrepris par les autres participants alors on dit que ce jeu est à information complète ou parfaite.  Informations incomplètes ou imparfaites : Contrairement à

la situation précédente, le joueur peut ne pas être au courant des stratégies de ces concurrents. Ou bien, le joueur ne sait pas les situations précédentes des autres joueurs.

Cours TQG-Aïda Kharrat

Page 80

 Jeux à somme nulle et jeux à somme non nulle  Un jeu de somme nulle est un jeu où la somme des gains de

tous les joueurs est égale à 0. Cela signifie donc que le gain de l'un constitue obligatoirement une perte pour l'autre. Par exemple si l’on définit le gain d’une partie d’échec comme 1 si on gagne, 0 si la partie est nulle et -1 si on perd, le jeu d’échec est un jeu à somme nulle. Nous consacrons la suite de ce chapitre au dernier type de jeu cidessus mentionné, à savoir jeux à somme nulle et jeux à somme non nulle. La théorie des jeux est généralement divisée selon le nombre de joueurs (2 ou plus). Nous nous limitons dans ce cours au cas de deux joueurs.

Cours TQG-Aïda Kharrat

Page 81

I- Jeux à deux personnes et à somme nulle

Page 82

Cours TQG-Aïda Kharrat

1. Caractéristiques:  Il y a deux joueurs I et II;  Le joueur I doit choisir parmi m stratégies; le joueur II

doit choisir parmi n stratégies;  Si le joueur I choisi la stratégie i et le joueur II la

stratégie j, le joueur I gagnera aij et le joueur II perdra

aij (le gain de l’un est une perte pour l’autre).  Il est supposé que chaque joueur connaisse exactement

les profits pour chaque combinaison possible des stratégies disponibles pour chaque joueur.

Cours TQG-Aïda Kharrat

Page 83

Ce jeu à deux joueurs et à somme nulle est représenté par la matrice suivante:

Exemple: a12 est un gain pour le joueur I lorsqu'il joue la stratégie 1 et le joueur II joue la stratégie 2 Cours TQG-Aïda Kharrat

Page 84

Application: Soient deux entreprises A et B qui veulent se partager le marché d'un certain produit. La matrice suivante représente les parts du marché (en %) obtenue par A alors B perd la part que A gagne. Stratégies de B x

y

z

Gain Min de A

1

80

40

75

40

2

70

35

30

30

80

40

75

Stratégies Stratégies de A

Perte maximale de B

max

min Si A choisi la stratégie 1 et B la stratégie x, alors A gagne 80 % et B perd 80 % (donc il gagne 20% restant de 100%). Cours TQG-Aïda Kharrat

Page 85

Pour toute combinaison de stratégies des joueurs A et B, la somme des gains (revenus) des 2 joueurs est nulle donc ces 2 joueurs ont des intérêts qui s'opposent directement.  Le joueur A va essayer de maximiser ses gains alors que le

joueur B va essayer de minimiser ses pertes.

 Si A choisit la stratégie 1, alors que B choisira la stratégie y

ce qui procure un gain de 40 % pour A.

 Si A choisit la stratégie 2, alors que B choisira la stratégie z

ce qui procure un gain possible de 30 % pour A.

A choisira la stratégie 1 avec un gain max possible de 40 contre la stratégie 2 avec un gain de 30. Cours TQG-Aïda Kharrat

Page 86

 Si l'entreprise B choisit la stratégie x, alors A choisira la

stratégie 1 donnant une perte de 80 pour B.

 Si l'entreprise B choisit la stratégie y, alors A choisira la

stratégie 1 donnant une perte de 40 pour B.

 Si l'entreprise B choisit la stratégie z, alors A choisira la

stratégie 1 donnant une perte de 75 pour B.

B choisit la stratégie y qui minimise ses pertes possibles (contre 80 et 75 pour x et z).

Cours TQG-Aïda Kharrat

Page 87

il s'agit du critère maxmin pour les gains ou minmax pour les pertes qui supposent que les décideurs sont pessimistes quant à l'environnement de la décision. Il est important de noter qu'en général le maxmin (minmax) donne la solution optimale pour chaque joueur tant que chaque partie utilise son principe. Il s'agit d'un point d'équilibre ou point selle (A joue la stratégie 1 et B la stratégie y). On dit qu'on est en présence d'un point d'équilibre stable ou d'un point selle lorsque la matrice des gains vérifie la relation maxmin = minmax.

Cours TQG-Aïda Kharrat

Page 88

Il en résulte donc une solution où chaque joueur est satisfait par le choix Autrement si A suppose que B essaye de minimiser les gains de A et B suppose que A essaye de maximiser les pertes B alors aucun joueur n'a intérêt à changer son choix il s'agit dans ce cas d'une stratégie pure. Une stratégie pure existe lorsque le problème admet un point d'équilibre (ou un état stable).

Cours TQG-Aïda Kharrat

Page 89

2. La règle de dominance : Dans notre table initiale, il apparaît que la stratégie 1 résulte en un gain max pour A quel que soit la stratégie choisie par B, alors la stratégie 1 domine la stratégie 2. Alors la stratégie 2 peut être éliminée de la table.

B

A

x

y

z

1

80

40

75

2

70

35

30

Pour B, la stratégie x est dominé par y parce que la perte avec x est toujours plus grande que celle avec y quelque soit la stratégie choisie par A, donc x est éliminée de la table, y et z ne se dominant pas.

A ne peut choisir que la stratégie 1 et B choisira la stratégie y qui minimise les pertes à 40 (même solution que précédent). Cours TQG-Aïda Kharrat

Page 90

Notons que le concept de dominance peut être appliqué à n'importe quel jeu à deux personnes et à somme nulle et avec n'importe quel nombre de stratégies. Pour les grandes tables, le rôle de la dominance est de réduire la taille de la table avant de déterminer la stratégie optimale choisie par chaque joueur : on a la même solution du jeu.

Cours TQG-Aïda Kharrat

Page 91

Exemple

stratégie pure yaany fama point d'équilibre

Pour joueur A

B w 1 A

x

y

z

40 80 35 60

2

65 90 55 70

3

55 40 45 75

4

45 25 50 50 Point d’équilibre: A: Stratégie 2 B: Stratégie y

La stratégie 2 domine la stratégie 1

Élimine st 1

La stratégie 2 domine la stratégie 4

Élimine st 4

Pour joueur B La stratégie y domine la stratégie w

Élimine st w

La stratégie y domine la stratégie Z

Élimine st Z

Pour joueur A La stratégie 2 domine la stratégie 3

Élimine st 3

Pour joueur B La stratégie y domine la stratégie x

Élimine st x

 La dominance est aussi valable dans l'évaluation des jeux où il

n'existe pas de point d'équilibre.

Cours TQG-Aïda Kharrat

Page 92

II- Jeux à deux personnes et à somme constante

Page 93

Cours TQG-Aïda Kharrat

Comme dans le cas précédent, les intérêts des deux joueurs sont totalement opposés mais la somme de leurs gains est toujours égale à une constante S. Appelons G(A) et G(B) les gains réalisés par les joueurs A et B, on a G(A) + G(B) = S. Le gain de l'un est d'autant plus grand que celui de l'autre est faible ce qui élimine toute possibilité de coopération entre les deux joueurs.

Cours TQG-Aïda Kharrat

Page 94

On remarque que si on retranche S/2 du gain de chaque joueur, ceci ne modifie pas leurs valeurs relatives: G'(A) = G(A) – S/2 et G'(B) = G(B) – S/2 La somme de leur gain sera: G'(A)+G'(B) = G(A)+G(B) – S/2 – S/2 = 0.

B

Exemple:

A

x

y

z

1

(70,30) (60,40) (55,45)

2

(80,20) (90,10) (35,65)

3

(95,5) (100,0) (50,50)

Ce sont deux gains

Si on retranche S/2 = 50 à chaque entrée dans la table, on obtient un jeu à somme nulle. Cours TQG-Aïda Kharrat

Page 95

Exemple x A

B y

z

1

(20,-20) (10,-10)

(5,-5)

2

(30,-30) (40,-40) (-15,15)

3

(45,-45) (50,-50)

(0,0)

B

A

x

y

z

Pour A:

1

20

10

5

3 domine 2

2

30

40

-15

3

45

50

0

Point d’équilibre:

A: Stratégie 1 B: Stratégie z Cours TQG-Aïda Kharrat

Élimine 2

Pour B: z domine x

Élimine x

z domine y

Élimine y Page 96

III- Jeux à deux personnes et à stratégie mixte

Page 97

Cours TQG-Aïda Kharrat

Il est possible qu'un jeu à deux personnes et à somme nulle ne résulte pas en une sélection de stratégies pures par les 2 joueurs parce qu'il n'existe pas de point d'équilibre, dans ce cas, les joueurs vont choisir des stratégies mixtes. Cas où il n'existe pas de point d'équilibre: Considérons l'exemple suivant où le directeur d'une entreprise et le représentant des travailleurs sont en train de négocier un nouveau contrat d'augmentation des salaires pour une période à venir. La matrice représente donc les gains par l'union des travailleurs (A) et les pertes pour la direction de l'entreprise (B). Evidemment, l'union souhaite maximiser les gains des employés qu'elle représente alors que la direction, elle souhaite minimiser ses pertes. 98

B (direction)

A (union)

Pour A:

w

x

y

z

1 domine 2

Élimine 2

1

75

105

65

45

4 domine 3

Élimine 3

2

70

60

55

40

Pour B:

3 4

80 95

90 100

35 50

50 55

w domine x

Élimine x

y domine w

Élimine w

La matrice précédente peut être réduite en enlevant les stratégies dominées ; on aura donc: B

Il n’existe pas de point d’équilibre Cours TQG-Aïda Kharrat

A

y

z

1

65

45

4

50

55 Page 99

1. Stratégie mixte Chaque joueur essaye de formuler une stratégie qui est indifférente à la stratégie choisie par l'autre. Ceci peut être réalisé en choisissant au hasard, entre différentes stratégies conformément à un plan prédéfini: choisir chaque stratégie avec une certaine probabilité de telle façon que le gain (ou perte) espéré(e) sont égaux peu importe la stratégie choisie par l'autre. Soient:  P : la probabilité que l'union choisisse la stratégie 1 et  1-P : la probabilité que l'union choisisse la stratégie 4.

si la direction choisit la stratégie y, alors le gains espéré de l'union est donné par : P  65  1  P  50  15 P  50 si la direction choisit la stratégie z, alors le gains espéré de l'union est donné par : P  45  1  P   55  10 P  55

Cours TQG-Aïda Kharrat

Page 100

Pour que l'union soit indifférente à la stratégie choisie par la direction, elle espère que son gain espéré soit égal pour chaque stratégie possible de la direction, alors on aura:

P  65  1  P   50  P  45  1  P   55

15 P  50  10 P  55

25 P  5

P = 0,2 et 1 – P = 0,8 Alors l'union choisit la stratégie 1 avec 20 % et la stratégie 4 avec 80 % ce qui résulte en un gain espéré de 53 D = (15x0,2) + 50.

Cours TQG-Aïda Kharrat

Page 101

De même, la direction déterminera ses probabilités comme suit : soit:  P’: la probabilité que la direction choisisse la stratégie y et  1-P’: la probabilité que la direction choisisse la stratégie z









P '  65  1  P '  45  P '  50  1  P '  55

25 P '  10

P' = 0,4 et 1 – P' = 0,6 La direction choisira la stratégie y avec une probabilité de 0,4 et z avec la probabilité 0,6. Cours TQG-Aïda Kharrat

Page 102

Observons que la valeur espérée du jeu est commune: 53, en effet ; Gain espéré de l'union : si la direction choisit y : 0,2 (65) + 0,8 (50) =53 si la direction choisit z : 0,2 (45) + 0,8 (55) =53 Perte espérée de la direction: si l'union choisit 1 : 0.4 (65) + 0.6 (45) = 53 si l'union choisit 4 : 0.4 (50) + 0.6 (55) = 53

une solution d'équilibre est alors atteinte

Note: si le jeu est joué plusieurs fois, conformément au plan de stratégies mixtes, la valeur moyenne du jeu tendra vers la valeur espérée : 53.

Cours TQG-Aïda Kharrat

Page 103

2. Résolution graphique

Gain si l’union choisit la stratégie 1

Stratégie 4

100

100

80

80 Max min

60 40

60 53 40

Gain minimale Joueur II veut minimiser le gain de I

20

1 0.9 0.8 0 0.1 0.2 Probabilité de choisir la stratégie 1

0.7 0.3

0.6 0.4

0.5 0.5

0.4 0.6

0.3 0.7

20

Gain si l’union choisit la stratégie 4

Graphe pour le joueur I: l’Union

Stratégie 1

0.2 0.1 0 0.9 0.8 1 Probabilité de choisir 104 la stratégie 4

En conclusion, l'union (A) choisit la stratégie 1 avec une probabilité de 0.2 et la stratégie 4 avec une probabilité de 0.8. Les lignes pour le graphe de A représentent respectivement les gains maximum possibles pour A pour toutes les combinaisons possibles de stratégies mixtes, si B choisit la stratégie y ou z. Or A, de nature pessimiste supposera que B choisira l'alternative donnant le résultat le plus mauvais pour A, alors, les gains offerts pour A seront représentés par les bornes inférieures des 2 lignes Le joueur A choisira alors une combinaison de stratégie 1 et 4 qui maximise le minimum des gains possibles.

Cours TQG-Aïda Kharrat

Page 105

100

Perte maximale Joueur I veut maximiser la perte du II

80

Stratégie z

100 80

Min max

60

60 53

40

40

20

20

1 0.9 0.8 0 0.1 0.2 Probabilité de choisir la stratégie y

0.7 0.3

0.6 0.4

0.5 0.5

0.4 0.6

0.3 0.7

Perte si la direction choisit la stratégie z

Perte si la direction choisit la stratégie y

Stratégie y

Graphe pour le joueur II: la direction

0.2 0.1 0 0.9 0.8 1 Probabilité de choisir 106 la stratégie z

De même pour B, les 2 lignes représentent les pertes minimales subies par B si A choisit respectivement la stratégie 1 et 4. A choisira l'alternative qui donne la perte maximale pour B, alors les pertes de B seront représentées par les bornes supérieures des 2 lignes, donc B cherchera le minimum des maximums des pertes, ce qui coïncide avec une probabilité de 0.4 de choisir la stratégie y et 0.6 de choisir la stratégie z. Notons que la valeur espérée du jeu est égale à 53 et c'est la même valeur trouvée par l'approche mathématique.

Cours TQG-Aïda Kharrat

Page 107

Lorsque le jeu admet plus que deux stratégies pour un joueur, la méthode graphique peut être utilisée pour déterminer la stratégie mixte du joueur ayant deux alternatives. La stratégie pour l'autre joueur peut alors être obtenue en utilisant l'approche mathématique en écrivant l'égalité des valeurs espérées du jeu pour ce joueur quand l'autre choisit les différentes stratégies.

B

Exemple: A

w

x

y

z

Min

1

80

35

55

50

35

2

20

70

40

60

20

Max 80

70

55

60

Puisque le joueur A possède 2 stratégies seulement, on détermine les stratégies mixte de ce joueur, Cours TQG-Aïda Kharrat

Page 108

Les stratégies mixtes du joueur A: On pose:  P : la probabilité que le joueur A choisit la stratégie 1 et  1-P : la probabilité que le joueur A choisit la stratégie 2. si le joueur B choisit la stratégie w, alors le gains espéré du joueur A est donné par : P  80  1  P   20  60 P  20 si joueur B choisit la stratégie x, alors le gains espéré d joueur A est donné par : P  35  1  P   70  35P  70 si joueur B choisit la stratégie y, alors le gains espéré d joueur A est donné par : P  55  1  P   40  15 P  40 si joueur B choisit la stratégie z, alors le gains espéré d joueur A est donné par : P  50  1  P   60  10 P  60 Ce qui peut être représenté par le graphe ci après : Cours TQG-Aïda Kharrat

Page 109

Stratégie 1

Stratégie 2

Graphe pour le joueur A

100

100

90

90

80

80

70

70

Max min

60

60

50

50

40

40

30

30

20

20

10

10 1 0

0.9 0.1

0.8 0.2

0.7 0.3

0.6 0.4

0.5 0.5

0.4 0.6

0.3 0.7

0.2 0.8

0.1 0 0.9110 1

La meilleure stratégie pour A est de choisir la stratégie 1 avec une probabilité de 0,6 est la stratégie 2 avec une probabilité de 0,4 donnant un gain espéré de 49. Le graphe montre que pour B il n'y a que deux stratégies (x et y) qui servent à la détermination des probabilités de la stratégie mixte de A.

Les stratégies mixtes du joueur B: On pose:  P’ : la probabilité que le joueur B choisit la stratégie x et  1-P’ : la probabilité que le joueur B choisit la stratégie y.

Cours TQG-Aïda Kharrat

Page 111

si le joueur A choisit la stratégie 1, alors la perte espérée du joueur B est donné par : 35 P' + 55 (1 – P' ) si joueur A choisit la stratégie 2, alors la perte espérée du joueur B est donné par : 70 P' + 40 (1 – P') Alors la solution pour B peut être trouvée en écrivant: 35 P' + 55 (1 – P' ) = 70 P' + 40 (1 – P') = 49 50P’ = 15

P’= 0,3

La meilleure stratégie pour B est de choisir la stratégie x avec une probabilité de 0,3 est la stratégie y avec une probabilité de 0,7 donnant une perte espérée de 49. Cours TQG-Aïda Kharrat

Page 112