# Théorie des jeux

La théorie des jeux est un domaine qui est née dans les années 1920 avec le travail de Ernest Zermelo. Il s'est notamment intéressé à la résolution du jeu des échecs.

C'est un domaine mathématique qui s'intérese au concept de jeu : les joueurs (ou agents) doivent prendre des décisions (les strategies). En fonction des choix de tous, on calcule des gains (les utilites).

[TOC]

## Les jeux

### Définition d'un jeu
:::success
On définit un __jeu__ sous la forme du triplet suivant :
* un __ensemble des joueurs $P$__
* un __ensemble des stratégies $S_p$ des joueurs $p \in P$__
* un ensemble de gain par joueur $G_p$, remplacé par __l'utilité $u_p : S_p \to G_p$__

En conclusion, un jeu est tout triplet défini comme __$(P, (S_p)_{p \in P}, (U_p)_{p \in P})$__.
:::

:::warning
Attention à différencier action et stratégie. Une action est quelque chose qu'on fait à un moment donné et une stratégie qui est une fonction qui renvoie un coup en fonction d'un état donné.
:::
#### Exemples
:::info
Le jeu des echecs :
* ensemble des joueurs $P = \{Blancs, Noirs\}$
* fonction qui renvoie les coups légaux à partir d'une position
* fonction qui renvoie $\{win ; draw ; loose\}$ en fonction de la board

Le [jeu de la vie](https://www.youtube.com/watch?v=S-W0NX97DB0) peut être modélisé comme un jeu à zéro joueur.

La bourse :
* Tous les acteurs des marchés financiers
* Ensemble des actions à faire (acheter, vendre ou ne rien faire) en fonction du temps
* Somme obtenue ou due
:::
### Un exemple pratique du dilemme des prisoniers
:::success
* Pour deux personnes
* Je dénonce mon camarade ou je ne le dénonce pas
* Les utilités sont dans la matrice des Paiements

<br/>
<center>

| J1 / J2 | Se taire | Parler |
| -------- | -------- | ------- |
| Se taire | (-3;-3) | (-10;0) |
| Parler | (0 ;-10) | (-5;-5) |

</center>
:::

Ce jeux contient un __équilibre de Nash__. C'est un point fixe d'un processus où les joueurs, maximisent successicement leur gain après avoir observé celui des autres. Cela peut être considéré comme une solution mathématique, mais pas forcément si on l'entend comme la prédictions que feront effectivement les joueurs placés dans la situation décrite par le jeu - même en supposant qu'ils soient rationels.

### Formalisation
:::success
* Le nombre de joueur est $|P|$
* Si $P$ est non-ordonné, alors le jeu est __simultané__ : les joueurs jouent en même temps. Sinon le jeu est non-simultané, ou __alterné__
Exemple : le dilemme du prisonier est simultané tandis que les echecs sont alternés
* $\sigma \in S_p$ est simultané si l'on dispose de $\sigma= (\sigma_p)_{p \in P}$, on parle alors de __profil stratégique__.
$\sigma$ profil stratégique $\Leftrightarrow \sigma \in \prod_{p \in P} S_p$
* Fonction d'utilité : $u_p : \prod_{p \in P} S_p \to G_p$
NB : on peut s'en passer en posant $G = \bigcup_{p \in P}G_p$
* Calcul d'un __gain__ réalisé pour une partie :
$\forall p \in P,\;u_p(\sigma)=g_p$ où $\sigma$ est le profil stratégique.
:::
La théorie de la décision est la théorie des jeux avec un seul joueur.

#### Exemple
:::info
Dans le dilemme du prisonier on a :
$$
\begin{aligned}
S &= \prod_{p \in P} S_p \\
&= S_A \times S_B \\
&= \{Coop, Trahir\} \times \{Coop, Trahir\} \\
&= \{(Coop; Coop) ; (Coop ; Trahir) ; (Trahir ; Coop) ; (Trahir; Trahir)\}
\end{aligned}
$$
:::

### Jeux en bimatriciel
:::success
On se donne $(A;B) \in M_{n,\,k}(\Bbb R)^2$.
On définit implicitement un jeu $\mathscr P = (A;B)$ dit __bimatriciel__ par :
* $\mathscr P = (A; B)$ (simultané)
* $S_A = \{1;2;...;n\} = [[1;n]]$ "choix ligne"
$S_B = [[1;n]]$ "choix colonne"
* $\forall (i;j) \in [[1;n]]^2$
\begin{cases}
u_A(i,j) = A_{ij} = a_{ij} \\
u_B(i,j) = B_{ij} = b_{ij}
\end{cases}

Avec $G_A = G_B = \Bbb R$ muni de son ordre $\le$ usuel (comme préférence de joueur).
:::

#### Exemple : $\mathscr P = DP$ en bimatriciel
:::info
$A = \begin{pmatrix} -3 & -10 \\ 0 & -5 \end{pmatrix}$ et $B = \,^tA$$
:::

### Notion de préférence
:::success
Posons pour $p \in P$ un esemble $G_p$ de gain sur lesquel on définit $\prec_p$ la relation binaire nommée __"relation de préférence de p"__.

* $g_1 \prec_p g_2$ signifie "le joueur $p$ préfère $g_2$ à $g_1$"

On dira que $g_1 \neq g_2$ sont __indifférents__ pour $p \in P$ lorsqu'on n'a ni $g_1 \prec_p g_2$ ni $g_2 \prec_p g_1$.
:::

:::info
À priori dans le $DP$ on a $–3 \prec_A 0$ et $–10 \prec_B –5$.

:::

### Notion de rationalité
:::success
Un joueur $p \in P$ est dit __rationel__ ssi $(G_p ; \prec_p)$ est un ensemble ordonné.
:::
:::warning
NB : On ne lui demande pas d'être totalement rationel.
:::
#### Cas particulier

Si $\prec_p$ est totale linéaire on peut réaliser un plongement $(G_p; \prec_p) \to (R ; s)$

Ainsi, si tous les $p \in P$ valident cette hypothèse on peut numériser le jeu (tout gain devient un réel).

### À propos de l'information (du jeu)
:::success
On dira qu'un jeu est __complet__ si tout $p \in P$ a accès à la description du triplet $(P, (S_p)_{p \in P}, (U_p)_{p \in P}))$. On dira qu'il est __incomplet__ sinon.
:::
:::info
Par exemple, la bourse a un caractère incomplet. La plupart des "jeux " courants sont à information complète.
:::
:::success
On dira qu'un jeu est __parfait__ si tout $p \in P$ a accès à la connaissance à tout instant de la description de l'état du jeu et de ses conséquences. On dira qu'il est __imparfait__ sinon.
:::

#### Exemple
:::info
* Échecs : information parfaite (Dames, Go, etc, …)
* DP : imparfaite
* Carte : imparfaite
* PFC : imparfaite
:::

#### Vocabulaire

Win / Loose game : cas où $G_p = \{win, loose\}$ avec $loose \prec_p win$

Win / Draw / Loose game : sous couvert de rationnalité, on code $–1 : loose,\; 0 : draw,\; +1 : win$

### Théorème de Zermelo
:::success
Tout jeu à deux joueurs, alterné, à information parfaire et complète, sans aléatoire de type win / loose (à somme nulle), à nombre fini d'état et durée finie (horizon fini) est tel que l'un des joueurs possède une stratégie gagnante.

$$
\exists p \in P \; \exists \sigma_p \in S_p \; \forall {\tau_q}_{(q \neq p)} \in S_q \; u_p(\sigma_p;\tau_q) = win
$$

Analogue avec win / draw / loose :

$$
\exists p \in P \; \exists \sigma_p \in S_p \; \forall \tau_q \in S_q \; u_p(\sigma_p;\tau_q) \ge draw
$$
:::

#### Démonstration
Création de brute-force

### Jeu à somme nulle
:::success
Si $P$ est numérisable alors $P$ est dit à somme nulle signifie :
$$
\forall \sigma \in \prod_{p \in P} S_p \quad \sum u_p(\sigma) = 0
$$
:::
#### Exemple
:::info
Beaucoup de win / loose et le poker
:::

### Propriété de stratégie
:::success
Une stratégie $\sigma_p \in S_p$ d'un joueur $p \in S$ est dite __dominée__ lorsque :
$$
\forall(\sigma_{-p}) \in \prod_{q \neq p} S_q \quad \exists_{\sigma_p^´ \neq \sigma_p} \sigma_p^´ \in S_p \quad u_p(\sigma_p; \sigma_{-p}) \prec_p u_p(\sigma_p^´; \sigma_{-p})
$$
:::
Un joueur rationnel ne cherche pas à jouer une stratégie donnée.

-> prétraitement : procédure d'élimination des stratégies dominées

#### Exemple
:::info
$P = (A ; B)$
Partie incomprise. Compléter avec 20210908_113808.jpg ou suivante.
:::

### Interractions en jeu : Best Responses
:::success
Soit $p \in P$ un joueur et $\sigma_{-p}$ profil stratégique (tronqué de $\sigma_p$).

On définit :
$$
BR(\sigma_{-p}) = \{\sigma_p \in S_p \;|\; u_p(\sigma_p ; \sigma_{-p}) = max_{\ast \in S_p}(u_p(\ast; \sigma_{-p})\}
$$
:::

#### Exemple
:::info
Avec $(A;B)$ précédent, $BR(\tau_2) = {\sigma_3}$ car $u_A(\sigma_3; \tau_2) = max(0;1)$.
:::
#### Exemple bis
:::info
Considérons :
$$
C =
\begin{pmatrix}
0 & 1 & 3 \\ 4 & -1 & 2 \\ 4 & 2 & 1
\end{pmatrix}
$$
avec $\{\sigma_1, \sigma_2, \sigma_3\}$ les lignes et $\{\tau_1, \tau_2, \tau_3\}$ les colonnes. Alors :
$$
BR(\tau_1) = \{\sigma_2;\sigma_3\}
$$
:::
#### Convention
On écrit $br(\sigma_{-p})$ pour décrire l'arbitraire des éléments de $BR(\sigma_{-p})$.

### Équilibre de Nash
:::success
Un profil stratégique $\sigma = (\sigma_p)_{p \in P}$ est dit __équilibre de Nash__ lorsque :
$$
\forall p \in P \quad \sigma_p = br(\sigma_{-p})
$$
:::

#### Analogie
$$
\forall p \in P \quad \sigma_p \in BR(\sigma_{-p})
$$

#### Exemple avec le Dilemme du prisonnier
:::info
$A = \begin{pmatrix} -3 & -10 \\ 0 & -5 \end{pmatrix}$ et $B = \,^tA$. On note également $T=Trahir$ et $C=Cooperer$

On propose $(T_A;T_B)$ un équilibre de Nash.

$$
BR(T_B) = \{T_A\} \text{ et } BR(T_A) = \{T_B\}
$$

On a $(T_A; T_B) = (br(T_B);br(T_A))$ est bien un équilibre de Nash.
:::

#### Exemple avec Pierre-Feuille-Ciseaux
:::info
$$
P = \{A;B\} \text{, } S_A = S_B = \{P;F;C\}
$$
$$
A =
\begin{pmatrix}
0 & -1 & 1 \\
1 & 0 & -1 \\
-1 & 1 & 0 \\
\end{pmatrix}
\text{ et } B = -A
$$
On a bien un jeu à somme nulle et sans équilibre de Nash.
:::

## Partie 2
:::warning
stratégies pures --> stratégies mixtes
:::
À partir d'un jeu $\Gamma$ on crée un nouveau jeu $\Gamma '$ de façon suivante:
* les joueurs sont inchangés
* _nouvelles stratégies :_
Si $S_p$ ancien ensemble de strat du joueur $p$, le nouveau pour $\Gamma'$ devient :
$$
\Delta(S_p) = { \mu : \text{distrib prob sur} \ S_p }
$$
Si on a $S_p =\{ \sigma_1(p), \dots, \sigma_n(p) \}$ alors on peut assimiler le nouvel ensemble pour le nouveau jeu à:
$$
\Delta_p = \{ x \in \mathbb{R}^n \ | \ \forall k \leq n \ x_k \geq 0 \ \ \wedge \sum_{k=1}^n x_k = 1 \}
$$
:::warning
Fait pensser a un simplexe !
polygone en dimension n
[probas] -> [analyse convexe]
:::

### Interprétation
Les vecteurs de base $e_i$ de $\mathbb{R}^n$ seront les analogues de $\sigma_i(p)$. On a alors :
$$
x_i = \mathbb{P}[p \text{ plays } \sigma_i(p)]
$$

_nouvelles fonctions d'utilité :_
pour le joueur $p$ on prend comme u
nouvelle utilité les espérances associées aux gains aléatoires induits par les distributions.
Si $X_p$ est la stratégie aléa jouée par $p$ alors:
$$
v_p(x_1 \dots x_P) = \mathbb{E}[u_p(X_1 \dots X_P)] \text{ avec } P = |\mathcal{P}|
$$

Discussions : le choix de l'espérance est remis en question dans de nombreux travaux
-> cette étude sera abordée ultérieurement

### Cas deux joueurs (bimatriciels)
On a donc pour les matrices de gain $(A;B)$ de nouvelles stratégies codififées par des vecteurs $x$ et $y$ de $\mathbb{R}^n$ et $\mathbb{R}^k$ où: $n = |S_A|$ et $k=|S_B|$.

:::success
On appelle :
* __stratégies pures__ : le vecteur de base associée à stratégie du jeu d'origine
* __stratégies mixtes__ : tout vecteur $x \in \Delta_p$ non "de base"
en particulier, si $x$ désigne un stratégie mixte, il existe $i$ tel que $0 < x_i < 1$
:::

### Théorème (cas bimatriciel normal)
:::success
Si $A$ joue $x$ et $B$ joue $y$ vecteurs stratégies dans le jeu sous forme normal alors :
$$
u_A(x;y) = \ ^tx A y \text{ et } u_B(x;y) = \ ^t x B y
$$
:::

#### Jeu normal bimatriciel : Exemple de PFC
$$
A =
\begin{pmatrix}
0 & -1 & 1 \\
1 & 0 & -1 \\
-1 & 1 & 0
\end{pmatrix}
\text{ avec }
B = -A = \,^tA
$$

Si $A$ joue : $\ ^tx_1 = \begin{pmatrix}\frac{1}{2} & \frac{1}{6} & \frac{1}{3}\end{pmatrix} = \begin{pmatrix} \mathbb P(P) & \mathbb P(F) & \mathbb P(C))\end{pmatrix}$ et B joue : $\ ^ty_1 = \begin{pmatrix}\frac{1}{4} & \frac{1}{4} & \frac{1}{2}\end{pmatrix}$

#### Calcul de gain :
$$
\begin{aligned}
u_A(x_1, y_1) &= \,^tx_1 A y_1 \\
&= \frac{1}{12}
\end{aligned}
$$
Ce qui ressemble à de l'algèbre linéaire (produit scalaire)

--------------------------------------
### Introduction aux jeux sous forme normale
Principe :
stratégies pures --> stratégies mixtes
à partir d'un jeu $\Gamma$ on crée un nouveau jeu $\Gamma '$ de façon suivante :
les joueurs sont inchangés
nouvelles stratégies :
Si $S_p$ ancien ensemble de strat du joueur $p$, le nouveau pour $\Gamma'$ devient :
$$\Delta(S_p) = \{\mu : \text{distrib prob sur} \ S_p\}$$
examinons le cas fini
si on a $S_p =\{ \sigma_1(p) \dots \sigma_n(p) \}$ alors on peut assimiler le nouvel ensemble pour le nouveau jeu à :
=tex \Delta_p = { x \in \mathbb{R}^n \ | \ \forall k \leq n \ xk \geq 0 \ \ \wedge \sum{k=1}^n x_k = 1 }

Cela fait penser à un simplex !
polgone en dimension n
[probas] -> [analyse convexe]
interprétation :
les vecteurs de base $e_i$ de $\mathbb{R}^n$ seront les analogues de $\sigma_i(p)$

on a alors $x_i$ vaut $\mathbb{P}[\text{player } \ p \ \text{plays } \ \sigma_i(p)]$

nouvelles fonctions d'utilité :
pour le joueur $p$ on prend comme u

nouvelle utilité les espérances associées aux gains aléatoires induits par les distribu
Si $X_p$ est la stratégie aléa jouée par $p$ alors :

=tex v_p(x_1 \dots x_P) = \mathbb{E}[u_p(X_1 \dots X_P]
avec $P = |\mathcal{P}|$

discussions : le choix de l'espérance est remis en question dans de nombreux travaux
-> cette étude sera abordée ultérieurement
Cas deux joueurs (bimatriciels)
On a donc pour les matrices de gain $(A;B)$ de nouvelles stratégies codififées par des vecteurs $x$ et $y$ de $\mathbb{R}^n$ et $\mathbb{R}^k$ où:

$n = |S_A|$ et $k=|S_B|$

Vocabulaire :
stratégies pure : vecteur de base associée à stratégie du jeu d'origine
Stratégies mixtes : tout vecteur $x \in \Delta_p$ non "de base"

en particulier, si $x$ désigne un stratégie mixte, il existe $i$ tel que $0 < x_i < 1$

théorème (cas bimatriciel normal)
Si $A$ joue $x$ et $B$ joue $y$ vecteurs stratégies dans le jeu sous forme normal alors :

$u_A(x;y) = \ \ x^T A y$