\documentclass[XUPS,XML,SOM,Unicode,francais,ThmDefs]{cedram}
\OneNumberAllTheorems
\setcounter{tocdepth}{2}

\newcommand\reals{\mathbb R}\let\R\reals
\let\vare\varepsilon

\DeclareMathOperator{\co}{co}
\DeclareMathOperator{\MRR}{MR}\let\MR\MRR

\begin{document}
\frontmatter

\title{Jeux sous forme normale}
\author[\initial{T.} \lastname{Tomala}]{\firstname{Tristan} \lastname{Tomala}}
\address{Ceremade,
Université Paris Dauphine,
Place du Maréchal de Lattre de Tassigny,
75775 Paris cedex 16}

\email{tomala@hec.fr}
\urladdr{https://sites.google.com/site/tristantomala2}

\thanks{Journées X-UPS 2006. Théorie des jeux -- Introduction à la théorie des jeux répétés. Éditions de l'École polytechnique, 2006}

\maketitle

\tableofcontents
\mainmatter

\section{Préliminaires}

On appelle \emph{jeu sous forme normale} ou jeu \emph{sous forme stratégique} la donnée d'un ensemble $N$ de joueurs, d'une famille d'ensembles de stratégies (ou d'actions) $(A^i)_{i\in N}$ et d'une famille de fonctions de paiements $(g^i)_{i\in N}$ avec $g^i:\prod_{j\in N}A^j \to \reals$. L'ensemble des joueurs sera toujours supposé fini et non vide. Les ensembles d'actions seront toujours supposés non vides et on parlera de \emph{jeu fini} lorsque $A^i$ est fini pour tout $i$.

Un jeu sous forme normale représente une interaction entre joueurs rationnels: chaque joueur $i\in N$ choisit une action $a^i\in A^i$, les choix étant simultanés, et si $a=(a^i)_{i\in N}$ est le \emph{profil} d'actions choisi, le joueur $i$ reçoit le paiement $g^i(a)$. Tous les joueurs connaissent le jeu et le but du joueur $i$ est d'obtenir un paiement le plus grand possible. Un~jeu à un joueur est donc simplement un problème de maximisation. Dès qu'il y a au moins deux joueurs, le joueur $i$ ne contrôle que partiellement son paiement et la notion de \emph{bonne} stratégie n'est pas claire. Les exemples usuels suivants permettent de s'en convaincre. Les matrices ci-dessous représentent des jeux à deux joueurs dans lesquels le joueur~1 choisit la ligne, le joueur~2 la colonne et l'entrée de la matrice est le couple de paiements $(g^1,g^2)$.

\subsubsection*{Le Dilemme du Prisonnier} Deux criminels sont arrêtés et interrogés dans des pièces séparées. Ils ont le choix entre dénoncer leur complice $(D)$ où se taire et donc coopérer avec leur complice $(C)$. Un criminel dénoncé par son complice se verra infliger une lourde peine et une peine légère dans le cas contraire. De plus le fait de dénoncer l'autre permet d'obtenir une remise de peine, que l'on soit soi-même dénoncé ou pas. Chaque joueur classe les issues du jeu par préférence décroissante selon l'ordre suivant: (ne pas être dénoncé et dénoncer), (ne pas être dénoncé et ne pas dénoncer), (être dénoncé et dénoncer), (être dénoncé et ne pas dénoncer). Attribuant des paiements numériques à ces alternatives, nous formalisons cette situation par le jeu suivant:
\[
\begin{array}{rc}
&C\hspace*{5mm}D
\\
\begin{array}{r}
C\\D
\end{array}
&\arraycolsep5pt\begin{array}{|c|c|}
\hline
3,3 & 0,4
\\
\hline 
4,0 & 1,1\\
\hline
\end{array}
\end{array}
\]

\subsubsection*{Un jeu de coordination} Deux amis veulent se rencontrer au lieu $(A)$ ou au lieu $(B)$. Leurs paiements sont égaux et valent 1 s'ils se rencontrent effectivement et 0 sinon. Ceci se représente par le jeu:
\[
\begin{array}{rc}
&A\hspace*{5mm}B
\\
\begin{array}{r}
A\\B
\end{array}
&\arraycolsep5pt\begin{array}{|c|c|}
\hline
1,1 & 0,0
\\
\hline 
0,0 & 1,1\\
\hline
\end{array}
\end{array}
\]

\subsubsection*{Le jeu \og Matching Pennies\fg} Chaque joueur possède une pièce de monnaie et choisit secrètement de la mettre sur Pile $(P)$ ou sur Face~$(F)$. Le joueur~1 gagne si son choix est le même que celui du joueur~2 et, dans ce cas, le joueur~2 perd. Dans le cas contraire c'est~2 qui gagne et 1 qui perd. Ceci se représente par le jeu:
\[
\begin{array}{rc}
&P\hspace*{8mm}F
\\
\begin{array}{r}
P\\F
\end{array}
&\arraycolsep5pt\begin{array}{|c|c|}
\hline
1,-1 & -1,1
\\
\hline 
 -1,1 & 1,-1\\
\hline
\end{array}
\end{array}
\]

Commençons par donner quelques notions simples de \emph{bonne} stratégie. Nous adopterons les notations suivantes. Pour tout joueur $i$, $-i$ désigne l'ensemble des autres joueurs $N\setminus\left\{i\right\}$. Si $(E^i)_{i\in N}$ est une famille d'ensembles indexée par $N$, nous notons $E=\prod_{i\in N}E^i$, $E^{-i}=\prod_{j\neq i}E^i$. Un élément $e$ de $E$ pourra se noter $e=(e^1,\ldots, e^n)=(e^i)_{i\in N}=(e^i,e^{-i})$ cette dernière notation étant utilisée lorsque l'on veut séparer le joueur $i$ des autres.

\skpt
\begin{definition}
\begin{itemize}
\item
Une stratégie $a^i\in A^i$ du joueur $i$ est \emph{dominée} si
\[
\exists b^i\in A^i,\;\forall a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})\leq g^i(b^i,a^{-i}).
\]

\item
Une stratégie $a^i\in A^i$ du joueur $i$ est \emph{faiblement dominée} si
\[
\exists b^i\in A^i,\;
\begin{cases}
\forall a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})\leq g^i(b^i,a^{-i})& \text{et}\\
\exists a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})< g^i(b^i,a^{-i}).
\end{cases}
\]

\item
Une stratégie $a^i\in A^i$ du joueur $i$ est \emph{strictement dominée} si
\[
\exists b^i\in A^i,\;\forall a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})< g^i(b^i,a^{-i}).
\]

\item
Une stratégie $a^i\in A^i$ du joueur $i$ est \emph{dominante} si
\[
\forall b^i\in A^i,\;\forall a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})\geq g^i(b^i,a^{-i}).
\]

\item
Une stratégie $a^i\in A^i$ du joueur $i$ est \emph{faiblement dominante} si
\[
\forall b^i\in A^i,\;
\begin{cases}
\forall a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})\geq g^i(b^i,a^{-i})& \text{et}\\
\exists a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})> g^i(b^i,a^{-i}).
\end{cases}
\]

\item
Une stratégie $a^i\in A^i$ du joueur $i$ est \emph{strictement dominante} si
\[
\forall b^i\in A^i,\;\forall a^{-i}\in A^{-i},\quad g^i(a^i,a^{-i})> g^i(b^i,a^{-i}).
\]
\end{itemize}
\end{definition}

Un joueur rationnel ne jouera jamais de stratégie strictement dominée, jouera à coup sur une stratégie strictement dominante si elle existe (et alors elle est unique) et ne perd rien à jouer une stratégie dominante. On peut remarquer que dans le jeu du Dilemme du Prisonnier, la stratégie $D$ est strictement dominante pour chaque joueur, l'issue rationnelle du jeu est donc $(D,D)$.

Lorsque tous les joueurs sont rationnels et savent que leurs adversaires le sont, chacun peut supprimer ses propres stratégies strictement dominées et s'attendre à ce que les autres fassent de même. De~nouvelles stratégies strictement dominées peuvent alors apparaître dans le jeu réduit. On est donc conduit à itérer cette opération.

\subsubsection*{Procédure d'élimination itérée des stratégies strictement dominées (EISSD)}

Pour tout jeu $G=(N, (A^i)_{i\in N}, (g^i)_{i\in N})$ et tout joueur $i$, on note $SD^i(G)$ l'ensemble des stratégies du joueur $i$ strictement dominées dans $G$. Partons d'un jeu $G_0=(N, (A^i_0)_{i \in N}, (g^i)_{i\in N})$.
\begin{itemize}
\item
Pour tout $i\in N$, on pose
\[
A^i_1=A^i_0\setminus SD^i(G_0)\quad\text{et}\quad G_1=(N, (A^i_1)_{i\in N}, (g^i)_{i\in N}),
\]
jeu dans lequel les fonctions de paiement sont définies par restriction.
\item
Pour tout entier $k>1$ et tout $i\in N$, on pose
\[
A^i_k=A^i_{k-1}\setminus SD^i(G_{k-1})\quad\text{et}\quad G_k=(N, (A^i_k)_{i\in N}, (g^i)_{i\in N}).
\]

\item
Pour tout $i\in N$ on pose enfin
\[
A^i_\infty=\bigcap_k A^i_k\quad\text{et}\quad G_\infty=(N, (A^i_\infty)_{i\in N}, (g^i)_{i\in N}).
\]
\end{itemize}

On dit que $G_0$ est \emph{résoluble par EISSD} si pour tout joueur $i$, la~restriction de $g^i$ à $\prod_{i\in N}A^i_\infty$ est une application constante.

\subsubsection*{Le jeu de concurrence de Cournot} Deux entreprises produisent le même bien et choisissent la quantité à produire. Le prix de vente est une fonction décroissante de la somme des quantités, le bénéfice de chaque entreprise s'écrit comme la différence entre ses recettes et le coût total de production.

Prenons des paramètres $\alpha,\beta,\gamma>0$ avec $\alpha>\gamma$ et définissons le jeu suivant: $G=(A^1,A^2, g^1, g^2)$ dans lequel $A^1=A^2=\reals_+$ et pour chaque joueur $i$ et paire de stratégies $(a_1,a_2)$:
$$g^i(a^1,a^2)=a^i(\alpha-\beta(a^1+a^2))^+ -\gamma a^i$$

Ce jeu est résoluble par EISSD et on montre que, pour $i=1,2$, $A^i_\infty=\left\{\psfrac{\alpha-\gamma}{3\beta}\right\}$.

\subsubsection*{Deviner le demi-moyenne} Un autre exemple est le jeu à $n$ joueurs dans lequel chacun choisit un réel entre $0$ et $100$, le but étant d'être le plus proche possible de la demi-moyenne:
$$g^i(a)=-\bigg|a^i-\frac{1}{2n}\sum_{j=1}^n a^j\bigg|$$
Ce jeu est résoluble par EISSD et on a, pour tout $i\in N$, $A^i_\infty=\left\{0\right\}$.

Comme le montrent les jeux de coordination et Matching Pennies ci- dessus, bon nombre de jeux ne sont pas résolubles par cette simple méthode. Les deux parties suivantes donnent des notions de solutions pour lesquels on dispose de théorèmes d'existence relativement généraux. Nous commençons par traiter les jeux \emph{à somme nulle.}

\section{Jeux à somme nulle}

Un jeu à somme nulle est un jeu à deux joueurs $G=(A^1,A^2, g^1, g^2) $ tel que pour tous $(a^1,a^2)\in A$, $g^1(a^1,a^2)+g^2(a^1,a^2)=0$. Pour cette partie posons, $A^1=S$, $A^2=T$, $g^1=g$. Ainsi, un jeu à somme nulle est déterminé par une application $g:S\times T\to \reals$. Dans la suite, par souci de simplicité, nous supposerons $g$ bornée.

\Subsection{Notions de solutions}

\skpt
\begin{definition}
\begin{itemize}
\item
Le joueur~1 \emph{garantit} le paiement $d\in \reals$ si:
\[
\exists s\in S,\; \forall t\in T,\quad g(s,t)\ge d.
\]

\item
Le joueur~1 \emph{défend} le paiement $d\in \reals$ si:
\[
\forall t\in T,\; \exists s\in S,\quad g(s,t)\ge d.
\]

\item
Le joueur~2 \emph{garantit} le paiement $d\in \reals$ si:
\[
\exists t\in T,\; \forall s\in S,\quad g(s,t)\le d.
\]


\item
Le joueur~2 \emph{défend} le paiement $d\in \reals$ si:
\[
\forall s\in S,\; \exists t\in T,\quad g(s,t)\le d.
\]
\end{itemize}
\end{definition}

Les propriétés suivantes sont immédiates:

\begin{proposition}
Posons 
\[
\underline{v}(g)=\sup_{s\in S}\inf_{t\in T} g(s,t)\quad\text{et}\quad \overline{v}(g)=\inf_{t\in T}\sup_{s\in S} g(s,t).
\]
On a $\underline{v}(g)\le \overline{v}(g)$ et
\begin{align*}
\underline{v}(g)&=\sup\{d\mid 1\text{ garantit }d\}=\inf\{d\mid 2\text{ défend }d\},\\
\overline{v}(g)&=\sup\{d\mid 1\text{ défend }d\}=\inf\{d\mid 2\text{ garantit }d\}.
\end{align*}
\end{proposition}

On voit donc que, à $\varepsilon$ près, le joueur~1 peut faire en sorte que le~paiement soit au moins $\underline{v}(g)$ alors que le joueur~2 peut assurer que le~paiement ne soit pas plus que $\overline{v}(g)$. Lorsque ces deux quantités sont égales et que les deux joueurs sont rationnels, on peut penser que l'issue du jeu sera très proche de leur valeur commune. Ceci conduit aux définitions suivantes:

\skpt
\begin{definition}
\begin{itemize}
\item
On dit que le jeu $(S,T,g)$ \emph{a une valeur} lorsque $\underline{v}(g)=\overline{v}(g)$ et on note $v(g)$ cette valeur.
\item
Soit $\vare\ge 0$, on dit que $s\in S$ est une \emph{stratégie $\vare$-optimale} (ou~simplement optimale si $\vare=0$) du joueur~1 si la stratégie $s$ garantit $\underline{v}(g)-\vare$:
\[
\forall t\in T,\quad g(s,t)\ge \underline{v}(g)-\vare.
\]

\item
On dit que $t\in T$ est une \emph{stratégie $\vare$-optimale} du joueur~2 si la stratégie $t$ garantit $\overline{v}(g)+\vare$:
\[
\forall t\in T,\quad g(s,t)\le \overline{v}(g)+\vare.
\]

\item
Un couple $(\bar s,\bar t)$ est un point selle si:
\[
\forall (s,t),\quad g(s,\bar t)\le g(\bar s, \bar t) \le g(\bar s, t).
\]
\end{itemize}
\end{definition}

On a les propriétés suivantes:

\pagebreak[2]
\skpt
\begin{proposition}
\begin{itemize}
\item
Il existe une stratégie optimale pour le joueur~1 (\resp le joueur~2) si et seulement si\vspace*{-3pt}\enlargethispage{1.5\baselineskip}
\[
\underline{v}(g)=\max_{s\in S}\inf_{t\in T} g(s,t)\quad (\text{resp. } \overline{v}(g)=\min_{t\in T}\sup_{s\in S} g(s,t)).
\]

\item
S'il existe un point selle, alors le jeu a une valeur, les joueurs ont des stratégies optimales et on a:\vspace*{-3pt}
\[
v(g)=\max_{s\in S}\min_{t\in T}g(s,t)=\min_{t\in T}\max_{s\in S}g (s,t).
\]
De plus si on note $O^i$ l'ensemble des stratégies optimales du joueur $i=1,2$ et $S$ l'ensemble des points selles, on a $S=O^1\times O^2$.
\end{itemize}
\end{proposition}

\subsection{Un théorème d'existence} Le théorème principal d'existence de valeur dans les jeux à somme nulle est dû à Sion (1958) et généralise le célèbre théorème du minimax de Von Neumann (1928) (voir le paragraphe \ref{jeux_finis} ci-dessous).

Étant donné une fonction $f:X\to \reals$ où $X$ est un espace topologique, on dit que $f$ est semi-continue supérieurement (scs) si pour tout réel $c$, l'ensemble $\left\{x\mid  f(x)\ge c\right\}$ est fermé. On dit que $f$ est semi-continue inférieurement (sci) si $-f$ est scs. On vérifie facilement que l'infimum d'une famille de fonctions scs est scs et que si $f$ est scs pour toute suite $(x_{n})_{n}$ qui converge vers $x$, $\overline{\mathrm{lim}}_{n}f(x_{n})\le f(x)$.

Lorsque $X$ est un sous-ensemble convexe d'un espace vectoriel, on dit que $f$ est quasi-concave si pour tout réel $c$, l'ensemble $\left\{x\mid  f(x)\ge c\right\}$ est convexe. On dit que $f$ est quasi-convexe si $-f$ est quasi-concave.

\begin{theorem}\label{thm_Sion}
Soit $G=(S,T,g)$ un jeu à somme nulle. On suppose:
\begin{enumeratei}
\item
$S$ et $T$ sont des sous-ensembles convexes non vides d'espaces vectoriels topologiques, l'un d'entre eux étant compact;
\item
pour tout $(s_0,t_0)\in S\times T$ et tout réel $c$, les ensembles $\left\{s\in S\mid  g(s,t_0)\geq c\right\}$, $\left\{t\in T\mid  g(s_0,t)\le c\right\}$ sont convexes et fermés. 
\end{enumeratei}
Alors:
\begin{enumeratea}
\item
$\underline{v}(g)=\overline{v}(g)$;
\item
si $S$ (\resp $T$) est compact, le joueur~1 (\resp 2) a une stratégie optimale;
\item
l'ensemble des stratégies $\vare$-optimales ($\vare\ge 0$) pour le joueur~1 (\resp 2) est convexe fermé.
\end{enumeratea}
\end{theorem}

L'outil principal de la démonstration est le théorème de séparations des convexes. On utilise le lemme suivant:

\begin{lemma}\label{helly}
Soit $(F_i)_{i=1}^n$ une famille de sous-ensembles convexes compacts non vides d'un espace vectoriel topologique localement convexe séparé (evtlcs), telle que $\bigcup_{i=1}^n \!F_i$ est convexe et pour~tout~$j$,~\hbox{$\bigcap_{i\neq j}\!F_i\!\neq\! \emptyset$}. On a alors: $\bigcap_{i=1}^n F_i\neq\emptyset$.
\end{lemma}

\begin{proof} Par récurrence sur $n$, le cas $n=1$ étant clair, supposons le résultat vrai pour $n-1$ et faux pour $n$. Prenons une famille $(F_i)_{i=1}^n$ vérifiant les hypothèses du lemme, posons $F=\bigcap_{i<n}F_i$ et supposons $F\cap F_n=\emptyset$. En utilisant le théorème de Hahn-Banach, il existe un hyperplan fermé $H$ qui sépare $F$ et $F_n$ et comme les ensembles sont compacts on peut obtenir une séparation stricte: $F\cap H=\emptyset$ et~$F_n\cap H=\emptyset$.

Nous pouvons appliquer l'hypothèse de récurrence à la famille $(F_i\cap H)_{i<n}$ car $\bigcup_{i<n} (F_i\cap H)=(\bigcup_{i=1}^n F_i)\cap H$ est convexe. Comme $\bigcap_{i<n} (F_i\cap H)=F\cap H=\emptyset$, d'après l'hypothèse de récurrence, il~existe un indice $j<n$ tel que $\bigcap_{i<n, i\neq j} (F_i\cap H)=\emptyset$. Mais l'ensemble $G=\bigcap_{i<n, i\neq j} F_i$ contient $F$ et $G\cap F_n\neq \emptyset$ par hypothèse, donc $G$ doit rencontrer $H$ d'où la contradiction.
\end{proof}

Nous pouvons alors démontrer le théorème de Sion pour des polytopes.

\begin{lemma}\label{lemme_Sion}
Supposons que les hypothèses du théorème \ref{thm_Sion} sont satisfaites et qu'il existe deux ensembles finis $S_0$ et $T_0$ tels que $S$ soit égal à l'enveloppe convexe $\co S_0$ de $S_0$ et  $T$ soit égal à $\co T_0$. Alors:
$$\sup_{s\in S}\inf_{t\in T_0}g(s,t)\geq \inf_{t\in T}\sup_{s\in S_0}g (s,t).$$
\end{lemma}

\begin{proof} Remarquons que $S$ et $T$ peuvent s'identifier à des convexes compacts de dimension finie et donc être munis de l'unique topologie d'evtlcs correspondante. Celle-ci étant nécessairement plus fine que la topologie de départ, les hypothèses du théorème restent satisfaites. Supposons par l'absurde qu'il existe un réel $c$ tel que:
$$\sup_{s\in S}\inf_{t\in T_0}g(s,t)<c<\inf_{t\in T}\sup_{s\in S_0}g (s,t).$$
Ceci revient à:
\begin{align*}
\forall s\in \co S_0,\; \exists t\in T_0, \quad g(s,t)&<c,\\
\forall t\in \co T_0,\; \exists s\in S_0,\quad g(s,t)&>c.
\end{align*}
Supposons de plus que $(S_0,T_0)$ soit minimal (pour l'inclusion) parmi les paires d'ensembles non vides vérifiant ces conditions. Posons alors pour tout $s\in S_0$, $T_s=\left\{t\in T\mid  g(s,t)\leq c\right\}$, cet ensemble est convexe fermé. Les conditions ci-dessus impliquent $\bigcap_{s\in S_0} T_s=\emptyset$ et comme on a pris $(S_0,T_0)$ minimal, $\bigcap_{s\in S_0, s\neq s_0}T_s\neq \emptyset$ pour tout $s_0\in S_0$. Le lemme \ref{helly} implique que $\bigcup_{s\in S_0}T_s\neq T$ et donc il existe $t^*\in T$ tel que $\forall s\in S_0$, $g(s,t^*)>c$. Enfin, par convexité de l'ensemble $\left\{s\in S\mid  g(s,t^*)\geq \min_{s'\in S_0}g(s',t^*)\right\}$, on a $g(s,t^*)>c$ pour tout \hbox{$s\in S$}. Échangeant les rôles des deux joueurs nous obtenons l'existence de $s^*$ telle que $g(s^*,t)<c$ pour tout $t\in T$ et donc $g(s^*,t^*)<c<g(s^*,t^*)$, d'où la contradiction.
\end{proof}

\begin{proof}[\proofname\ du théorème \ref{thm_Sion}]
Supposons par l'absurde que l'on ait:
$$\sup_{s\in S}\inf_{t\in T_0}g(s,t)<\inf_{t\in T}\sup_{s\in S_0}g (s,t).$$
On peut alors trouver $c\in \reals$ tels que:
\begin{align*}
\forall s\in S,\; \exists t\in T,\quad g(s,t)&<c,\\
\forall t\in T,\; \exists s\in S,\quad g(s,t)&>c.
\end{align*}
Supposons $S$ compact, les ensembles $S_t\!=\!\{s\!\in\! S\!\mid\!  g(s,t)\!<\!c\}$~forment un recouvrement ouvert de $S$. Soit $(S_t)_ {t\in T_0}$ un sous-re\-cou\-vre\-ment fini, on a:
\begin{align*}
\forall s\in S,\; \exists t\in T_0,\quad g(s,t)&<c,\\
\forall t\in \co T_0,\; \exists s\in S,\quad g(s,t)&>c.
\end{align*}
Remplaçant $T$ par $\co T_0$ (qui est compact), nous pouvons échanger les rôles de $S$ et $T$ et obtenir un ensemble fini $S_0\subset S$ tel que:
\begin{align*}
\forall s\in \co S_0,\; \exists t\in T_0,\quad g(s,t)&<c,\\
\forall t\in \co T_0,\; \exists s\in S_0,\quad g(s,t)&>c,
\end{align*}
et on conclut grâce au lemme \ref{lemme_Sion}.

Les points (b) et (c) du théorème \ref{thm_Sion} s'obtiennent directement par la semi-continuité supérieure et la quasi-concavité de $s\mto g(s,t)$ (et les conditions duales pour $t\mto g(s,t)$).
\end{proof}

\subsection{Continuité et dérivabilité de la valeur}
Fixons deux espaces compacts $S$ et $T$. Soit $E$ l'espace vectoriel des applications $g:S\times T\to \reals$ bornées. On pose $\left\|g\right\|=\sup_{(s,t)\in S\times T}\left|g(s,t)\right|$, pour $g \in E$.

\skpt
\begin{proposition}
\begin{enumerate}
\item
Pour toutes applications $f,g\in E$:
\[
\left|\underline{v}(g)-\underline{v}(f)\right|\leq \left\|g-f\right\|\quad\text{et}\quad\left|\overline{v}(g)-\overline{v}(f)\right|\leq \left\|g-f\right\|.
\]

\item
Soit $(f_\alpha)_\alpha$ une suite généralisée de $E$ telle que $\left\|f_\alpha-f\right\|\to 0$ avec $f\in E$ telle que pour tout $t$, l'application partielle $f(\cdot,t)$ est scs. Soit $(s_\alpha)_\alpha $ une suite généralisée de $S$ telle que $s_\alpha$ est une stratégie $\varepsilon_\alpha$-optimale du joueur~1 pour $f_\alpha$ avec $\vare_\alpha>0$, $\vare_\alpha\to 0$. Alors, tout point d'accumulation de $(s_\alpha)_\alpha$ est une stratégie optimale du joueur~1 pour $f$.
\end{enumerate}
\end{proposition}

\skpt
\begin{proof}
\begin{enumerate}
\item
Il est immédiat que pour toutes constantes $a>0$ et $b\in \reals $, si l'on pose $af+b$ l'application $(s,t)\mto af(s,t)+b$, on a: $\underline{v}(af+b)=a\underline{v}(f)+b$. De plus si pour tout $(s,t)$, $f(s,t)\leq g(s,t)$, alors $\underline{v}(f)\le \underline{v}(g)$. Comme $f(s,t)\leq g(s,t)+\left\|g-f\right\|$, on a $\underline{v}(f)\le \underline{v}(g)+\left\|g-f\right\|$, d'où le résultat.

\item
Supposons que pour tout $t\in T$, $f_\alpha(s_\alpha, t)\geq \underline{v}(f_\alpha)-\vare_\alpha$. D'après le point précédent $ \underline{v}(f_\alpha)\to \underline{v}(f)$ et donc pour tout $t\in T$, $\underline{\mathrm{lim}} f_\alpha(s_\alpha,t)\ge \underline{v}(f)$. Comme $f_\alpha$ converge uniformément vers $f$, $\underline{\mathrm{lim}} f_\alpha(s_\alpha,t)=\underline{\mathrm {lim}} f(s_\alpha,t)$. Soit $s$ un point d'accumulation de $(s_\alpha)_\alpha$, puisque $f(\cdot, t)$ est scs, $f(s,t)\ge\underline{\mathrm{lim}} f(s_\alpha,t)\ge \underline{v}(f)$.\qedhere
\end{enumerate}
\end{proof}

En utilisant ce résultat, nous obtenons une formule pour la dérivée directionnelle de la fonction valeur (Mills, 1956). Soient $f,g$ dans $E$, toutes deux scs en $s$ et sci en $t$. On suppose que pour tout $\vare\ge0$, $v(f+\vare g)$ existe. Soit $S(f)=O^1(f)\times O^2(f)$ l'ensemble des points selles de $f$, on pose $v_f(g)=v(g\vert_{S(f)})$ (lorsque cette valeur existe).

\begin{proposition}
Avec ces hypothèses, $v_f(g)$ existe et on a:
$$\lim_{\vare\to 0^+} \frac{v(f+\vare g)- v(f)}{\vare}=v_f(g)$$
\end{proposition}

\begin{proof} Soit $t$ une stratégie optimale du joueur~2 pour $f$ ($t\in\nobreak O^2(f)$), et $s_\vare$ une stratégie optimale du joueur~1 pour $f+\vare g$. Il~vient:
\begin{align*}
v(f+\vare g)&\leq f(s_\vare,t)+\vare g(s_\vare,t)\\
&\leq v(f)+\vare g(s_\vare,t)
\end{align*}
D'où $\sfrac{v(f+\vare g)- v(f)}{\vare}\leq g(s_\vare,t)$, et comme ceci est vrai pour toute stratégie optimale du joueur~2 pour $f$, on obtient
\[
\frac{v(f+\vare g)- v(f)}{\vare}\leq \inf_{t\in O^2(f)}g(s_\vare,t).
\]
Comme $g(\cdot,t)$ est scs, $\inf_{t\in O^2(f)}g(\cdot,t)$ l'est aussi. D'où, pour tout point d'accumulation $s$ de $(s_\vare)_{\vare\to 0}$, $\overline{\mathrm{lim}}_{\vare\to 0^+}\inf_{t\in O^2(f)}g(s_\vare,t)\le \inf_{t\in O^2(f)}g(s,t)$, et $s\in O^1(f)$. Donc,
$$\overline{\mathrm{lim}}_{\vare\to 0^+}\frac{v(f+\vare g)- v(f)}{\vare}\leq \sup_{s\in O^1(f)}\inf_{t\in O^2(f)}g(s,t)$$

On obtient l'égalité en échangeant les rôles des deux joueurs.
\end{proof}

\section{Jeux à somme non nulle}

La notion centrale de solution pour les jeux sous forme normale est l'équilibre de Nash (1950), qui généralise la notion de point selle. Soit $G=(N, (A^i)_{i\in N}, (g^i)_{i\in N})$ un jeu.

\Subsection{Équilibres de Nash}

\begin{definition}
Un équilibre de Nash du jeu $G$ est un profil de stratégies $a=(a^i)_ {i\in N}$ tel que:
$$\forall i\in N,\; \forall b^i\in A^i,\quad g^i(b^i,a^{-i})\leq g^i(a)$$
\end{definition}

Cette définition peut se reformuler de différentes façons. Par exemple, étant donné un profil de stratégies $a$, on dit que le joueur~$i$ a une \emph{déviation profitable} par rapport à $a$, s'il existe $b^i$ telle que $g^i(b^i,a^{-i})>g^i(a)$. Un équilibre de Nash est un profil de stratégies pour lequel il n'existe pas de déviation profitable. C'est donc un point tel que, si tous les joueurs savent qu'on va jouer $a$, alors chacun a effectivement intérêt à le jouer. On peut remarquer que pour les jeux à somme nulle, équilibres de Nash et points selles coïncident.

Une autre reformulation va suggérer une méthode de calcul et de démonstration d'existence.

\skpt
\begin{definition}
\begin{itemize}
\item
Pour chaque joueur $i$ et profil d'action de ses adversaires $a^{-i}$, on dit que $a^i$ est \emph{meilleure réponse} contre $a^{-i}$ si:
\[
\forall b^i\in A^i,\quad g^i(b^i,a^{-i})\leq g^i(a^i,a^{-i}).
\]

\item
On appelle \emph{correspondance de meilleure réponse du joueur $i $}, l'application $\MR^i$ de $A^{-i}$ dans les parties de $A^{i}$, qui à $a^{-i}$ associe l'ensemble des meilleures réponses du joueur $i$.

\item
On appelle \emph{correspondance de meilleure réponse} du jeu $G$, l'application $\MR:A\to 2^A$ définie par $\MR(a)=\prod_{i\in N} \MR^i(a^{-i})$.
\end{itemize}
\end{definition}

On voit alors que $a$ est un équilibre de Nash de $G$ si et seulement si $a\in \MR(a)$. On dit que $a$ est un \emph{point fixe} de la correspondance de meilleure réponse. La procédure de calcul des équilibres est donc la suivante: tracer le graphe de la correspondance de meilleure réponse de chaque joueur, et chercher l'intersection des graphes.

\subsubsection*{Calcul des équilibres de Nash dans le jeu de Cournot}
On prend $G=(A^1,A^2, g^1, g^2)$ avec $A^1=A^2=\reals_+$ et
\[
g^i(a^1,a^2)=a^i(\alpha-\beta(a^1+a^2))^+ -\gamma a^i\quad (\alpha,\beta,\gamma>0,\; \alpha>\gamma).
\]

On a:
\[
\MR^1(a^2)=\begin{cases}
\left\{\dfrac{\alpha-\gamma}{2\beta}-\dfrac{a^2}{2}\right\}&\text{si }a^2\le \dfrac{\alpha-\gamma}{\beta},\\
\left\{0\right\}&\text{sinon}.
\end{cases} 
\]
La correspondance de meilleure réponse du joueur~2 est identique.

On voit alors facilement que ($a^1\in \MR^1(a^2)$ et $a^2\in \MR^2(a^1) $) si et seulement si, $a^1=a^2=\psfrac{\alpha-\gamma}{3\beta}$.

\Subsubsection*{Lien avec l'élimination itérée des stratégies strictement dominées}
Il découle des définitions qu'une stratégie strictement dominée n'est jamais meilleure réponse et donc n'est jamais utilisée dans un équilibre de Nash. Il s'ensuit que l'ensemble des équilibres de Nash est inchangé lors de l'élimination des stratégies strictement dominées. Pour trouver les équilibres d'un jeu on peut donc effectuer l'EISSD au préalable.

\subsection{Un théorème d'existence} La dernière reformulation suggère également une méthode de preuve d'existence d'équilibre: étant donné une correspondance de $A$ dans $A$, c'est-à-dire une application~$F$ de $A$ dans ses parties, on cherche un point fixe, c'est-à-dire un point~$a$ tel que $a\in F(a)$. Lorsque $F $ est \emph{univoque}: il existe une application $f:A\to A$ telle que, pour tout $a$, $F(a)=\left\{f(a)\right\}$, ceci revient à trouver un point fixe de l'application $f$. Les deux théorèmes de point fixes les plus utilisés sont le théorème de Brouwer et ses généralisations par Kakutani (1941) et Glicksberg (1952).

\begin{theorem}[Théorème de Brouwer]
Soit $C$ un convexe compact non vide de $\reals^k$ et $f:C\to C$ continue, alors $f$ admet un point fixe: il existe $c\in C$ tel que $c=f(c)$.
\end{theorem}

Le théorème de Brouwer a été généralisé aux correspondances par Kakutani (1941) dans les espaces vectoriels de dimension finie et par Glicksberg (1952) dans les espaces vectoriels topologiques.

\begin{theorem}[Kakutani-Glicksberg] \label{thm_kak}
Soit $C$ un convexe compact non vide d'un evtlcs et $F$ une correspondance de $C$ dans $C$ telle que
\begin{enumeratei}
\item
pour tout $c\in C$, $F(c)$ est un convexe compact non vide,
\item
le graphe de $F$, à savoir $\left\{(c,d)\in C\times C\mid  c\in F(d)\right\}$, est fermé.
\end{enumeratei}
Alors, il existe $c\in C$ tel que $c\in F(c)$.
\end{theorem}

On peut aussi formuler ce théorème de la façon suivante: Soit~$X$ un sous-ensemble fermé de $C\times C$ tel que pour tout $c\in C$, la section de~$X$ au-dessus de $c$ (\ie $\left\{d\in C\mid  (c,d)\in X\right\}$) est un convexe compact non vide. Alors, $X$ coupe la diagonale de $C\times C$.

Donnons une démonstration de ce résultat en dimension finie.

\begin{proof} On suppose que $C$ est un convexe compact non vide de $\reals^k$. Pour tout entier $n$, il existe une famille finie de points $(x^n_i)_i$ de $C$ telle que $C\subset\bigcup_i B(x_i^n,\sfrac1n)$, ou $B(x_i^n,\sfrac1n)$ désigne la boule ouverte de centre $x^n_i$ et de rayon $\sfrac1n$. Notons $B^c(x_i^n,\sfrac1n)$ le complémentaire dans $\reals^k$ de cette boule et fixons, pour chaque $x^n_i$ un élément $y^n_i\in F(x^n_i)$. Pour tout $x$ dans $C$ on pose:
$$f^n(x)=\sum_i\frac{d(x,B^c(x_i^n,\sfrac1n))}{\sum_jd(x,B^c(x_j^n, \sfrac1n))}\,y_i^n$$
Pour tout $x$ dans $C$, il existe $i$ tel que $x\in B(x_i^n,\sfrac1n)$, d'où $\sum_jd(x,B^c(x_j^n,\sfrac1n))>0$. L'application $f^n$ est donc bien définie et continue sur $C$, et $f^n(x)\in C$ par convexité. D'après le théorème de Brouwer, il existe $x^n\in C$ tel que $x^n=f^n(x^n)$. Comme $d(x,B^c(x_i^n,\sfrac1n))>0$ si et seulement si $d(x,x^n_i)<\sfrac1n$, on a:
$$x^n=\sum_{i\,\mid\, d(x^n,x^n_i)<\sfrac1n} \frac{d(x^n,B^c(x_i^n,\sfrac1n))}{\sum_jd(x^n,B^c (x_j^n,\sfrac1n))}\,y_i^n$$
Appliquons maintenant le théorème de Carathéodory: toute combinaison convexe des $(y_i^n)_i$ peut s'écrire comme combinaison d'au plus $k+1 $ points parmi cette famille. Cela fournit la conclusion suivante, pour tout $n $, il existe:

\begin{itemize}
\item
$x^n, x^n_1,\ldots, x^n_{k+1}$ éléments de $C$, tels que $d(x^n,x^n_i)<\sfrac1n$ ($\forall i$);
\item
$y_1^n,\ldots, y_{k+1}^n$ avec $y^n_i\in F(x^n_i)$;
\item
$\lambda_1^n,\ldots, \lambda_{k+1}^n$, $\lambda^n_i\ge 0$, $\sum_i\lambda_i^n=1$;
\item
$x^n=\sum_{i=1}^{k+1} \lambda_i^n y_i^n$.
\end{itemize}

Par compacité, quitte à extraire une sous-suite, supposons que $x^n \to x$, $x^n_i\to x_i$, $y^n_i\to y_i$, $\lambda_i^n\to\lambda_i$. Alors, $x=x_i$ pour tout $i$, $y_i\in F(x)$ car le graphe de $F$ est fermé et $x=\sum_{i=1}^{k+1}\lambda_i y_i$ appartient à $F(x)$ qui est convexe.
\end{proof}

On déduit de ce résultat un théorème d'existence d'équilibres (Glicksberg, 1952, généralisant Nash, 1950).

\skpt
\begin{theorem}[Théorème de Glicksberg-Nash]
Soit $G=(N, (A^i)_{i\in N}, (g^i)_{i\in N})$ un jeu tel que, pour tout $i\!\in\! N$, $A^i$~est un convexe compact non vide dans un evtlcs, $g^i:A \to \reals$ est \hbox{continue} et pour tout $a^{-i}\in A^{-i}$, l'application partielle $a^i\mto g^i(a^i,a^{-i})$ est quasi-concave.

Alors, l'ensemble des équilibres de Nash de $G$ est un fermé non vide.
\end{theorem}

\begin{proof} On vérifie simplement que le théorème \ref{thm_kak} s'applique. Les hypothèses de compacité, de continuité et quasi-concavité des fonctions de paiements assurent que $\MR^i(a^{-i})$ est convexe fermé non vide ($\forall i$, $\forall a^{-i}$), $\MR(a)$ est donc bien convexe compact non vide ($\forall a$). Le graphe de la correspondance $\MR$ s'écrit:
$$\left\{(a,b)\in A\times A\mid  \forall i\in N,\, \forall c^i\in A^i,\, g^i(a^i,b^{-i})\ge g^i(c^i,b^{-i})\right\}.$$
Les fonctions de paiement étant continues,
$$\left\{(a,b)\in A\times A\mid  g^i(a^i,b^{-i})\ge g^i(c^i,b^{-i})\right\}$$
est fermé ($\forall i\in N$, $\forall c^i\in A^i$). Le graphe de la correspondance $\MR$ est donc une intersection de fermés. L'ensemble des équilibres de Nash est donc non vide et il est clairement fermé.
\end{proof}

\section{Jeux finis et stratégies mixtes}\label{jeux_finis} On dit qu'un jeu $G=(N, (A^i)_{i\in N}, (g^i)_{i\in N})$ est fini lorsque les ensembles de stratégies sont tous des ensembles finis. Le jeu \emph{matching pennies} (ci-dessus) n'admet pas de point selle ni de valeur. Toutefois, le but du joueur~1 étant de deviner l'action du joueur~2, et le but du joueur~2 étant de l'en empêcher, la meilleure \og stratégie\fg du joueur~2 est de choisir son action aléatoirement et de façon équiprobable pour être le plus difficilement prédictible. On est donc naturellement conduit à élargir le modèle et à autoriser les joueurs à choisir leur action au hasard et avec les probabilités de leur choix, on parle de stratégies mixtes. Outre l'interprétation directe selon laquelle les joueurs utilisent un dispositif aléatoire pour choisir leur action, une stratégie mixte d'un joueur peut se voir comme la croyance qu'ont ses adversaires sur son action: le joueur lui, sait parfaitement quelle action il va jouer, les probabilités sont l'expression de l'incertitude des adversaires. On peut également donner une interprétation statistique en voyant les joueurs non pas comme des agents individuels mais comme des populations d'individus. La probabilité d'une stratégie s'interprète alors comme la proportion d'individus jouant cette stratégie. Cette interprétation est particulièrement fructueuse en biologie évolutionnaire où une stratégie représente un caractère génétique, et une stratégie mixte, la distribution statistique des gènes dans la population.

Soit $E$ un ensemble fini. On note $\Delta(E)$ l'ensemble des distributions de probabilités sur $E$, que l'on identifiera avec des vecteurs de $\reals^E$ à coordonnées positives de somme 1.
$$\textstyle
\Delta(E)=\big\{p\in \reals^E\mid  \forall e\in E,\, p(e)\ge0,\, \sum_{e\in E} p(e)=1\big\}.$$

Cet ensemble est l'enveloppe convexe de la base canonique de $\reals^E$, c'est donc un convexe compact. L'ensemble $E$ s'injecte naturellement dans $\Delta(E)$ en identifiant $e\in E$ à la masse de Dirac $\delta_e\in \Delta(E)$ qui vérifie $\delta_e(e')=1$ si $e'=e$ et 0 sinon.

\begin{definition} Soit $G=(N, (A^i)_{i\in N}, (g^i)_{i\in N})$ un jeu fini.

\begin{itemize}
\item
On appelle \emph{stratégie mixte} du joueur $i$, une probabilité $\sigma^i\in \Delta(A^i)$ et \emph{stratégie pure} une action $a^i\in A^i$. L'ensemble des stratégies mixtes du joueur $i$ est $\Delta(A^i)$.
\item
Étant donné un profil de stratégies mixtes $\sigma=(\sigma^i)_{i \in N}\in\prod_{i\in N}\Delta(A^i)$, on appelle \emph{paiement espéré} du joueur $i$ la quantité:
$$g^i(\sigma)=\sum_{a\in A}\big(\textstyle\prod_{i\in N}\sigma^i(a^i)\big)g^i(a)$$
Ceci définit une extension de l'application $g^i$ de $\prod_{i\in N}A^i$ à l'ensemble $\prod_{i\in N}\Delta(A^i)$ que l'on note encore $g^i$: on appelle cette application \emph{extension multilinéaire} ou \emph{extension mixte} de $g^i$.
\item
On appelle \emph{extension mixte} du jeu $G$ le jeu
\[
(N, (\Delta(A^i))_{i\in N}, (g^i)_{i\in N}).
\]
\item
Un équilibre de Nash de l'extension mixte de $G$ s'appellera équilibre de $G$ en stratégies mixtes.
\end{itemize}
\end{definition}

Les jeux finis joués en stratégies mixtes sont les premiers jeux pour lesquels ont été démontrés des résultats d'existence, Von Neumann (1928) pour les jeux à somme nulle et Nash (1950) pour les jeux à somme non nulle.

\begin{theorem}[Théorème du MinMax, Von Neumann1928]
Tout jeu fini $(A^1,A^2,g)$ admet un point selle en stratégies mixtes. En particulier le jeu admet une valeur $v$ et les deux joueurs ont des stratégies optimales. De plus,
$$v=\max_{\sigma^1\in\Delta(A^1)}\min_{a^2\in A^2}g(\sigma^1,a^2)=\min_{\sigma^2\in\Delta(A^2)}\max_{a^1\in A^1}g(a^1,\sigma^2)$$
\end{theorem}

\begin{proof} L'existence de valeur et de stratégies optimales pour les deux joueurs découle directement du théorème de Sion. Les ensembles de stratégies mixtes sont convexes et compacts et les extensions mixtes des fonctions de paiement sont multi-linéaires, donc continues et possèdent les propriétés requises de quasi-concavité.

De plus, si l'on fixe une stratégie mixte $\sigma^1$ du joueur~1, $g(\sigma^1,\sigma^2)$ est une application linéaire sur le polytope $\Delta(A^2)$. Elle atteint donc son minimum en un point extrême, c'est-à-dire en une stratégie pure.
\end{proof}

\skpt
\begin{theorem}[Théorème de Nash, 1950]\label{thmnash}
Tout jeu fini $G=(N,(A^i)_{i\in N},(g^i)_{i\in N})$ admet un équilibre de Nash en stratégies mixtes.
\end{theorem}

\begin{proof} De la même façon, les ensembles de stratégies mixtes sont convexes et compacts et les extensions mixtes des fonctions de paiement sont multi-linéaires, donc continues et possèdent les propriétés requises de quasi-concavité.
\end{proof}

\subsubsection*{Extension: ensembles infinis de stratégies}
La notion de stratégie mixte peut s'étendre à des espaces mesurables d'actions, en posant des conditions de mesurabilité et intégrabilité sur les fonctions de paiements. Un cadre simple à traiter est le cas des espaces métriques compacts. Si $E$ est un espace métrique compact, on le munit de la tribu borélienne et on pose $\Delta(E)$ l'ensemble des mesures probabilités boréliennes sur $E$. Muni de la topologie faible-$*$ (la plus petite topologie rendant continues les applications $\mu\mto \int_E fd\mu$ avec $f:E\to \reals$ continue), $\Delta(E)$ est métrisable et compact.

On dit qu'un jeu $G=(N,(A^i)_{i\in N},(g^i)_{i\in N})$ est \emph{compact} si chaque~$A^i$ est métrique compact et chaque $g^i$ est continue. L'extension mixte de~$g^i$ est définie sur $\prod_{i\in N}\Delta(A^i)$ par:
$$g^i(\sigma^1,\ldots,\sigma^n)=\int g^i d\sigma^1\cdots d\sigma^n$$
On définit ainsi, comme dans le cas fini, l'extension mixte du jeu $G $. On obtient alors un résultat d'existence en stratégies mixtes.

\begin{theorem}\label{thmnash2} Tout jeu compact $G=(N,(A^i)_{i\in N},(g^i)_{i\in N})$ admet un équilibre de Nash en stratégies mixtes.
\end{theorem}

\begin{proof} Comme dans le cas fini, les espaces de stratégies mixtes sont des convexes compacts, les fonctions de paiements sont continues et multi-linéaires, l'aspect quasi-concave est donc garanti.
\end{proof}

Revenons aux jeux finis pour donner une caractérisation des équilibres de Nash en stratégies mixtes.

\begin{theorem} Soit $G=(N,(A^i)_{i\in N},(g^i)_{i\in N})$ un jeu fini. Un profil de stratégies mixtes $\sigma=(\sigma^i)_{i\in N}$ est un équilibre de Nash en stratégies mixtes de $G$ si et seulement si:
$$\forall i\in N,\; \forall a^i\in A^i,\quad (\sigma^i(a^i)>0\Rightarrow a^i\in \MR^i(\sigma^{- i}))$$
\end{theorem}

Autrement dit, toutes les stratégies pures jouées avec une probabilité non nulle sont des meilleures réponses au profil de stratégies des autres joueurs, et en particulier elles donnent le même paiement. Ce résultat peut permettre un calcul assez simple des équilibres de Nash. Dans le jeu de coordination:
\[
\begin{array}{rc}
&A\hspace*{5mm}B
\\
\begin{array}{r}
A\\B
\end{array}
&\arraycolsep5pt\begin{array}{|c|c|}
\hline
1,1 & 0,0
\\
\hline 
0,0 & 1,1\\
\hline
\end{array}
\end{array}
\]
les profils $(A,A)$ et $(B,B)$ sont deux équilibres de Nash en stratégies pures. Pour déterminer les équilibres en stratégies mixtes, remarquons d'abord qu'il n'y a pas d'équilibre dans lequel un joueur joue une stratégie pure et l'autre joue une stratégie strictement mixte: les deux actions sont jouées avec probabilité strictement positive. En effet, dès qu'un joueur joue une stratégie pure, l'autre a une unique meilleure réponse qui est pure. On cherche donc les équilibres dans lesquels les deux joueurs jouent une stratégie strictement mixte. Chaque joueur doit alors avoir le même paiement espéré en jouant $A$ ou $B$. Les équations d'égalisations des paiement donnent que chaque joueur joue la stratégie mixte $(\frac12,\frac12)$. Ce jeu a donc exactement trois équilibres.

\begin{proof} Soit $\sigma=(\sigma^i)_{i\in N}$ un équilibre de $G$ en stratégies mixtes et $i$ un joueur. Par multi-linéarité:
$$g^i(\sigma^i,\sigma^{-i})=\sum_{a^i\in A^i}\sigma^i(a^i)\,g^i(a^i,\sigma^{-i})$$
Comme $\sigma$ est un équilibre, pour toute action $a^i$,
$$g^i(a^i,\sigma^{-i})\leq g^i(\sigma^i,\sigma^{-i})=\max_{\tau^i\in\Delta(A^i)}g^i(\tau^i, \sigma^{-i})$$
D'où, $g^i(a^i,\sigma^{-i})= g^i(\sigma^i,\sigma^{-i})$ dès que $\sigma^i(a^i)>0$. Réciproquement, si pour tout $i\in N$ et tout $a^i$ tel que $\sigma^i(a^i)>0$, on a $g^i(a^i,\sigma^{-i})=\max_{\tau^i\in\Delta(A^i)}g^i(\tau^i,\sigma^{- i})$, alors
$$g^i(\sigma^i,\sigma^{-i})=\sum_{a^i\in A^i}\sigma^i(a^i)g^i(a^i,\sigma^{-i})=\max_{\tau^i\in\Delta(A^i)}g^i (\tau^i,\sigma^{-i})$$
et donc $\sigma$ est un équilibre.
\end{proof}

\section{Jeux à information parfaite} Nous décrivons ici une classe de jeux contenant les jeux de plateaux traditionnels (échecs, dames, jeu de Go): ce sont les \emph{jeux à information parfaite} dans lesquels les joueurs jouent séquentiellement (et non pas simultanément) en ayant pleinement connaissance de l'état de la partie au moment de jouer. Ces interactions sont modélisées par des arbres de décision.

\begin{definition}

On appelle \emph{arbre} un ensemble de n\oe uds ou d'histoires~$H$ muni de:
\begin{itemize}
\item
une racine ou histoire initiale $h_0\in H$,
\item
une relation binaire sur $H$, $h\prec h'$ ($h$ est le prédécesseur de $h'$) telle que:
\begin{enumeratei}
\item
tout $h\in H\setminus\left\{h_0\right\}$ a un unique prédécesseur $\pi(h)$ et il existe un entier $k\geq 1$ tel que $\pi^k(h)=h_0$,
\item
$h_0$ n'a pas de prédécesseur.
\end{enumeratei}
\end{itemize}
\end{definition}

Un arbre est un graphe connexe tel que pour toute paire d'histoires $h,h'$, il existe un unique chemin de $h$ à $h'$.

Partant d'un arbre, on définit un jeu en spécifiant quel joueur joue en chaque n\oe ud, ce joueur choisit alors une branche issue de ce n\oe ud. Posons $A(h)=\left\{h':\ h\prec h'\right\}$ l'ensemble des successeurs de $h$. On dit que $h$ est une histoire terminale si $A(h)=\emptyset$ et on pose $H_T$ l'ensemble des histoires terminales.

\begin{definition}
Un \emph{jeu à information parfaite} est donné par un ensemble de joueurs $N$, un arbre $(H,h_0,\prec)$, une application
\[
\iota:H\setminus H_T \to N
\]
et pour chaque joueur $i\in N$, une application $u^i:H_T\to \reals$.
\end{definition}

Le déroulement du jeu est le suivant. Le jeu commence en $h_0$. Au n\oe ud $h\in H\setminus H_T$, le joueur $\iota(h)$ choisit un successeur $h'$ de $h$ dans l'ensemble $A(h)$, le jeu passe au n\oe ud $h'$. Au n\oe ud $h\in H_T$, le jeu est terminé et chaque joueur $i$ reçoit le paiement $u^i (h)$.

Une stratégie du joueur $i$ dans un tel jeu est le choix d'une action pour chaque n\oe ud qui lui est attribué (le joueur $i$ écrit un programme qui prévoit quoi jouer dans chaque cas possible). L'ensemble des stratégies du joueur $i$ est donc: $S^i=\prod_{\left\{h:\ \iota(h)=i\right\}}A(h) $. Un profil de stratégies $s=(s^i)_{i\in N}$ induit une unique suite de n\oe uds $(h_0,h_1,\ldots, h_t,\ldots)$: si $i=\iota(h_t)$ alors, $h_{t+1}=s^i(h_t)$. Si il existe un rang $t$ tel que $h_t\in H_T$, la suite s'arrête et on pose $h_T(s)$ le n\oe ud terminal ainsi atteint. Lorsque l'arbre a un nombre fini de n\oe uds, on atteint toujours un n\oe ud terminal.

\begin{definition} Soit $(N,(H,h_0,\prec), \iota, (u^i)_{i\in N})$ un jeu à information parfaite fini ($N$ et $H$ sont des ensembles finis), le jeu sous forme stratégique associé est le jeu $G=(N,(S^i)_{i\in N},(g^i)_{i\in N})$ où $g^i(s)=u^i(h_T(s))$.
\end{definition}

On a alors le théorème suivant prouvé par Zermelo (1912) pour le jeu d'échecs et basé sur l'algorithme de Kuhn.

\begin{theorem} Tout jeu à information parfaite fini admet un équilibre de Nash en stratégies pures. En particulier, si le jeu est à somme nulle, le jeu a une valeur et les deux joueurs ont des stratégies optimales.
\end{theorem}

\begin{proof} On procède par récurrence sur le nombre de n\oe uds de l'arbre. Si l'arbre a un seul n\oe ud, l'assertion est évidente. Supposons qu'elle soit vraie pour tout jeu à information parfaite dont l'arbre a strictement moins que $K$ n\oe uds, et soit un jeu à information parfaite dont l'arbre a $K$ n\oe uds. Pour chaque successeur $h$ de la racine $h_0$ on considère le sous-arbre issu de $h$. Ceci définit un \emph{sous-jeu} à information parfaite qui a strictement moins que $K$ n\oe uds et donc, par hypothèse de récurrence possède un équilibre en stratégies pures.

Fixons pour chaque $h\in A(h_0)$, un équilibre $s_h$ du sous-jeu issu de~$h$. Soit alors $i=\iota(h_0)$. On a un équilibre de Nash du jeu en définissant~$s$ tel que: au n\oe ud $h_0$, $i$ choisit $h$ pour lequel $g^i(s_h)$ est maximal, et en tout autre n\oe ud, on suit les stratégies $s_h$ si $h$ a été choisit par~$i$ en $h_0$.
\end{proof}

Cette démonstration décrit également un algorithme de résolution: on résout le jeu aux n\oe uds précédant les n\oe uds terminaux, et on remonte vers la racine (procédure de \emph{backward induction} ou récurrence amont).

Ce théorème montre en particulier que le jeu d'échecs est parfaitement résoluble: soit les Blancs ont une stratégie gagnante, soit les Noirs ont une stratégie gagnante, soit les deux peuvent forcer la partie nulle. Seule la capacité de calcul empêche de décider dans quel cas on se trouve.

\Subsubsection*{Exemple: Le jeu du Mille-Pattes de Rosenthal}
Dans ce jeu, les deux joueurs choisissent alternativement soit  d'arrêter le jeu, auquel cas les paiements sont distribués, soit de passer la main à l'autre joueur. Les paiements sont de plus en plus élevés à mesure que le temps passe.
\unitlength 0,7mm 
\begin{center}
\begin{picture}(100,40)
\put(-5,30){\line(1,0){100}}
\put(-5,30){\line(0,-1){20}}
\put(20,30){\line(0,-1){20}}
\put(45,30){\line(0,-1){20}}
\put(70,30){\line(0,-1){20}}
\put(-12,30){$h_0$}
\put(-5,30){\circle*{2}}
\put(20,30){\circle*{2}}
\put(45,30){\circle*{2}}
\put(70,30){\circle*{2}}
\put(-5,32){$1$}
\put(20,32){$2$}
\put(45,32){$1$}
\put(70,32){$2$}
\put(-4,8){$(2,2)$}
\put(21,8){$(1,10)$}
\put(46,8){$(100,9)$}
\put(71,8){$(99, 1000)$}
\put(97,30){$(1000, 999)$}
\end{picture}
\end{center}

La résolution de ce jeu par l'algorithme de Kuhn donne le paiement d'équilibre $(2,2)$.

\subsubsection*{Exemple: Le Jeu de Gale} Soit un échiquier de taille $n\times m$, $n$ et $m$ étant deux entiers finis supérieurs à 1. Deux joueurs (1 et 2) choisissent alternativement une case sur l'échiquier. Lorsqu'une case $\left(i,j\right) $ est choisie, toutes les cases $ \left(i',j'\right) $ situées au Nord-est, c'est-à-dire telles que $i'\geq i$ et $j'\geq j$, sont éliminées de l'échiquier.

Le joueur~1 commence le jeu et est déclaré perdant le joueur contraint de choisir la case $\left(1,1\right) $.

Alors:
\begin{enumerate}
\item
Le joueur~1 a une stratégie gagnante.

\item
On construit facilement une stratégie gagnante pour le joueur~1 dans le cas $n\times n$, et dans le cas $m\times 2$.

\item
On n'en connaît toujours pas dans le cas $(n,m)$ général.
\end{enumerate}

\begin{proof}[\proofname\ de \textup{(1)}]
On sait que l'un des deux joueurs a une stratégie gagnante. Supposons que ce soit le joueur~2 et remarquons que, quel que soit le premier coup du joueur~1, la case $(n,m)$ est effacée. Soit alors $(i_0,j_0)$ le coup gagnant du joueur~2 qui suit le coup $(n,m)$ du joueur~1. Ce coup gagnant du joueur~2 aurait pu être joué dès le départ par le joueur~1 d'où la contradiction.
\end{proof}


\backmatter
\enddocument

