Part 2 Jeux m1

Equilibre parfait en sous-jeux Jeux répétés
Partie II : Jeux et Dynamique
Nicolas Carayol
M1 MIMSE - 12 février 2014

Dynamique
• Réellement prendre en compte la dynamique dans le cadre

d’un jeu séquentiel
• Jeux répétés
Exemple)
CHAPITRE 2. JEUX, STRATEGIES ET INFORMATION 12
(uE , uI )
Coopérer (40, 50)
Entrer I
E
Combattre (−10, 0)
Non
(0, 300)
Fig. 2.1: Le Jeu de l’Entrée I

Jeu de l’entrée tiré de Yildizoglu (2011)
Remarque 2.3 Les gains représentent en général des utilités ordinales et non des sommes moné-
taires. En organisation industrielle, néanmoins, les gains des firmes correspondent souvent à des
profits.
→ Deux équilibres de Nash en stratégies pures :
La formulation sous la forme d’un jeu permet de clarifier une situation conflictuelle. Il nous faut
(Entrer ,ennous
Coopérer
plus comprendre ) ettype
à quel (Non, Combattre).
de solution ce jeu peut nous conduire. Pour déterminer cette solution,
allons étudier plus tard les équilibres du jeu.
Mais :
2.1.2 La forme extensive d’un jeu
L’équilibreLa (Non, Combattre)
forme normale est surtout –mais pas←exclusivement–
la menace deà lacombattre
adaptée représentation des l’entrée
jeux si
simultanés. Selten(1975) a popularisé une représentation arborescente et plus intuitive des jeux : la
elle a lieu.
forme extensive. Nous pouvons alors représenter des jeux séquentiels où les décisions sont prises à
des moments différents et où chaque joueur peut être amené à jouer plusieurs fois.
Est-ce Exemple
que cette menace
2 : Le problème vapotentiel
de l’entrant vraiment être exécutée ?
Considérons le problème d’entrée d’une firme dans le marché d’un monopole.
Non puisque l’entrée n’aura pas lieu à cet équilibre.
1. L’entrant (E) doit choisir entre Entrer ou N e pas entrer.
Equilibre de Nash :
• L’EN est basé sur la résistance aux déviations en termes de

plans d’action au début du jeu.
• Il n’y pas de résistance des choix aux déviations pendant le
déroulement effectif du jeu.
• Donc, il devient possible pour les joueurs d’annoncer des plans
qu’ils n’auront pas nécessairement envie de suivre pendant le
déroulement du jeu, ce qui va jouer sur la détermination de
l’équilibre.
• Techniquement, il y a peu de contraintes sur les actions
choisies par les joueurs en dehors du chemin d’équilibre.
Sous-jeux
Généralisation de l’idée de base → utilisation effective des
stratégies annoncées.
Définition
Un sous-jeu d’un jeu en forme extensive J est constitué par :
• un ensemble K de sommets, comprenant un sommet de J et
les sommets consécutifs à celui-ci, muni de la propriété
suivante : si un sommet k de K appartient à un ensemble
d’information h non-réduit à un singleton alors tous les
sommets de h appartiennent à K (h ⊂ K ) ;
• l’ensemble des arcs reliant les différents sommets de K ;
• les gains terminaux de J correspondants aux sommets
terminaux de K .
Définition
Quand un sous–jeu est différent du jeu original, on l’appelle un
sous-jeu propre.
Tout jeu J en forme extensive contient au moins un sous-jeu :
lui-même.
ENPSJ
Définition
(Selten (1975)) Un profil de stratégies du jeu J est un équilibre
de Nash parfait en sous–jeux (ENPSJ) s’il correspond à un
équilibre de Nash dans chaque sous–jeu du jeu J.
Lemma
Un EPSJ doit être un équilibre de Nash du jeu original (car ce
dernier correspond à l’un des sous–jeux).
Illustration
exemples tirés des TD

Jeux répétés
• Beaucoup d’interactions sociales se déploient dans le temps et

souvent de manière répétée.
• Les modèles de jeux répétés servent à analyser la logique de
ce type d’interactions de long terme.
• L’idée principale : la répétition permet, dans certaines
circonstances, de faire émerger des comportements nouveaux.
• Application principale (mais particulière) : le dilemme du
prisonnier auquel deux joueurs sont confrontés de manière
répétée.
L’idée de base
2
C D
1 C (3, 3) (−1, 4)
D (4, −1) (0, 0)
Table: Dilemme du prisonnier II
• Le seul équilibre de Nash → (D, D) → Pareto–dominé par

(C , C ) .
• La coopération peut-elle quand même apparaı̂tre si le
jeu est répété ?
• Mécanisme potentiel : lorsque chaque joueur pense que s’il
arrête de coopérer il peut éteindre des perspectives futures de
coopération , voire être puni par les autres joueurs → notion
de paiement minmax.
Paiements minmax
• Le niveau de paiement minmax, ou paiement de punition, du

joueur i noté ũi dans un jeu sous forme normale est le niveau
le plus faible auquel les autres joueurs peuvent le contraindre :
ũi = min max ui

Stratégies des autres Stratégies de i
• Ainsi, ũi est le paiement le plus faible cohérent avec la

rationalité individuelle du joueur i.
• Un profil de paiements u = (u1 , ..., un ) est individuellement
rationnel ssi ui ≥ ũi , ∀i.
Paiements minmax
2
C D
1 C (3, 3) (−1, 4)
D (4, −1) (0, 0)
Paiements minmax
2
C D
1 C (3, 3) (−1, 4)
D (4, −1) (0, 0)
• Minimax = EN
• Paiements de minmax = 0
Paiements minmax
2
C D P
C (3, 3) (−1, 4) (−2, −1)
1 D (4, −1) (0, 0) (−1, −1)
P (−1, −2) (−1, −1) (−3, −3)
Paiements minmax
2
C D P
C (3, 3) (−1, 4) (−2, −1)
1 D (4, −1) (0, 0) (−1, −1)
P (−1, −2) (−1, −1) (−3, −3)
• EN=DD
• Paiements de minimax → −1
• Les agents jouent un jeu de base répété.

• Leurs gains portent sur la totalité des périodes.
• Comment pouvons-nous représenter un tel jeu ?
Definitions
Définition
Un jeu en forme normale est décrit par :
Un ensemble de n joueurs : I = {1, 2, . . . , n} .
Chaque joueur i a un ensemble d’actions ai ∈ Ai . Une issue ou
profil d’actions est donnée par le vecteur a ≡ (a1 , a2 , . . . , an )
Pour chaque joueur i, une fonction de gain, ui : A = X Ai → R
i∈I
Definitions
Définition
Etant donné un jeu sous forme normale G = (I , (Ai ), (ui )), le jeu
répété G (T , δ) est le jeu sous forme extensive où G est joué en T
étapes, où les actions de toutes les étapes sont publiquement et
parfaitement observées, et les gains sont obtenu à chaque période
jouée et actualisés au facteur δ.
Définition
Le jeu répété G (∞, δ) est le jeu sous forme extensive où G est joué
un nombre d’étapes infini.
Définition
Le profil d’action en t est noté at ≡ (a1t , a2t , . . . , ant ) , at ∈ A, ∀t.
Histoires et Stratégies
Définition
Une histoire à l’étape t est le vecteur
ht = (a1 , a2 , ..., at−1 ) ∈ At−1 = A
| × {z
··· × A}.
t−1 fois
Définition
Une stratégie (pure) du joueur i est donnée par : si = (si1 , ..., siT ),
où sit : At−1 → Ai .
Equilibre de Nash
Définition
Un profil de stratégies (pure) donné par : s = (s1 , ..., sn ) = (si , s−i )
est un équilibre de Nash si pour toute autre stratégie de n’importe
quel joueur i ŝi = (ŝi1 , ..., ŝiT ) :
T
X T
X
δ t−1 ui (sit , s−i
t
)≥ t
δ t−1 ui (ŝit , s−i ).
t=1 t=1
Equilibre de Nash parfait en sous jeux 1
Définition
La stratégie (pure) si du joueur i, sa stratégie de continuation en t
est donnée par si |ht .
Définition
Un profil de stratégies (pure) s = (si , s−i ) est un équilibre de Nash
parfait en sous jeux si pour toutes les histoires ht , si |ht est un
équilibre de Nash du jeu répété.
Equilibre de Nash parfait en sous jeux 2
Définition
Une déviation en un coup du joueur i de la stratégie si est une
stratégie ŝi 6= si telle qu’il existe une seule histoire ĥt pour laquelle,
si (ĥt ) 6= ŝi (ĥt ).
Définition
Un profil de stratégies s = (si , s−i ) est un équilibre de Nash parfait
en sous-jeux d’un jeu répété si et seulement si il n’existe pas de
déviation en un coup profitable. Soit ŝi toute déviation en un coup
du joueur i de la stratégie si . P
s = (si , s−i ) est un ENPSJ ssi :
∀i ∈ I , ∀τ ≤ T , ∀ĥτ ∈ At−1 : T t=τ δ
t−1 u (s t , s t ) ≥
i i −i
PT t−1 u (ŝ t , s t ).
t=τ δ i i −i
Jeux répétés finis et jeux répétés infinis
L’horizon temporel
• L’horizon temporel du jeu est une variable essentielle.
• Horizon fini/infini : les résultats sont très différents entre ces
deux types de jeux.
• NB : il s’agit de l’horizon tel qu’il est perçu par les joueurs
plus que tel qu’il est objectivement.
Horizon fini mais indéfini
Autre possibilité : le jeu est répété un nombre fini mais indéfini de

fois.
Après chaque tour → une probabilité 1 − q que le jeu s’arrête.
→ L’espérance des gains sur la totalité de la séquence :
∞
X
q t−1 u1 at ,

q ∈ (0, 1)
t=1
Un horizon infini avec actualisation et le jeu est répété fini mais

indéfini sont équivalents du point de vue des agents.
Les résultats sont fondamentalement différents en fonction de

l’horizon temporel :
• Horizon fini et défini vs.
• Infini ou fini et indéfini.
Jeux avec horizon fini et defini

• Prenons le dilemme du prisonnier II répété exactement 100
fois.
2
C D
1 C (3, 3) (−1, 4)
D (4, −1) (0, 0)
• Ici : Minimax = unique équilibre de Nash du jeu de base.

• L’unique EN (et ENPSJ) du dilemme des prisonniers répété
un nombre fini de fois : les deux joueurs dénoncent à toutes
les périodes.
• Particularité du jeu du dilemme des prisonniers : comme les
paiements d’équilibre sont les paiements minmax, il n’y a pas
de menace suffisante pour “forcer” la coopération).
Théorème
Si tous les profils de paiements d’équilibre du jeu de base
coı̈ncident avec le profil de paiements minmax du jeu de base alors
toutes les trajectoires d’équilibres de Nash du jeu répété fini sont
telles que chaque action dans tous les jeux de base correspond aux
stratégies d’équilibre de Nash.
• La coopération dans le dilemme du prisonnier répété à horizon

fini et défini est causée par l’absence de possibilité de punition
au delà de l’EN (l’issue de paiement minmax correspond à
l’EN).
Prenons le dilemme du prisonnier III joué exactement 2 périodes :

période 1 et 2.
2
C D P
C (3, 3) (−1, 4) (−2, −1)
1 D (4, −1) (0, 0) (−1, −1)
P (−1, −2) (−1, −1) (−3, −3)
Table: Dilemme du prisonnier III
• Ici, un seul équilibre de Nash du jeu de base : DD

→ 0 > −1 ← Minimax
• Considérons la stratégie s :
• jouer C à la première période et
• jouer D à la seconde période si CC en 1 et P sinon.
Prenons le dilemme du prisonnier III joué exactement 2 périodes :

périodes 1 et 2.
2
C D P
C (3, 3) (−1, 4) (−2, −1)
1 D (4, −1) (0, 0) (−1, −1)
P (−1, −2) (−1, −1) (−3, −3)
Table: Dilemme du prisonnier III
• Un profil de stratégies dans lequel les deux joueurs jouent s

constitue-t-il un EN du jeu répété ?
• Demo : (conseil : raisonner en plans d’actions fixés au début
de la période 1)
• Deviation unilatérale de s en 1 vs non déviation
• Deviation unilatérale de s en 2 vs non déviation
• Mais ce n’est pas un ENPSJ, car les joueurs n’ont pas intérêt
à jouer P à la seconde période ← il y a une déviation en un
coup profitable !
• Unique ENPSJ : les deux joueurs jouent D à la première
période et D à la seconde période.
Théorème
Si le jeu de base a un unique équilibre de Nash, le jeu répété un
nombre fini de fois a un unique équilibre de Nash parfait en sous
jeu, où l’équilibre de Nash du jeu de base est joué à chaque étape
(quelle que soit l’histoire préalable du jeu).
• Prenons le dilemme du prisonnier IV :
2
C D P
C (3, 3) (−1, 4) (−2, −1)
1 D (4, −1) (1, 1) (−1, −1)
P (−1, −2) (−1, −1) (−1/2, −1/2)
Table: Dilemme du prisonnier IV
• Deux équilibres de Nash du jeu de base : DD et PP

• 2 périodes
• Considérons la stratégie s :
• jouer C à la première période et
• jouer D à la seconde période si CC en 1 et P sinon.
• Prenons le dilemme du prisonnier V :
2
C D A B
C (2, 2) (0, 3) (0, 0) (−2, 0)
1 D (3, 0) (1, 1) (0, 0) (−2, 0)
A (0, −2) (0, −2) (2, −1) (−2, −2)
B (0, 0) (0, 0) (0, 0) (−1, 2)
Table: Dilemme du prisonnier V
• Trois équilibres de Nash du jeu de base : DD, AA et BB.

• Sur 2 périodes, considérons la si de l’agent i :
• si1 = C 
 D si a11 = a21 = C ou a11 et a21 6= C
2
• si = A si a11 = C et a21 6= C
B si a21 = C et a11 6= C

• (s1 , s2 ) est un ENPSJ car un EN est joué en 2 dans toutes les
histoires possible en 1.
• Il devient possible de soutenir la coopération à la première

période.
• Par l’éventualité d’une punition crédible, qui consisterait à
jouer P, et sachant que l’autre joueur ferait de même (PP est
un EN du jeu de base).
• Impossibilité absolue de soutenir la coopération à la dernière
période.
• Condamnation courte → nos voleurs recommencent de

manière répétée.
• Ils jouent au dilemme du prisonnier répété pour toujours.
• Quels sont les résultats qui émergent si l’on passe du jeu
statique au dilemme de prisonnier répété ?
Le résultat principal : la coopération devient un résultat d’équilibre.
• Reprenons le Dilemme du prisonnier II
2
C D
1 C (3, 3) (−1, 4)
D (4, −1) (0, 0)
• Considérons la stratégie suivante de 1 :

• il joue C tant que 2 joue C et
• si jamais 2 joue D, 1 joue D jusqu’à la fin du jeu (pour
toujours).
• C’est la “stratégie du méchant” (grim strategy)
• 2 applique la même stratégie (symmétrique)
• Ce profil de stratégie est-il un équilibre ?
Respecter sa stratégie grim face à une grim rapporte un flux

continu de gains dont la valeur actualisée est :
∞
X
3δ t = 3/ (1 − δ) .
t=0
Si un joueur dévie et joue D à un tour,

• il va obtenir 4 à ce tour mais
• 0 pour le reste des périodes.
→ Il a donc intérêt à coopérer (jouer grim par exemple) si :
3 1
≥ 4 ⇔ δ ≥ = 25%.
1−δ 4
→ Ce profil de stratégies forme donc un équilibre de Nash si les

1
agents ne préfèrent pas trop le présent (pour δ = 1+ρ ≥ 25%)
d’autres profils de stratégies ne constituent-ils pas aussi un EN ?
quid de la multiplicité des équilibres.

Cet équilibre de Nash est-il le seul possible ?

Supposons par exemple que 1 annonce la stratégie suivante :
• il va alterner entre C et D tant que 2 joue C .
• Si jamais 2 dévie et joue D, 1 joue D pour toujours.
Si 2 adopte une stratégie qui l’amène à jouer C face à cette

stratégie, ses gains vont alterner entre 3 et −1 jusqu’à la fin des
temps.
Si adopte une stratégie qui l’amène à jouer D alors il obtient 4 à

cette période mais 0 pour le reste du jeu.
Si cette stratégie est formulé de manière à ce que 1 n’ait pas

intérêt à dévier, alors pour une valeur suffisamment élevée de δ la
coopération est encore préférable.
• Equilibre → si 2 annonce une menace suffisante pour inciter

1 à respecter sa stratégie
• Par exemple : jouer D pour toujours si jamais 1 arrête
d’alterner
• On peut en imaginer d’autres.
• Par exemple : un équilibre où les deux alternent tant que
l’autre continue à alterner
• Donc : jeu répété → la profusion d’équilibres.
Définition
Un profil de paiement û est réalisable si, pour tout i, ûi est une
combinaison convexe
P des paiements P des différentes issues du
jeu :∃ρ, tel que a ρ(a) = 1 et a ρ(a)ui (a) = ûi .
Reprenons le dilemme du prisonnier :
2
C D
1 C (3, 3) (−1, 4)
D (4, −1) (0, 0)
→ représentation graphique des paiements réalisables.

Théorème
Tout vecteur de gains réalisables espérés peut être soutenu à
l’équilibre s’il donne à chaque joueur au moins autant que ses
gains de minmax (si tous les autres joueurs s’étaient ligués contre
lui, rationalité individuelle).
→ représentation graphique
→ Le folk theorem (ou le théorème de tout le monde).
→ Multiplicité des équilibres de Nash.
Question : Quel est l’intérêt des autres joueurs à punir celui qui a
dévié de l’accord ?
→ La punition peut être très coûteuse non seulement pour le puni
mais aussi pour ceux qui l’infligent.
→ Equilibres de Nash basés sur ce type de menaces → Ils ne sont
pas parfaits en sous-jeux.
Soit le jeu d’étape suivant
2
C D
1 C (5, 5) (−1, −2)
D (6, −1) (0, −3)
Table: Dilemme du prisonnier (variante)
→ 2 peut menacer 1 de le contraindre à un gain nul (gains

minmax du joueur 1) en jouant D.
2
C D
1 C (5, 5) (−1, −2)
D (6, −1) (0, −3)
Un équilibre de Nash :
• 1 joue C tout le temps.
• 2 joue C tant que 1 joue C et adopte D si jamais 1 joue D.
Problème : 1 n’aura pas envie de jouer D (si δ est suffisamment
élevé)
← s’il croit que 2 va exécuter sa menace
→ mais difficile de croire que 2 va effectivement exécuter cette
menace :
• 2 n’obtiendra pas plus de −2 s’il exécute sa menace
• en jouant C , il obtient au pire −1.
La coopération n’est ici pas un ENPSJ : il existe une histoire dans
laquelle un joueur a envie de dévier de sa stratégie annoncée.
→ 1 va être incitée à jouer impunément D
Mais cela n’implique pas que le théorème folk ne s’applique pas

pour les EPSJ.
Théorème
Soit J un jeu fini statique en information complète. Soient
u ∗ = (u1∗ , . . . un∗ ) le vecteur des gains des joueurs pour un équilibre
de Nash du jeu de base, et u = (u1 , . . . un ) un vecteur de gains
réalisables dans ce jeu . Si ui > ui∗ pour tout joueur i et si δ est
suffisamment proche de l’unité alors il existe un EPSJ du jeu
répété de manière infinie G (∞, δ) qui donne u comme le vecteur
des gains moyens des joueurs.
Oeil pour oeil... (tit for tat)

Intuition pour le folk theorem II
• Toute stratégie de punition est entre :
• Grim et
• tit–for–tat : je commence par jouer C et, dans chaque période
ultérieure, je vais faire ce que l’autre a fait dans la période
précédente.
• Si δ suffisamment proche de 1 → on n’a pas besoin d’une
punition qui durera jusqu’à la fin des temps pour soutenir la
coopération :
• Il suffit de calibrer une période suffisament longue de punition
pour qu’elle soit dissuasive
• Comme il est anticipé que la coopération reprenne ensuite
jusqu’à la fin de temps, la désincitation à punir (lorsque la
punition est coûteuse pour celui qui inflige la punition) est
compensée par le gain de la coopération jusqu’à la fin des
temps.
Oeil pour oeil... (tit for tat)

Exercice
On condidère le jeu infiniement répété G (∞, δ) du jeu de base
suivant
Joueur 2
c d
Joueur 1 c 2, 2 0, 3
d 3, 0 1, 1
a. Sous quelles conditions le profil de stratégies (tft, tft) est un

EN ?
b. Sous quelles conditions le profil de stratégies (tft, tft) est un
ENPSJ ?
c. Sous quelles conditions le profil de stratégies (tft, grim-fort)
est un ENPSJ ?

Part 2 Jeux m1

Transféré par

Droits d'auteur :

Formats disponibles

Part 2 Jeux m1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Part 2 Jeux m1

Transféré par

Droits d'auteur :

Formats disponibles

Equilibre parfait en sous-jeux Jeux répétés

Partie II : Jeux et Dynamique

M1 MIMSE - 12 février 2014

• Réellement prendre en compte la dynamique dans le cadre

Fig. 2.1: Le Jeu de l’Entrée I

• L’EN est basé sur la résistance aux déviations en termes de

exemples tirés des TD

• Beaucoup d’interactions sociales se déploient dans le temps et

• Le seul équilibre de Nash → (D, D) → Pareto–dominé par

• Le niveau de paiement minmax, ou paiement de punition, du

ũi = min max ui

• Ainsi, ũi est le paiement le plus faible cohérent avec la

• Les agents jouent un jeu de base répété.

Equilibre de Nash parfait en sous jeux 1

Equilibre de Nash parfait en sous jeux 2

Jeux répétés finis et jeux répétés infinis

Horizon fini mais indéfini

Autre possibilité : le jeu est répété un nombre fini mais indéfini de

Un horizon infini avec actualisation et le jeu est répété fini mais

Les résultats sont fondamentalement différents en fonction de

Jeux avec horizon fini et defini

• Ici : Minimax = unique équilibre de Nash du jeu de base.

• La coopération dans le dilemme du prisonnier répété à horizon

Prenons le dilemme du prisonnier III joué exactement 2 périodes :

• Ici, un seul équilibre de Nash du jeu de base : DD

Prenons le dilemme du prisonnier III joué exactement 2 périodes :

• Un profil de stratégies dans lequel les deux joueurs jouent s

• Prenons le dilemme du prisonnier IV :

• Deux équilibres de Nash du jeu de base : DD et PP

• Prenons le dilemme du prisonnier V :

• Trois équilibres de Nash du jeu de base : DD, AA et BB.

• Il devient possible de soutenir la coopération à la première

• Condamnation courte → nos voleurs recommencent de

• Reprenons le Dilemme du prisonnier II

• Considérons la stratégie suivante de 1 :

Respecter sa stratégie grim face à une grim rapporte un flux

Si un joueur dévie et joue D à un tour,

→ Il a donc intérêt à coopérer (jouer grim par exemple) si :

→ Ce profil de stratégies forme donc un équilibre de Nash si les

d’autres profils de stratégies ne constituent-ils pas aussi un EN ?

quid de la multiplicité des équilibres.

Cet équilibre de Nash est-il le seul possible ?

Si 2 adopte une stratégie qui l’amène à jouer C face à cette

Si adopte une stratégie qui l’amène à jouer D alors il obtient 4 à

Si cette stratégie est formulé de manière à ce que 1 n’ait pas

• Equilibre → si 2 annonce une menace suffisante pour inciter

→ représentation graphique des paiements réalisables.

Soit le jeu d’étape suivant

→ 2 peut menacer 1 de le contraindre à un gain nul (gains

Mais cela n’implique pas que le théorème folk ne s’applique pas

Oeil pour oeil... (tit for tat)

Oeil pour oeil... (tit for tat)

a. Sous quelles conditions le profil de stratégies (tft, tft) est un

Vous aimerez peut-être aussi