Théorie des jeux

une introduction
Master 2 GADM
Enseignant Mme Belleili Souici H.

Définition
• La théorie mathématique des jeux est une branche des
sciences économiques
• On est dans une situation de jeux lorsque l’impact de
chaque agent sur les autres agents est « significatif »
• La théorie des jeux vise à étudier formellement ce type
de jeux où le sort de chaque agent participant dans le
jeu, dépend non seulement des décisions qu’il prend
mais également des décisions prises par les autres
agents intervenant dans le jeu.
• Dès lors, le “meilleur” choix pour un agent dépend
généralement de ce que font les autres.

Interaction stratégique
• On parle d’interaction stratégique lorsque
aucun des participants dans l’interaction
n’est maitre de son sort,

1
 Questions à se poser
• Qu'est-ce qu'un individu peut inférer sur
les décisions des autres ?
• Peut-on prédire le choix de chaque
joueur?
• Quel sera le résultat de ces actions ?
• Cela fait-il une différence si le jeu se
déroule plusieurs fois ?

But
• Le mot jeu peut faire penser à des problèmes
banals
• En réalité, on utilise la théorie des jeux dans des
situations très sérieuses:
– Les réglements de faillite,
– L’attribution aux enchères de bandes de fréquence
pour les technologies des réseaux sans fil
– Décisions en matière de développement et de
tarification de produits
– Défense nationale….
5

La théorie du choix rationnel

• Comment modéliser le comportement et les choix des
joueurs ?
• La théorie du choix rationnel est une composante
majeure de la plupart des modèles de théorie des jeux.
• Cette théorie stipule qu'étant données ses préférences,
un joueur choisit la meilleure action parmi celles
disponibles.
• La "rationalité" tient dans la cohérence des actions d'un
joueur avec ses préférences,

2
 suite
• Afin de pouvoir représenter les préférences, il est toutefois
nécessaire de supposer:
– que celles-ci sont complètes sur l'ensemble des actions
possibles : si un joueur doit faire un choix entre deux actions, il
sera toujours capable de dire laquelle il préfère des deux ou si il
est indifférent entre les deux.
– Pour que le problème soit formalisable, il est par ailleurs
nécessaire de supposer des préférences transitives : si l'action a
est préférée à l'action b et b préférée à c alors a devra être
préférée à c. Aucune autre restriction n'est imposée aux
préférences.
– Par exemple, il se peut qu'un joueur ait des préférences
altruistes dans le sens où ses préférences dépendent du bien-
être du ou des autres joueurs.
7

Comment représenter les préférences?

• Une des possibilités est de spécifier pour chaque paire
d'actions, l'action que le joueur préfère ou de noter que
le joueur est indifférent entre les deux actions.
• Alternativement, on peut représenter les préférences par
une "fonction de paiement" qui associe un nombre
(valeur) à chaque action de telle sorte que les actions
avec la plus grande valeur soient celles qui sont
préférées1.

Comment évaluer le résultat

d’un jeu pour un individu?
• Lorsque le gain est monétaire, et dans le cas de
joueurs opportunistes (non altruistes) le joueurs
préfèrent le résultat pour lequel il obtient le plus
d’argent,
• Or tous les jeux n’ont pas de résultats monétaire
• Dans ce cas la fonction de paiement u est
déterminée par le degré de satisfaction du joueur
• La fonction de paiement u représentera les
préférences d’un joueur si pour toute action a et b
(dans l’ensemble des actions possibles)
• u(a)>u(b) si et seulement si le joueur préfère a à b 9

3
 Exemple
• Une personne a le choix entre 3 destinations pour ses
vacances : La Havane, New-York et Venise.
• Elle préfère La Havane aux deux autres, qu'elle juge
équivalentes.
• Ses préférences entre les 3 destinations sont
représentées par n'importe quelle fonction de paiement
qui assigne le même nombre à New-York et Venise et
un nombre plus élevé à La Havane.
• Par exemple, on peut fixer u(La Havane)=1 et u(New-
York)=u(Venise)=0 ; ou
• u(La Havane)=10 et u(New-York)=u(Venise)=1 ; ou
encore u(La Havane)=0 et u(New-York)=u(Venise)=-2,...
10

Synthèse
• La théorie du choix rationnel peut-être exposée
simplement : dans chaque situation, le joueur
choisit parmi les actions disponibles celle qui est
la meilleure selon ses préférences.
• En permettant que le joueurs soient indifférent
entre plusieurs actions, la théorie des choix
rationnels stipule que :
• l'action choisie par le preneur de décision est
au moins aussi bonne (au sens de ses
préférences) que toutes les autres actions
disponibles . 11

Synthèse suite
• Cette théorie apparait également dans la
théorie économique classique du
consommateur et du producteur
• Théorie du consommateur, l’ensemble des
action possibles est l’ensemble des
paniers des biens abordables
• La théorie du producteur l’action a est
préférée à l’action b si a conduit à plus de
profit que b
12

4
 Remarque
• Cependant, en pratique la satisfaction du
joueur ne dépend pas seulement de
l’action qu’il préfère mais des actions
possibles des autres joueurs,
• Dans ce cas un joueur n’est pas capable
de contrôler toutes les variables du jeux
• Ce qui rend la prise de décision plus
complexe
13

Typologie des jeux

• Jeux coopératifs / non coopératifs
• Jeux avec décisions simultanées /
séquentielles
• Jeux statiques/répétés
• Jeux à information parfaite/imparfaite

14

Utilités et préférences
• Supposons que nous avons 2 agents
soient Ag = {i,j}
• Ces agents ont leurs propres intérêts et ils
ont des préférences sur comment est
l’environnement qui les entoure,
• Supposons que W = {w1,w2, …} est
l’ensemble des conséquences (= issues)
sur lesquels l’agent a des préférences
15

5
 Utilités et préférences (suite)

16

Action sur l’environnement

• Il nous faut un modèle de l’environnement
dans lequel agissent les agents.
• Les Agents choisissent une action à
exécuter → il en résulte une issue dans W
• L’issue actuelle (de l’interaction) dépend
de la combinaison des actions

17

Exemple

• Supposons que chaque agent a juste 2 actions qu’il peut exécuter

C(coopérer) et D(ne pas coopérer ou faire défaut)

• Le comportement de l’environnement peut s’exprimer par la fonction

transformation d’états t: Action x Action → W

• Ex1 : t (D,D) = w1, t (D,C) = w2 , t (C,D) = w3 , t (C,C) = w4 .

• Un tel environnement est sensible aux actions des 2 agents.

• Ex2 : t(D,D) = w1 , t(D,C) = w1 , t(C,D) = w1 , t(C,C) = w1 .

• Aucun des 2 agents n’a d’influence sur cet environnement.

• Ex3 : t(D,D) = w1 , t(D,C) = w 2 , t(C,D) = w1 , t(C,C) = w2 .

• L’environnement est contrôlé ici par j.

18

6
 Action rationnelle
• Supposons qu’on est dans le cas où
l’environnement est influencé par les 2 agents et
que leur utilité est comme suit :
ui(w1)=1 ui(w2)=1 ui(w3)=4 ui(w4)=4
uj(w1)=1 uj(w2)=4 uj(w3)=1 uj(w4)= 4

• En remplaçant w1 = (D,D), w2 = (D,C)etc. on a:

• Dans ce cas, les préférences de l’agent i sont:

• « C » est donc le choix rationnel de i. 19

Modélisation d’un jeux

20

Introduction
• Afin de modéliser une situation
d’interaction décisionnelle (jeu) 4 éléments
doivent être précisés:
– L’ensemble des joueurs,
– Les actions possibles pour chaque joueur,
– Les règles du jeu spécifiant l’ordre dans lequel les
joueurs jouent et quand le jeu se termine,
– Le résultat du jeu pour chaque fin possible et son
implication en termes de fonction de paiement (via les
préférences des joueurs)
21

7
 Jeux sous forme stratégique
(normale)
• Un jeu sous forme stratégique est un modèle
mettant en œuvre des joueurs en interaction,
• Cette modélisation est utile pour décrire des
situations dans lesquelles les joueurs jouent en
même temps
• Plusieurs situations peuvent être modélisées en
forme normale. Par exemple:
– les joueurs peuvent être des firmes
– les actions les prix
– et les préfèrences peuvent l’impact sur les gains des
firmes , 22

Le dilemme du prisonnier
• Le jeux le plus connu en forme stratégique est le
dilemme du prisonnier;
• Deux suspects (Suspect1 et Suspect2) sont interrogés
séparément par un juge pour un délit grave. Le juge ne
dispose pas d’éléments de preuve suffisants pour les
condamner et l’aveu d’au moins un est indispensable.
Dès lors, il propose à chaque accusé la liberté s’il avoue.
Par contre s’il n’avoue pas et que l’autre le fait , il subit
d’une peine de 15 ans.
• Si les 2 avouent il peuvent espérer bénéficier de
circonstances atténuantes et recevoir une peine de 8
ans. Enfin si aucun des 2 n’avoue, ils seront condamnés
pour des délits mineurs à 1 an de prison chacun. Dans
ce cas, la matrice des gains des deux joueurs a la forme
suivante.
23

Le dilemme du prisonnier
• Ce jeu peut être représenté comme un jeu stratégique
où :
• les joueurs sont les deux suspects
• qui ont chacun le choix entre deux actions : {Se taire,
Dénoncer}
• on suppose que les préférences des joueurs sont
uniquement déterminées par les années qu'ils passeront
en prison. Ainsi :
• u1(Dénoncer, Se taire) > u1(Se taire, Se taire) >
u1(Dénoncer, Dénoncer)>u1(Se taire, Dénoncer), et
• u2(Se taire, Dénoncer)>u2(Se taire, Se
taire)>u2(Dénoncer, Dénoncer)>u2(Dénoncer, Se taire)24

8
 Le dilemme du prisonnier
représentation matricielle

25

Dilemme du prisonnier
intérêt
• Le dilemme du prisonnier modélise des situations dans
lesquelles il y a un gain à la coopération (les deux
joueurs préfèrent une situation dans laquelle ils se
taisent tous les deux, à une situation où ils dénoncent
tous les deux).
• Ce jeu est intéressant pas parce qu'on est intéressé à
comprendre les intérêts des prisonniers à avouer mais
parce que de nombreuses autres situations ont la même
structure,
•

26

Dilemme du prisonnier
situations équivalentes
• en économie : les questions de politique tarifaire : le concurrent qui
baisse son prix gagne des parts de marché et peut ainsi augmenter
ses ventes et accroître éventuellement son bénéfice... mais si son
concurrent principal en fait autant, les deux peuvent y perdre.
• en politique internationale. Deux pays peuvent choisir de maintenir
ou non une armée. Si tous deux ont une armée (de force à peu près
équivalente), la guerre est moins "tentante", car très coûteuse
(situation de guerre froide). Les dépenses militaires sont alors une
perte nette pour les deux pays. Si un seul a une armée, il peut
évidemment conquérir l'autre, ce qui est pire. Enfin, si aucun n'a
d'armée, la paix règne et les pays n'ont pas de dépenses militaires

27

9
 Exemple1: Travailler sur un
projet commun
• Vous travaillez avec un ami sur un projet commun. Chacun de vous
peut travailler dur ou ne rien faire (goof off). Si votre ami travaille
dur, alors vous préférez rien faire (le résultat du projet serait mieux
si vous travailliez dur aussi, mais l'augmentation de sa valeur pour
vous ne vaut pas l'effort supplémentaire).
• Vous préférez le résultat de votre travail (les 2 travaillent dur) que
l’issue de vos deux abandons (ne rien faire) (dans ce cas, rien n'est
accompli),
• et le pire résultat pour vous est que vous travaillez dur et votre ami
ne fait rien (vous détestez être "exploité").
• Si votre ami a les mêmes préférences alors le jeu, qui modélise la
situation à laquelle vous faites est un dilemme du prisonnier.

28

Exemple1: Travailler sur un

projet commun
• La matrice de gain

• Si on change d’hypothèse: préférer

travailler dur que de ne rien faire lorsque
l’autre personne travaille dur, dans ce cas
le dilemme du prisonnier ne tient plus
29

Duopole
• deux entreprises produisent le même bien, pour lequel chacune
d’elle doit choisir entre un prix bas ou un prix élevé.
• Chaque entreprise veut atteindre le profit le plus élevé possible. Si
les deux firmes choisissent High, chacune d'elles gagne un bénéfice
de 1000 $.
• Si une entreprise choisit High et que l'autre choisit Low, l'entreprise
ayant choisit High n'obtient aucun client et fait une perte de 200 $
alors que l'entreprise qui a choisit Faible gagne un bénéfice de
1200 $ (son bénéfice unitaire est faible, mais son volume est élevé).
• Si les deux entreprises choisissent Low ,chacune d’elle gagne un
bénéfice de 600 $.
• Chaque entreprise ne se soucie que de son bénéfice,

30

10
 Matrice de gain

31

Synthèse DP
• Dans le DP où est la coopération?
• Premier exemple:
– (Ne pas avouer, Ne pas avouer) gain (-1,-1)
• Deuxième exemple:
– (work hard, work hard) gain (2,2)
• Troisième exemple:
– (high, high) gain (1200,1200)
• C’est la coopération qui rapporte le plus
de gain. 32

Bach ou Stravinsky
• Dans le dilemme du prisonnier le principal objectif est de
savoir si les joueurs vont coopérer (choisir la
coopération: ne pas avouer),
• Un autre type de jeu est que les joueurs sont d’accord
qu’il faut coopérer, mais ne sont pas d’accord sur le
meilleur choix

33

11
 Exemple

• Deux personnes veulent sortir pour assister à un concert . Deux concerts

sont disponibles: celui de Bach et celui de Stravinsky
• Une personne préfère Bach et l’autre Stravinsky,
• S’ils vont à différents concerts, ils seront insatisfaits tous les deux. (voulant
être ensemble)

• Ce jeux peut modéliser plusieurs situations réelles exemple:

• Deux firmes émergentes veulent utiliser des technologies différentes à
cause de leur expériences passées, mais comme elles appartiennent à une
même grandes firmes, elles doivent choisir la même technologie….

34

Jeux conflictuels
• Un autre modèle de jeu purement conflictuel est illustré par cet exemple:
jeu d’appariement (matching pennies)
• Charles et Louise doivent placer simultanément une pièce d’un penny sur la
table, sur pile ou sur face. Si les deux pièces sont sur le même côté, Louise
les prend, si elles ont sur des côtés différents, Charles les prend.

• Jeu en forme normale

• Ce type de jeu est dit jeux à somme nulle

35

Jeu conflictuel
• Dans ce jeu, les intérêts des joueurs sont
diamétralement opposés,
• Ce jeu est strictement compétitive: le joueur 1
veut prendre la même action que l’autre joueur,
et le joueur 2 veut prendre l’action opposée.

36

12
 Exemple
• Deux entreprises doivent choisir la caractéristique d’un
nouveau produit.
• Une entreprise est présente sur le marché depuis
longtemps, alors que l’autre vient d’entrer sur le marché.
• L’entreprise la plus ancienne préfère que le produit du
nouveau concurrent ait une caractéristique différente de
celle de son produit,
• alors que le nouveau concurrent préfère que la
caractéristique soit la même.
• Le jeu à somme nulle modélise une relation entre deux
personnes dans laquelle l’une veut être comme l’autre,
et l’autre ne veut pas.
37

Application
• Exprimer sous forme stratégique l’exemple
précedent.

38

Jeu sous forme extensive

• La modélisation sous forme extensive est
un autre moyen de représenter un jeu.
• Il s'agit d'un modèle où les joueurs
choisissent séquentiellement leurs actions,
jusqu'au moment où le jeu est déclaré fini.

39

13
 Représentation graphique
• Tout jeu sous forme extensive peut être représenté par
un arbre (graphe connexe sans cycle)
• Où à chaque noeud terminal correspond un résultat du
jeu
• à chaque noeud non terminal est associé un joueur :
arrivé à ce point du jeu, c'est à son tour de jouer.
• chaque arc représente chacune des actions que ce
joueur peut prendre à ce point du jeu

40

41

Exemple
• Un joueur en position de monopole, le "titulaire", est
confronté à la possible entrée d'un challenger (le
challenger peut, par exemple, être:
– une firme désirant entrer sur un marché régit par un monopole ;
– un homme politique désirant prendre le contrôle d'un parti ;
• Le challenger peut entrer ou non. S’il entre, le "titulaire"
peut accepter ou se battre.
• Les résultats possibles du jeux sont ainsi (Entrer,
Accepter), (Entrer, Se battre) ou (Ne pas entrer).
• Les règles du jeux spécifient par ailleurs que le
challenger joue le premier et que le titulaire ne joue que
si le challenger a joué "Entrer".
42

14
 43

Jeux en information parfaite

• Un jeu sous forme extensive, en information parfaite, est défini par
– l'ensemble des joueurs {
i Î 1, 2 ,..., N }
– l'arbre du jeu : constitué d'un ensemble fini de nœuds T Î{t1, t2 ...,tk }
muni d'une relation de "succession" :
• le noeud initial (début du jeu) n'est le successeur d'aucun autre noeud
• chaque noeud (non initial) est le successeur d'un seul noeud
• les noeuds terminaux n'ont pas de successeurs
(on note s(t), l'ensemble des successeurs d'un noeud t)
• à chaque noeud t (non terminal) est associé un joueur i(t). A ce point du jeu
c'est à i(t) de jouer
• à chaque noeud t est associé un ensemble d'actions A(t), à chaque action
correspond un noeud successeur unique dans s(t)
• à chaque noeud terminal z est associé un vecteur de paiements.
• u(i, z) est le gain du joueur i si le jeu se termine au noeud z

44

Exemple
• joueurs: titulaire et le challenger
• Les histoires terminales:
(Entrer, Accepter);
(Entrer, Se battre);
(Ne pas Entrer).
• La fonction joueur:
– P(f)= Challenger et P(Entrer)= Titulaire
• Préférences:
– Challenger fonction d’utilité (paiement) : u1(Entrer, Accepter)=2,
u1 (Entrer, Se battre)=0 et u1(Ne pas Entrer)=1
– Titulaire: u2(Ne pas Entrer)=2, u2 (Entrer, Accepter)=1,
u2((Entrer, Se battre)=0
45

15
 Jeu en information imparfaite
• Le concept d’ensemble d’information permet de
formaliser l’information imparfaite.
• Formellement, un ensemble d’information est un sous-
ensemble des noeuds de décision d’un joueur.
• Les ensembles d’information d’un joueur forment une
partition des noeuds gérés par ce joueur.
• L’interprétation est qu’un joueur ne peut distinguer les
noeuds d’un même ensemble d’information.
• Les actions perçues par le joueur en chaque noeud d’un
même ensemble d’information sont donc identiques.
• Définition : un jeu est à information parfaite si chaque
ensemble d’information est un singleton. Sinon, le jeu 46
est à information imparfaite.

Exemples
• Avec information parfaite
– Joueurs : Deux joueurs notés 1 et 2
– Règles du jeu : font leurs choix séquentiellement, Le
joueur 1 choisit en premier. Le joueur 2 observe le
choix du joueur 1 et joue en second.
• Avec information imparfaite:
– Le joueur 2 ne peut pas observer le choix du joueur 1.

47

Exemples (suite)
• Information parfaite: • Information imparfaite

• Ensemble d’information pour le

joueur 2 {Face,Pile}
• Ensemble d’information pour le
joueur 2 est {Face} {pile}

48

16
 Règle générale
• le concept d'information imparfaite n'est pas applicable à des jeux
dans lesquels le joueur peut discerner dans quelle situation il se
trouve en fonction du joueur qui a joué avant lui
• Le graphe ci-dessus n'est pas cohérent : le joueur 2 peut savoir s'il
est en D ou B en fonction de l'identité du joueur qui a joué avant lui.

49

Exercice
• Soit un jeu à deux joueurs, dans lequel
chaque joueurs a deux actions possibles :
aller à droite ou aller à gauche.. Chaque
joueur préfère être à droite si l'autre y est
aussi, sinon il préfère être à gauche.
• Le joueur 1 joue en premier

50

Introduction au joueur
« Nature »
• Le modèle de jeu sous forme extensive avec information parfaite ne permet
pas de rendre compte d'événements aléatoires pouvant intervenir durant le
jeu.
• Cependant, il peut être aisément étendu pour couvrir de telles situations. La
définition d'un jeu sous forme extensive avec joueur "Nature" est une
variante de la définition précédente dans laquelle :
– la fonction joueur assigne la "Nature" à certaine sous-séquences (on ajoute un
nouveau joueur)
– les probabilités de chacune des actions de la "Nature" sont spécifiées
– les préférences des joueurs sont définies sur l'ensemble des loteries d'histoires
terminales (et non plus sur les histoires terminales elles-mêmes)
• Pour que l'analyse reste simple, on supposera que les événements
aléatoires après une certaine histoire (sous-séquence) sont indépendants
des événements aléatoires après les autres sous-séquences.

51

17
 Exemple
• Considérons un jeu à deux joueurs dans lequel le
joueur 1 doit d'abord choisir entre les actions A et B.
• S’il choisit A le jeu s'arrête avec des paiements
(1,1).
• S’il choisit B :
– avec probabilité 1/2 le jeu s'arrête et les paiements
sont (3,0), et
– avec probabilité 1/2 le joueur 2 peut choisir entre les
actions:
• C qui donne un paiement (0,1) et
• D qui donne un paiement (1,0).
52

• Jeux sous forme extensive

• N représente le joueur Nature et les

nombres sur les arcs sont les probabilités 53

jeux sous forme extensive avec

information imparfaite + hasard
• Un jeu sous forme extensive, en information imparfaite (avec
hasard), est défini par:
– un ensemble de joueurs,
– un ensemble de séquences (histoires terminales) tel qu'aucune
séquence n'est sous séquence d'une autre séquence,
– une fonction (la fonction joueur) qui assigne un joueur ou la "nature" à
chaque sous-séquence d'une histoire terminale,
– une fonction qui assigne pour chaque sous-séquence à laquelle le
joueur « nature » est associé (par la fonction joueur) une distribution de
probabilités sur les actions disponibles après cette histoire (les
différentes distributions étant indépendantes les unes des autres)
– pour chaque joueur, une partition (la partition de l'information) de
l'ensemble des histoires qui lui sont assignées par la fonction joueur.
– pour chaque joueur, des préférences sur les loteries d'histoires
terminales
54

18
 Exercice
• Soient 2 joueurs:
• Chacun des deux joueurs commence par mettre un euro dans le
pot. On donne au joueur 1 une carte qui peut être Haute avec
probabilité q ou Basse avec probabilité(1-q). Il observe la carte mais
le joueur 2 ne l'observe pas. Il peut "laisser" ou "monter".
• S’il "laisse", le joueur 2 prend le pot et le jeu s'arrête. Si le joueur 1
"monte", il rajoute 1euro dans le pot et le joueur 2 a le choix entre
"passer" et "suivre".
• Si il passe, le joueur 1 prend le pot. Si le joueur 2 "suit", il ajoute
1euro dans le pot et le joueur 1 montre la carte.
• Si elle est Haute, le joueur 1 prend le pot, sinon le joueur 2 le prend.

55

Exemple suite
• Le joueur 1 a deux ensembles
d'information, un contenant
l'histoire unique Haute et
l'autre contenant l'histoire
unique Bas.
• Le joueur 2 a un ensemble
d'information qui consiste en
deux histoires : {Haute,
Monter} et {Bas, Monter}. Cet
ensemble d'information reflète
le fait que le joueur 2 ne peut
pas observer le carte du joueur

56

De la forme extensive à la
forme stratégique
• En d’autres terme : comment
représenter la séquentialité d’un jeu en
utilisant une représentation sous forme
stratégique?
• Soit le jeu suivant:
• Pour représenter ce jeu sous forme
stratégique il faut:
– prendre en compte le fait que le joueur
2 observe ce que 1 a joué
– L’action du joueur 2 pourra différer selon
ce que le joueur 1 a joué;
– On doit donc spécifier une stratégie
pour le joueur 2 qui indique ce qu’il fera
dans toutes les configurations possibles.
• Ainsi dans l’exemple:
– Si le joueur 1 joue G, 2 joue g et si le
joueur 1 joue D, 2 jouerai g’ (-> gg’)
– gd’: si 1 joue G, 2 joue g si 1 joue D, 2
jouerai d’… de même dg’ et dd’
57

19
 suite

58

Jeu information incomplète

• Si on suppose dans le jeu
précédent que le joueur 2
ne peut pas observer (ou
distinguer) ce qu'a joué le
joueur 1 ,
• tout se passe comme si
le jeu était simultané.
Sous forme extensive,on
a:

59

suite
• Par contre, si le joueur 2
est capable de distinguer
entre certaines actions du
joueur 1 mais pas entre
d'autres, l'écriture de la
stratégie devient plus
complexe.
• Le jeu sous forme
extensive :

60

20