Faculté des Sciences El Jadida

Théorie des jeux

Prof. Mohamed NABIL

Département Informatique
Année Universitaire 2023/2024
 Introduction
1. Définition
La théorie des jeux est un ensemble d’outils analytiques qui nous facilitent
la compréhension des situations d’interaction entre des décideurs (joueurs
= agents) rationnels.

La théorie des jeux est une branche des mathématiques qui s'intéresse aux
interactions stratégiques des agents.

La théorie des jeux utilise la mathématique pour exprimer formellement

les idées, mais les idées ne sont pas essentiellement mathématiques.

La théorie des jeux est la modélisation mathématique de l'interaction

stratégique entre des agents

2
 Introduction
1. Définition

La théorie des jeux a été développée à l’origine par:

John von Neumann, Oskar Morgenstern, The Theory of Games and

Economic Behavior (1944),

Ils ont affirmé que les mathématiques développées pour les sciences
physiques étaient un mauvais modèle pour l'économie.

Ils ont observé que l'économie ressemble beaucoup à un jeu, dans lequel
les joueurs anticipent les mouvements des autres, et nécessite donc un
nouveau type de mathématiques, qu'ils ont appelé théorie des jeux.

Ils ont étudié les jeux à « somme nulle » où les intérêts de deux joueurs
étaient strictement opposés.
3
 Introduction
1. Définition
Dans la théorie des jeux, le résultat pour chaque joueur dépend des actions
de tous.

Si vous êtes un joueur dans un tel jeu, lorsque vous choisissez votre plan
d'action ou votre « stratégie », vous devez tenir compte des choix des
autres.

Mais en réfléchissant à leurs choix, vous devez reconnaître qu'ils pensent

aux vôtres et qu'ils essaient à leur tour de prendre en compte votre
réflexion sur leur façon de penser.

4
 Introduction
2. Domaines d’application
➢ Elle s’utilise pour déterminer:
✓ Le prix optimal (auquel vendre) des produits ou des services face à la
concurrence.
✓ Le meilleur site pour une usine de fabrication.
✓ Le comportement de certains animaux et plantes dans leur lutte pour
la survie.
➢ Elle modélise des conflits entre les nations, les campagnes politiques, la
concurrence entre les entreprises et le comportement commercial sur
des marchés.
➢ Elle s’utilise dans le réseau informatique pour la détection des
malveillants par exemple.
➢ Elle est vraiment applicable à toute situation où il y a des compétitions
ou des interactions stratégiques. 5
 Introduction
3. Différents types de jeux

Les différents contextes d’interaction peuvent classés selon trois

dimensions:

✓ Le type de relation entre les agents (coopératif ou non-coopératif)

✓ Le déroulement dans le temps (simultané ou séquentiel)

✓ L’information dont disposent les agents (information parfaite ≠

imparfaite; complète ≠ incomplète)

6
 Introduction
4. Jeux coopératifs et jeux non-coopératifs
Un jeu coopératif est un jeu de société dans lequel tous les joueurs
gagnent ou perdent ensemble. Au lieu de jouer en opposition les uns
contre les autres, les joueurs jouent conjointement ou ensemble pour
réaliser un ou plusieurs objectifs communs, hors de tout esprit
de compétition.

Un jeux non-coopératif correspond à des situations d'interactions entre

individus libres dans leurs choix et poursuivant des objectifs propres et
indépendants. Ces individus ne communiquent pas avant le jeu et n'ont pas
nécessairement le moyen de s'engager à poursuivre une stratégie
particulière.

7
 Introduction
5. Jeux simultanés et jeux séquentiels
Un jeu simultané (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.

Jeu séquentiel spécifie le déroulement exacte du jeu; chaque joueur

considère son plan d’action non seulement au début du jeu mais aussi
chaque fois qu’il doit prendre une décision pendant le déroulement du jeu.

8
 Introduction
6. Nature de l’information
L’information est parfaite si chaque joueur est parfaitement informé des
actions passées des autres joueurs. Le jeu d’échecs: les joueurs observent
tous les coups joués

L’information est imparfaite quand un joueur ignore certains des choix qui
ont été effectués avant le sien. Le jeu de la bataille navale: ignore
l’emplacement choisi par l’adversaire pour chacun de ses navires.

Un jeu est à information complète si chaque joueur connaît parfaitement

la structure du jeu (ses possibilités d'action, les possibilités d'action des
autres joueurs, les gains résultants de ces actions, les motivations des
autres joueurs).

Les jeux est à information incomplète sont des situations où l'une des
conditions n'est pas vérifiée. 9
 Introduction
7. Comportement rationnel
Un joueur rationnel:

✓ est conscient des alternatifs,

✓ fait des anticipations sur les éléments inconnus,

✓ possède des préférences claires,

✓ choisit délibérément son action après un processus d’optimisation.

10
 Jeux, stratégies et information
A. Représentation des situations d’interaction
Les jeux non-coopératifs sont caractérisés par les éléments suivants:

✓ Un petit nombre de joueurs qui interagissent,

✓ Les décisions de chaque joueur influencent les gains des autres,

✓ La prise en compte de l’information dont chaque joueur dispose au

moment de prendre sa décision,

✓ La prise en compte du déroulement des décisions dans le temps

(simultanées ou séquentielles)

Les décisions simultanées sont en général représentées sous la forme d’un

tableau (jeux en forme normale). Les décisions séquentielles sont
représentées sous la forme d’un arbre (jeux en forme extensive).
11
 Jeux, stratégies et information
1. La frome normale d’un jeu
Un jeu en forme normale est décrit par les éléments suivants:
Un ensemble n de joueurs : 𝐼 = 1, 2, … , 𝑁 .

Pour chaque joueur iI, un ensemble de stratégies 𝑆𝑖 = si1 , si2 , … , sik i où ki

le nombre de stratégies disponibles pour le joueur i et siSi est une
stratégie particulière du joueur i.
Si chaque joueur choisit une stratégie si, nous pouvons représenter le
résultat (profil de stratégies) du jeu par un vecteur qui contient toutes ces
stratégies: s(s1, s2, …,sn).
Pour chaque joueur i, une fonction de gain (ui) qui représente les
préférences du joueur i en donnant la valeur pour le joueur i de chaque
résultat du jeu: ui(s). 𝑢 : 𝑆 = 𝑋𝑆 → ℝ
𝑖 𝑖

𝑠 ≡ 𝑠1 , 𝑠2 , … , 𝑠𝑛 → 𝑢𝑖 𝑠
12
 Jeux, stratégies et information
Exemple (le dilemme du prisonnier)
Deux individus (Bonnie et Clyde) sont arrêtés par la police suite à un vol à
main armée et ils sont enfermés dans deux cellules séparées sans
possibilité de communication. Chaque individu est interrogé séparément et
il a le choix entre nier d’avoir commis le vol (stratégie N) ou dénoncer son
complice comme seul responsable (stratégie D).
Si Bonnie et Clyde dénoncent tous les deux, ils sont condamnés à 8 ans de
prison.
S’ils nient tous les deux, ils auront 1 année de prison du fait d’absence de
preuves accablantes.
Si un seul dénonce, il est relâché en récompense de sa coopération et
l’autre est condamné à 10 ans de prison.
Type de jeu, Les joueurs, stratégies de chaque joueur, Les résultats
possible du jeu, Les gains de joueurs, et la forme du jeu? 13
 Jeux, stratégies et information
Exemple (le dilemme du prisonnier)
Type de jeu : non-coopératif
Les joueurs: n=2, I={1,2}={Bonnie, Clyde}
L’ensemble de stratégies de chaque joueur: S1=S2={N,D}
Les résultat possible du jeu : S={(N,N), (N,D), (D,N), (D,D)}
Les gains de joueurs sont symétriques:
u1(N,N) = u2(N,N) = -1
Clyde
u1(N,D) = u2(D,N) = -10
N D
u1(D,N) = u2(N,D) = 0 N (-1,-1) (-10,0)
Bonnie
u1(D,D) = u2(D,D) = -8 D (0,-10) (-8,-8)

14
 Jeux, stratégies et information
2. La frome extensive d’un jeu
Un jeu en forme extensive est donné par un arbre de jeu contenant un
nœud initial, des nœuds de décisions, des nœuds terminaux et des
branches reliant chaque nœud à ceux qui lui succèdent.
✓ Un ensemble de joueurs n≥1, indexés par i = 1, 2, …,n.
✓ Pour chaque nœud de décision, le nom du joueur qui a le droit de choisir
une stratégie à ce nœud.
✓ Pour chaque joueur i, la spécification de l’ensemble des actions permises
à chaque nœud où il est susceptible de prendre une décision.
✓ La spécification des gains de chaque joueur à chaque nœud terminal.

15
 Jeux, stratégies et information
2. La frome extensive d’un jeu

Considérons le problème d’entrée d’une firme dans le marché d’un

monopole.
1. L'entrant (E) doit choisir entre Entrer ou Ne pas entrer.
2. S'il entre, la firme installée (I) peut choisir de le Combattre en
cassant les prix ou de Coopérer avec lui, de manière a créer un
monopole joint .
(uE, uI)
Coopérer (40,50)
Entrer
E • I •
Non
(0,300) Combattre (-10,0)

16
 Jeux, information et stratégies
B. Représentation de l’information
A chaque étape d'un jeu en forme extensive, on appelle un ensemble
d'information (hi) la collection de tous les nœuds que le joueur qui doit
jouer à cette étape (i) ne peut distinguer, compte tenu de l'information
dont il dispose. Chaque nœud contenu dans hi contient alors exactement le
même ensemble d'actions localement disponibles. On note par Hi
l'ensemble des ensembles d'information du joueur i.

On représente chaque ensemble d'information en reliant par une courbe

en pointille les nœuds qui appartiennent à cet ensemble.

17
 Jeux, information et stratégies
B. Représentation de l’information
L'ensemble C = {C 1, C 2} est l'ensemble d'information de Clyde qui résulte
du fait qu'il ne peut observer le choix initial de Bonnie. II ne peut dire par
conséquent s'il doit faire face à une dénonciation par Bonnie ou non. On
représente cet ensemble d'information par une ligne en pointille qui relie
les deux sommets qu'il contient.

18
 Jeux, information et stratégies
B. Représentation de l’information
Un jeu en forme extensive est:

✓ Un jeu avec information imparfaite si au moins un ensemble

d'information contient plus d'un nœud.

✓ Un jeu avec information parfaite si chaque ensemble d'information est

réduit à un seul nœud.

Un jeu est à information incomplète si au moins un des joueurs ne connait

pas parfaitement la structure du jeu. Dans le cas contraire, il est à
information complète.

19
 Jeux, information et stratégies
C. Définition des stratégies
Une stratégie d'un joueur doit spécifier une action pour ce joueur chaque
fois qu'il est susceptible de jouer (s'il joue à plusieurs tours du jeu, nous
devons spécifier une action pour chacun des tours).

Un profil de stratégies (résultat) spécifie un déroulement complet du jeu

en précisant une stratégie par joueur.

20
 Jeux, information et stratégies
C. Définition des stratégies
Le jeu de l‘entrée II
Le jeu commence par la décision de l'entrant potentiel (E): il doit choisir s'il
met en place les capacités de production nécessaires à son entrée sur ce
nouveau marche. Ayant observe cette décision, la firme installée (I) doit
choisir si elle augmente ses propres capacités de production ou non.
L'entrant doit alors prendre sa décision de procéder effectivement à la
production du bien ou non et cela, sans pouvoir observer la décision de la
firme installée. Si E choisit dès le début de ne pas installer de capacités de
production, le problème de l'entrée ne se pose plus et I garde son
monopole.

21
 Jeux, information et stratégies
C. Définition des stratégies

chaque stratégie de E doit préciser une action pour l'ensemble d'information E0

et une autre pour E1 : (Non/E0, Produire/E1) est une stratégie complète de E.

((Non/E0, Produire/E1), Non/I): est un profil de stratégies complet de ce jeu.

22
 Jeux, information et stratégies
C. Définition des stratégies

Le joueur E possède deux ensembles d'information (E0 et E1) et donc

chacune de ses stratégies pures doit préciser une action en E0 et une autre
en E1 :

SE={(Installer/E0,Produire/E1) , (Installer/E0,Non/E1) , (Non/E0,Produire/E1) ,

(Non/E0,Non/E1) }

Le joueur I possède un seul ensemble d' information (I) et il dispose de 2

stratégies a cet ensemble d'information.

SI = {Augmenter/I, Non/I} = {Augmenter, Non}

23
 Jeux, information et stratégies
C. Définition des stratégies
Le joueur I possède un seul ensemble d' information (I) et il dispose de 2
stratégies a cet ensemble d'information.

Les gains (-50, 40) correspondent donc à :

✓ uE((lnstaller, Produire), Augmenter)= -50 pour l'entrant potentiel

✓ uI((Installer, Produire), Augmenter)= 40 pour la firme installée.

24
 Jeux, information et stratégies
C. Définition des stratégies

Une stratégie pure du joueur i est un plan d’actions qui prescrit une action
de ce joueur pour chaque fois qu’il est susceptible de jouer. On note par Si
l’ensemble des stratégies pures du joueur i et par siSi une stratégie pure
de ce joueur.

Une stratégie mixte du joueur i est une mesure de probabilités pi définie

sur l'ensemble de stratégies pures du joueur i. On note Pi l'ensemble des
stratégies mixtes du joueur i. piPi correspond donc à une stratégie mixte
du joueur i.

25
 Jeux, information et stratégies
C. Définition des stratégies
Une stratégie mixte du joueur E va assigner des probabilités à chacune de
ses stratégies pures pE(s)  [0, 1] avec :
𝑝𝐸 𝑠 = 1
𝑠∈𝑆𝐸
Un exemple de stratégie mixte, pE est
pE(Installer/E0 , Produire/ E1) = 1/5
pE(Non/E0, Produire/ E1) = 1/5
pE(Installer/E0, Non/ E1) = 3/5
pE(Non/E0 , Non/E1) = 0
Un autre exemple:
pE(Installer/E0 , Produire/ E1) = 1
les stratégies pures sont des stratégies mixtes dégénérées (le poids des
autres stratégies pures étant nuls).
26
 Jeux, information et stratégies
C. Définition des stratégies
Stratégies dans un jeu en forme extensive:

Une stratégie locale du joueur i est similaire à une stratégie mixte, sauf
qu’elle est définie au niveau d'un ensemble d'information, au lieu du jeu
global. Pour un joueur i, elle définit par conséquent, pour chaque ensemble
d'information h, une mesure de probabilités sur l'ensemble des actions
disponibles en cet ensemble d'information. On la note par ih, (la stratégie
locale du joueur i a son ensemble d'information h) et ih, est l'ensemble
des stratégies locales de i pour l'ensemble d'information h.

Une stratégie comportementale du joueur i est un vecteur de stratégies

locales de ce joueur, contenant une stratégie comportementale par
ensemble d’information de ce joueur. On la note par i et i est l'ensemble
des stratégies comportementales du joueur i. 27
 Jeux, information et stratégies
C. Définition des stratégies
Pour les stratégies locales, nous devons donc avoir ih(si)  [0, 1] avec :

Pour le joueur E, le profil de stratégies locales suivant forme un exemple de

stratégie comportementale :

Les stratégies pures et mixtes existent pour tout type de jeu, tandis que les
stratégies locales et comportementales ne peuvent être définies que dans
les jeux en forme extensive (car on a besoin de connaitre le déroulement
du jeu). 28
 Jeux, information et stratégies
D. Solutions et équilibres d’un jeu
Considérons le profil de stratégies qui contient les stratégies de tous Les
joueurs sauf le joueur i. Nous pouvons alors le noter de la manière suivante :

Le profil de stratégies complet s correspond alors à s = (si, s-i).

Elimination des stratégies équivalentes

Deux stratégies si et si’ sont équivalentes si et seulement si, pour tout profil
de stratégies donné des autres joueurs, tous les joueurs obtiennent la même
utilité quand i joue si ou si’

Toutes les stratégies équivalentes à une stratégie si forment une classe

d’équivalence. 29
 Jeux, information et stratégies
D. Solutions et équilibres d’un jeu
La forme normale réduite d'un jeu s'obtient a partir de la forme normale
initiale en remplaçant toutes les stratégies d'une classe d’équivalence par
une seule stratégie.

30
 Jeux, information et stratégies
D. Solutions et équilibres d’un jeu
Elimination des stratégies dominées

La stratégie pi du joueur i est strictement dominée par la stratégie pi’ si et

seulement si, quelque soit le comportement des autres joueurs, le joueur i
obtient avec pi une utilité strictement inferieure a celle obtenue avec pi’:

La stratégie pi est faiblement dominée par pi’ si l’inégalité est faible pour
toutes les stratégies des autres joueurs et qu'il existe au moins un profil de
stratégies des autres joueurs pour lequel l’utilité avec pi est strictement
inferieure a celle avec pi’:

31
 Jeux, information et stratégies
D. Solutions et équilibres d’un jeu

32
 Jeux, information et stratégies
D. Solutions et équilibres d’un jeu

Jacqueline
O F
O (2 , 1) (0, 0)
Paul
F (0 , 0) (1 , 2)

Ce jeu ne comporte pas de stratégies dominées. Nous devons donc

introduire un autre concept d’équilibre pour pouvoir prédire la
solution de ce type de jeux.

33