From 62446ff800447eb1f75340f67f44e7cbf92e7a91 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sun, 20 Feb 2022 20:31:14 +0100
Subject: Rework the part about zero-sum games.

---
 notes-mitro206.tex | 376 +++++++++++++++++++++++++++++++----------------------
 1 file changed, 218 insertions(+), 158 deletions(-)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 237e5c9..7d20177 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1037,12 +1037,12 @@ $\lambda_1,\ldots,\lambda_m$ vérifient $\sum_{i=1}^m \lambda_i = 1$
 forme $\frac{\sum_{i=1}^m \lambda_i x_i}{\sum_{i=1}^m \lambda_i}$ où
 $\lambda_1,\ldots,\lambda_m$ vérifient $\sum_{i=1}^m \lambda_i \neq
 0$ : on parle alors de \defin{barycentre} de $x_1,\ldots,x_m$ affecté
-des coefficients $\lambda_1,\ldots,\lambda_m$).
+des poids $\lambda_1,\ldots,\lambda_m$).
 
 Lorsque $x_1,\ldots,x_m$ sont tels que la combinaison affine est
 déterminée par ses coefficients, autrement dit lorsque l'application
 $(\lambda_1,\ldots,\lambda_m) \mapsto \sum_{i=1}^m \lambda_i x_i$
-définie sur l'ensmble des $(\lambda_1,\ldots,\lambda_m)$ tels que
+définie sur l'ensemble des $(\lambda_1,\ldots,\lambda_m)$ tels que
 $\sum_{i=1}^m \lambda_i = 1$, est injective, on dit que
 $x_1,\ldots,x_m$ sont \index{affinement indépendants
   (points)}\defin{affinement indépendants} (ou affinement libres).  Il
@@ -1084,7 +1084,7 @@ affinement libre et finie\footnote{Une partie affinement libre de
 $u\colon \mathbb{R}^p \to \mathbb{R}^q$ est une fonction qui préserve
 les combinaisons affines (autrement dit, si $\sum_{i=1}^m \lambda_i =
 1$ alors $u\Big(\sum_{i=1}^m \lambda_i x_i\Big) = \sum_{i=1}^m
-\lambda_i u(x_i)$).  Il revient au même de dire que $u$ est la somme
+\lambda_i\, u(x_i)$).  Il revient au même de dire que $u$ est la somme
 d'une constante (dans $\mathbb{R}^q$) et d'une application linéaire
 $\mathbb{R}^p \to \mathbb{R}^q$.
 
@@ -1105,9 +1105,9 @@ sur un sommet de ce dernier ».
 Tout point $s$ de $C$ est combinaison convexe de points de $A$,
 c'est-à-dire $s = \sum_{i=1}^n \lambda_i x_i$ avec $x_i \in A$ et
 $\lambda_i \geq 0$ vérifiant $\sum_{i=1}^n \lambda_i = 1$.  Comme $u$
-est affine, on a alors $u(s) = \sum_{i=1}^n \lambda_i u(x_i)$.  Si
+est affine, on a alors $u(s) = \sum_{i=1}^n \lambda_i\, u(x_i)$.  Si
 $u(a) \leq M$ pour tout $a\in A$, ceci implique $u(s) \leq
-\sum_{i=1}^n \lambda_i M = M$, comme annoncé.
+\sum_{i=1}^n \lambda_i\, M = M$, comme annoncé.
 
 Pour en déduire l'affirmation sur le $\max$, il suffit d'appliquer ce
 qu'on vient de démontrer pour $M = \max\{u(a) : a\in A\}$ (qui existe
@@ -1130,11 +1130,11 @@ aussi cette propriété (i.e., on a $u(x_i) = M$ pour tout $i$).
 
 \begin{proof}
 On vient de voir que $u(x_i) \leq M$ pour tout $i$ implique $u(s) \leq
-M$.  Si on a $u(x_j) < M$ pour un certain $j$, alors on a $\lambda_j
-u(x_j) < \lambda_j M$, donc en sommant avec les autres $\lambda_i
-u(x_i) \leq \lambda_i M$ on trouve $u(s) = \sum_{i=1}^n \lambda_i
-u(x_i) < \sum_{i=1}^n \lambda_i M = M$.  Réciproquement, si $u(x_i) =
-M$ pour tout $i$, il est évident que $u(s) = M$.
+M$.  Si on a $u(x_j) < M$ pour un certain $j$, alors on a $\lambda_j\,
+u(x_j) < \lambda_j\, M$, donc en sommant avec les autres $\lambda_i\,
+u(x_i) \leq \lambda_i M$ on trouve $u(s) = \sum_{i=1}^n \lambda_i\,
+u(x_i) < \sum_{i=1}^n \lambda_i\, M = M$.  Réciproquement, si $u(x_i)
+= M$ pour tout $i$, il est évident que $u(s) = M$.
 \end{proof}
 
 On peut aussi reformuler ce résultat en affirmant que la partie de $C$
@@ -1183,21 +1183,22 @@ l'ensemble des options $b\in B$ pour lesquelles $s(b) > 0$.
 On identifiera un élément $b$ de $B$ à la fonction (stratégie pure)
 $\delta_b \colon B\to\mathbb{R}$ qui prend la valeur $1$ en $b$ et $0$
 ailleurs (distribution de probabilités de Dirac en $b$).  Ceci permet
-d'identifier une stratégie mixte $s\colon B\to\mathbb{R}$ quelconque
-sur $B$ à la combinaison convexe $\sum_{b\in B} s(b)\cdot b$ des
-stratégies pures : i.e., on peut considérer les stratégies mixtes
-comme des combinaison convexes formelles\footnote{Le mot « formel »
-  signifie ici que la combinaison n'a pas d'autre sens que comme
-  l'expression par laquelle elle est définie, par exemple
+de considérer $B$ comme une partie de l'ensemble $S_B$ des stratégies
+mixtes, et d'identifier une stratégie mixte $s\colon B\to\mathbb{R}$
+quelconque sur $B$ à la combinaison convexe $\sum_{b\in B} s(b)\cdot
+b$ des stratégies pures : i.e., on peut considérer les stratégies
+mixtes comme des combinaison convexes formelles\footnote{Le mot
+  « formel » signifie ici que la combinaison n'a pas d'autre sens que
+  comme l'expression par laquelle elle est définie, par exemple
   $\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} +
   \frac{1}{3}\text{Ciseaux}$ est une combinaison convexe formelle de
   $\{\text{Pierre}, \text{Papier}, \text{Ciseaux}\}$ représentant la
   probabilité uniforme sur cet ensemble.} des éléments de $B$.
 
 On passera indifféremment entre ces trois points de vue sur les
-stratégies mixtes : fonctions $s\colon B\to\mathbb{R}$, mesures de
-probabilités sur $B$, ou bien combinaisons convexes formelles
-d'éléments de $B$.
+stratégies mixtes : fonctions $s\colon B\to\mathbb{R}$ (positives de
+somme $1$), mesures de probabilités sur $B$, ou bien combinaisons
+convexes formelles d'éléments de $B$.
 
 En tout état de cause, l'ensemble $S_B$ des stratégies mixtes sur $B$
 sera vu comme la partie de $\mathbb{R}^B$ définie par l'intersection
@@ -1206,7 +1207,8 @@ la somme des coordonnées égale à $1$ : il s'agit d'un \emph{convexe
   fermé}, qui est l'enveloppe convexe des points de $B$ identifiés
 ainsi qu'on vient de le dire aux $\delta_b =
 (0,\ldots,0,1,0,\ldots,0)$, c'est-à-dire que $S_B$ est le
-\defin{simplexe} d'ensemble de sommets $B$.
+\defin{simplexe} d'ensemble de sommets $B$ (identifié à l'ensemble
+des $\delta_b$).
 
 \begin{defn}\label{definition-mixed-strategy-game}
 Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une
@@ -1253,14 +1255,15 @@ aléatoires indépendantes).  Les distributions de probabilités $s$
 sur $A$ définies par la formule ($*$) sont précisément celles dont
 composantes sont indépendantes, et qui sont alors complètement
 déterminées par leurs \emph{distributions
-  marginales}\footnote{\label{footnote-marginals}La $i$-ième marginale
-  d'une variable aléatoire sur $A_1\times \cdots \times A_N$ est
-  simplement sa $i$-ième composante (= projection sur $A_i$).  La
-  $i$-ième distribution marginale de la distribution de probabilités
-  $s \colon A \to \mathbb{R}$ est donc la distribution de probabilités
-  $s_i \colon A_i \to \mathbb{R}$ qui à $b\in A_i$ associe la somme
-  des $s(a_1,\ldots,a_N)$ prise sur tous les $N$-uplets
-  $(a_1,\ldots,a_N)$ tels que $a_i = b$.} $s_1,\ldots,s_N$.
+  marginales}\footnote{\label{footnote-marginals}La $i$-ième
+  \defin{marginale} d'une variable aléatoire sur $A_1\times \cdots
+  \times A_N$ est simplement sa $i$-ième composante (= projection
+  sur $A_i$).  La $i$-ième \textbf{distribution marginale} de la
+  distribution de probabilités $s \colon A \to \mathbb{R}$ est donc la
+  distribution de probabilités $s_i \colon A_i \to \mathbb{R}$ qui à
+  $b\in A_i$ associe la somme des $s(a_1,\ldots,a_N)$ prise sur tous
+  les $N$-uplets $(a_1,\ldots,a_N)$ tels que $a_i =
+  b$.} $s_1,\ldots,s_N$.
 
 On identifiera parfois abusivement l'élément $(s_1,\ldots,s_N) \in S$
 à la distribution $s\colon A\to\mathbb{R}$ qu'on vient de décrire (ce
@@ -1269,17 +1272,18 @@ $s_i(b) = \sum_{a\,:\, a_i = b} s(a)$ où la somme est prise sur les $a
 \in A$ tels que $a_i = b$, cf. note \ref{footnote-marginals}).
 
 \danger Il faudra prendre garde au fait que, du coup, $S$ peut se voir
-soit comme la partie $S_1\times\cdots\times S_N$ de
+\emph{soit} comme la partie $S_1\times\cdots\times S_N$ de
 $\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$ formé des
-$N$-uplets $(s_1,\ldots,s_N)$, soit comme la partie de $\mathbb{R}^A =
-\mathbb{R}^{A_1\times\cdots\times A_N}$ formé des fonctions de la
-forme $s\colon (a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ comme on
-l'a expliqué au paragraphe précédent.  Ces deux points de vue ont un
-sens et ont parfois un intérêt, mais ils ne partagent pas les mêmes
-propriétés.  Par exemple, $S$ est convexe en tant que partie
-$S_1\times\cdots\times S_N$ de $\mathbb{R}^{A_1}\times\cdots\times
-\mathbb{R}^{A_N}$, mais pas en tant que partie de $\mathbb{R}^A$.
-Néanmoins, ce double point de vue ne devrait pas causer de confusion.
+$N$-uplets $(s_1,\ldots,s_N)$, \emph{soit} comme la partie de
+$\mathbb{R}^A = \mathbb{R}^{A_1\times\cdots\times A_N}$ formé des
+fonctions de la forme $s\colon (a_1,\ldots,a_N) \mapsto s_1(a_1)\cdots
+s_N(a_N)$ comme on l'a expliqué aux paragraphes précédents.  Ces deux
+points de vue ont un sens et ont parfois un intérêt, mais ils ne
+partagent pas les mêmes propriétés.  Par exemple, $S$ est convexe en
+tant que partie $S_1\times\cdots\times S_N$ de
+$\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$, mais pas en
+tant que partie de $\mathbb{R}^A$.  Néanmoins, ce double point de vue
+ne devrait pas causer de confusion.
 
 Ceci conduit à faire la définition suivante :
 
@@ -1304,7 +1308,8 @@ Selon l'approche qu'on veut avoir, on peut dire qu'on a défini
 $u_i(s)$ comme l'espérance de $u_i(a)$ si chaque $a_j$ est tiré
 indépendamment selon la distribution de probabilité $s_i$ ; ou bien
 qu'on a utilisé l'unique prolongement de $u_i$ au produit des
-simplexes $S_i$ qui soit affine en chaque variable $s_i$.
+simplexes $S_i$ qui soit affine en chaque variable $s_i$
+(« multi-affine »).
 
 
 
@@ -1313,24 +1318,26 @@ simplexes $S_i$ qui soit affine en chaque variable $s_i$.
 \begin{defn}\label{definition-best-response-and-nash-equilibrium}
 Donné un jeu en forme normale comme
 en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si
-$s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_1 \times \cdots
-\times S_{i-1} \times S_{i+1} \times \cdots \times S_N$ est un profil
-de stratégies mixtes pour tous les joueurs autres que le joueur $i$,
-on dit que la stratégie mixte $s_! \in S_i$ est une \defin{meilleure
-  réponse} (resp. la meilleure réponse \textbf{stricte}) contre $s_?$
-lorsque pour tout $t \in S_i$ on a $u_i(s_?,s_!) \geq u_i(s_?,t)$
-(resp. lorsque pour tout $t \in S_i$ différent de $s_!$ on a
-$u_i(s_?,s_!) > u_i(s_?,t)$), où $(s_?,t)$ désigne l'élément de
-$S_1\times \cdots \times S_N$ obtenu en insérant $t \in S_i$ comme
-$i$-ième composante entre $s_{i-1}$ et $s_{i+1}$, c'est-à-dire le gain
-[espéré] obtenu en jouant $t$ contre $s_?$.
+$s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_{?i} := S_1
+\times \cdots \times S_{i-1} \times S_{i+1} \times \cdots \times S_N$
+est un profil de stratégies mixtes pour tous les joueurs autres que le
+joueur $i$, on dit que la stratégie mixte $s_! \in S_i$ est une
+\defin{meilleure réponse} (resp. la meilleure réponse
+\textbf{stricte}) contre $s_?$ lorsque pour tout $t \in S_i$ on a
+$u_i(s_?,s_!) \geq u_i(s_?,t)$ (resp. lorsque pour tout $t \in S_i$
+différent de $s_!$ on a $u_i(s_?,s_!) > u_i(s_?,t)$), où $(s_?,t)$
+désigne l'élément de $S_1\times \cdots \times S_N$ obtenu en insérant
+$t \in S_i$ comme $i$-ième composante entre $s_{i-1}$ et $s_{i+1}$,
+c'est-à-dire le gain [espéré] obtenu en jouant $t$ contre $s_?$.
 
 Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble
-des joueurs) est dit être un \index{Nash (équilibre de)}\defin{équilibre de Nash} (resp., un
-équilibre de Nash \defin[strict (équilibre de Nash)]{strict}) lorsque pour tout $1\leq i \leq N$,
-la stratégie $s_i$ pour le joueur $i$ est une meilleure réponse
-(resp. la meilleure réponse stricte) contre le profil $s_{?i}$ pour
-les autres joueurs obtenu en supprimant la composante $s_i$ de $s$.
+des joueurs) est dit être un \index{Nash (équilibre
+  de)}\defin{équilibre de Nash} (resp., un équilibre de Nash
+\defin[strict (équilibre de Nash)]{strict}) lorsque pour tout $1\leq i
+\leq N$, la stratégie $s_i$ pour le joueur $i$ est une meilleure
+réponse (resp. la meilleure réponse stricte) contre le profil $s_{?i}
+:= (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N)$ pour les autres joueurs
+obtenu en supprimant la composante $s_i$ de $s$.
 \end{defn}
 
 Concrètement, donc, un équilibre de Nash est donc un profil de
@@ -1358,31 +1365,46 @@ stratégie pure.
 \end{prop}
 \begin{proof}
 Tout ceci résulte essentiellement des propositions
-\ref{affine-functions-take-no-strict-extrema-inside}
-et \ref{affine-functions-take-extrema-at-boundary} : le gain espéré
-$u_i(s_?,t)$ du joueur $i$ (une fois fixé le profi $s_?$ de tous les
-autres joueurs) est une fonction affine de la stratégie $t \in S_i$ du
-joueur $i$, et une fonction affine sur un simplexe prend son maximum
-sur un sommet du simplexe, et ne peut la prendre à l'intérieure que si
-elle la prend également en chaque sommet.
+\ref{affine-functions-take-extrema-at-boundary} et \ref{affine-functions-take-no-strict-extrema-inside} :
+le gain espéré $u_i(s_?,t)$ du joueur $i$ (une fois fixé le
+profil $s_?$ de tous les autres joueurs) est une fonction affine de la
+stratégie $t \in S_i$ du joueur $i$, et une fonction affine sur un
+simplexe prend son maximum sur un sommet du simplexe, et ne peut la
+prendre à l'intérieur d'une face (= enveloppe convexe d'un
+sous-ensemble des sommets) que si elle la prend également en chaque
+sommet de cette face.
 
 Plus précisément, soit $v = \max_{t \in S_i} u_i(s_?,t)$, dont la
-proposition \ref{affine-functions-take-no-strict-extrema-inside}
-garantit l'existence ; une meilleure réponse possible contre $s_?$ est
+proposition \ref{affine-functions-take-extrema-at-boundary} garantit
+l'existence ; une meilleure réponse possible contre $s_?$ est
 précisément un $t$ réalisant $u_i(s_?,t) = v$ : il résulte de la
 proposition citée que $v$ est aussi $\max_{a \in A_i} u_i(s_?,a)$,
 c'est-à-dire qu'il existe une stratégie \emph{pure} $a \in A_i$ qui
 est une meilleure réponse possible contre $s_?$.  Par ailleurs, si
 $s_!$ est une meilleure réponse, i.e., $u_i(s_?,s_!) = v$, alors la
-proposition \ref{affine-functions-take-extrema-at-boundary} (appliquée
-avec pour $x_1,\ldots,x_n$ les points du support de $s_!$) montre que
-chaque stratégie pure $a$ appartenant au support de $s_!$ vérifie
-aussi $u_i(s_?,a) = v$.
+proposition \ref{affine-functions-take-no-strict-extrema-inside}
+(appliquée avec pour $x_1,\ldots,x_n$ les points du support de $s_!$)
+montre que chaque stratégie pure $a$ appartenant au support de $s_!$
+vérifie aussi $u_i(s_?,a) = v$.
 
 Comme une meilleure réponse stricte est unique, elle est forcément
 pure d'après ce qu'on vient de voir.
 \end{proof}
 
+\textbf{Reformulation.}  Un profil de stratégies mixtes
+$(s_1,\ldots,s_N) \in S_1\times \cdots\times S_N$ est un équilibre de
+Nash si et seulement si, pour chaque $i$,
+\begin{itemize}
+\item pour tout $a$ dans le support de $s_i$, le gain espéré
+  $u_i(s_{?i},a)$ (rappelons que ceci est une notation pour
+  $u_i(s_1,\ldots,s_{i-1},a,s_{i+1},\ldots,s_N$) prend la \emph{même}
+  valeur, et
+\item cette valeur est supérieure ou égale à $u_i(s_{?i},b)$ pour
+  tout $b\in A_i$.
+\end{itemize}
+
+\smallskip
+
 On vient de voir que \emph{lorsque les stratégies de tous les autres
   joueurs sont fixées} (à $s_?$ dans la proposition ci-dessus), le
 joueur $i$ a une meilleure réponse en stratégie pure : on pourrait
@@ -1453,9 +1475,10 @@ mais elle peut donner l'impression qu'on commet une « erreur
 
 D'après la première expression donnée, il est clair qu'on a bien
 $s^\sharp_i \in S_i$, et qu'on a donc bien défini une fonction
-$T\colon S\to S$.  Cette fonction est continue, donc admet un point
-fixe $s$ d'après \ref{brouwer-fixed-point-theorem} (notons qu'ici, $S$
-est vu comme le convexe $S_1\times\cdots\times S_N$ dans
+$T\colon S\to S$.  Cette fonction est continue (comme composée de
+fonctions continues), donc admet un point fixe $s$
+d'après \ref{brouwer-fixed-point-theorem} (notons qu'ici, $S$ est vu
+comme le convexe $S_1\times\cdots\times S_N$ dans
 $\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$).  On va montrer
 que $s$ est un équilibre de Nash.
 
@@ -1557,7 +1580,7 @@ vérifier qu'il n'y en a pas d'autre, on peut :
   d'après \ref{stupid-remark-best-mixed-strategies}, le gain d'Alice
   dans les cases $(C,a)$ et $(F,a)$ doit être le même, ce qui n'est
   pas le cas, donc il n'y a pas de tel équilibre (pas plus que dans le
-  cas symétrique) ;
+  cas correspondant pour Bob) ;
 \item enfin, rechercher les équilibres de Nash où chacun des deux
   joueurs joue une stratégie supportée par les deux options, soit ici
   $pC+(1-p)F$ pour Alice et $qC+(1-q)F$ pour Bob avec $0<p<1$ et
@@ -1663,6 +1686,7 @@ alors :
 \max_{x\in S_1} \min_{y\in S_2} u(x,y) =
 \min_{y\in S_2} \max_{x\in S_1} u(x,y)
 \]
+(Ceci sous-entend notamment ces $\min$ et $\max$ existent bien.)
 
 Plus généralement, si $S_1$ et $S_2$ sont deux convexes compacts dans
 des espaces affines réels de dimension finie, et $u\colon S_1\times
@@ -1674,27 +1698,29 @@ Plaçons-nous d'abord dans le cas (qui intéresse la théorie des jeux)
 où $A_1,A_2$ sont deux ensembles finis et $S_1,S_2$ les simplexes de
 stratégies mixtes.
 
-Tout d'abord, l'inégalité dans le sens $\max\min \leq \min\max$ est
-facile : on a
+Tout d'abord, montrons l'existence des $\min$ et $\max$ annoncés ainsi
+que l'inégalité dans le sens $\max\min \leq \min\max$.  On a vu
+en \ref{affine-functions-take-extrema-at-boundary} que $\min_{y\in
+  S_2} u(x,y)$ existe et vaut $\min_{b\in A_2} u(x,b)$ pour tout $x\in
+S_1$ : ceci montre que la fonction $x \mapsto \min_{y\in S_2} u(x,y)$
+s'écrit encore $x \mapsto \min_{b\in A_2} u(x,b)$, donc il s'agit du
+minimum d'un nombre \emph{fini} de fonctions continues (affines)
+sur $S_1$, donc elle est encore continue et atteint ses bornes sur
+l'ensemble compact $S_1$ : il existe donc $x_* \in S_1$ où cette
+fonction atteint son maximum.  Soit de même $y_* \in S_2$ un point où
+$y \mapsto \max_{x\in S_1} u(x,y)$ atteint son minimum.  On a alors :
 \[
 \max_{x\in S_1} \min_{y\in S_2} u(x,y)
 = \min_{y\in S_2} u(x_*,y)
 \leq u(x_*,y_*) \leq \max_{x\in S_1} u(x,y_*) =
 \min_{y\in S_2} \max_{x\in S_1} u(x,y)
 \]
-où $x_* \in S_1$ est un point où $\max_{x\in S_1} \min_{y\in S_2}
-u(x,y)$ est atteint et $y_* \in S_2$ un point où $\min_{y\in S_2}
-\max_{x\in S_1} u(x,y)$ l'est (ces extrema existent car on a affaire à
-une fonction continue sur un compact, ou bien
-d'après \ref{affine-functions-take-extrema-at-boundary} car on a
-affaire à une fonction affine sur l'enveloppe convexe d'un nombre fini
-de points) : la première relation est la définition de $x_*$, la
-seconde est la définition du $\min$, la troisième la définition du
-$\max$, et la quatrième est la définition de $y_*$.  (Notons que tout
-ceci vaut dans n'importe quel contexte où les $\min$ et $\max$
-existent, notamment ceci prouve $\max_{a \in A_1} \min_{b\in A_2}
-u(a,b) \leq \min_{b\in A_2} \max_{a \in A_1} u(a,b)$ affirmé
-ci-dessus.)
+La première relation est la définition de $x_*$, la seconde est la
+définition du $\min$, la troisième la définition du $\max$, et la
+quatrième est la définition de $y_*$.  (Notons que tout ceci vaut dans
+n'importe quel contexte où les $\min$ et $\max$ existent, notamment
+ceci prouve aussi $\max_{a \in A_1} \min_{b\in A_2} u(a,b) \leq
+\min_{b\in A_2} \max_{a \in A_1} u(a,b)$ affirmé ci-dessus.)
 
 Il s'agit maintenant de prouver l'inégalité de sens contraire.
 
@@ -1787,78 +1813,109 @@ en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in S} u(x,y) =
 0$, ce qu'on voulait prouver.
 \end{proof}
 
-%% TODO: rendre ça plus clair ; énoncer un théorème précis pour les
-%% phrases en italiques.
-
-\thingy\label{minimax-for-games} Le théorème \ref{theorem-minimax}
-s'applique à la théorie des jeux de la manière suivante : si on
-considère un jeu à deux joueurs à somme nulle, en notant $S_1$ et
-$S_2$ les ensembles des stratégies mixtes des deux joueurs, et $u
-\colon S_1 \times S_2 \to \mathbb{R}$ le gain espéré du joueur $1$, le
-gain du joueur $2$ étant donc $-u$, le fait que $(x_0,y_0)$ soit un
-équilibre de Nash se traduit par le fait que $x_0$ soit la meilleure
-réponse possible de $1$ contre $y_0$, i.e., $u(x_0,y_0) = \max_{x\in
-  S_1} u(x,y_0)$, et le fait que $y_0$ soit la meilleure réponse
-possible de $2$ contre $x_0$, c'est-à-dire $u(x_0,y_0) = \min_{y\in
-  S_2} u(x_0,y)$ (puisque $2$ cherche à maximiser $-u$, c'est-à-dire
-minimiser $u$).  Comme on l'a expliqué dans la preuve, on a
-\[
-\max_{x\in S_1} \min_{y\in S_2} u(x,y)
-\geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0)
-= \max_{x\in S_1} u(x,y_0) \geq
-\min_{y\in S_2} \max_{x\in S_1} u(x,y)
-\]
-donc en fait il y a égalité partout : tout équilibre de Nash réalise
-la même valeur $u(x_0,y_0) = \max_{x\in S_1} \min_{y\in S_2} u(x,y) =
-\min_{y\in S_2} \max_{x\in S_1} u(x,y)$, qu'on appelle la
-\defin[valeur (d'un jeu à somme nulle)]{valeur} du jeu à somme nulle.
-
-On peut donc parler de \index{optimale (stratégie)}\defin{stratégie
-  optimale} pour le joueur $1$, resp. $2$ pour désigner une composante
-$x_0$, resp. $y_0$, d'un équilibre de Nash, i.e., vérifiant
-$\min_{y\in S_2} u(x_0,y) = \max_{x\in S_1} \min_{y\in S_2} u(x,y)$,
-resp. $\max_{x\in S_1} u(x,y_0) = \min_{y\in S_2} \max_{x\in S_1}
-u(x,y)$, ces deux quantités étant égales à la valeur du jeu.
-
-Moralité : \emph{dans un jeu à somme nulle, un profil de stratégies
+\smallskip
+
+Considérons maintenant les applications du
+théorème \ref{theorem-minimax} dans le cadre de la théorie des jeux.
+Commençons par définir les concepts suivants :
+
+\begin{defn}\label{definition-zero-sum-game-value-and-optimum}
+Pour un jeu à somme nulle défini par une matrice de gains $u \colon
+A_1 \times A_2 \to \mathbb{R}$ :
+\begin{itemize}
+\item La \defin[valeur (d'un jeu à somme nulle)]{valeur} est la valeur
+  commune $\max_{x\in S_1} \min_{y\in S_2} u(x,y) = \min_{y\in S_2}
+  \max_{x\in S_1} u(x,y)$ où $S_1,S_2$ sont les simplexes de
+  stratégies mixtes des joueurs $1$ et $2$ respectivement (et $u(x,y)$
+  l'espérance de gain explicitée
+  en \ref{definition-mixed-strategy-gain}).
+\item Une stratégie mixte du joueur $1$ qui réalise $\max_{x\in S_1}
+  \min_{y\in S_2} u(x,y)$ (resp. une stratégie mixte du joueur $2$ qui
+  réalise $\min_{y\in S_2} \max_{x\in S_1} u(x,y)$) est dite
+  \index{optimale (stratégie)}\defin{stratégie optimale} pour le
+  joueur en question.
+\end{itemize}
+\end{defn}
+
+Le théorème \ref{theorem-minimax} (et, pour le dernier point, le
+corollaire \ref{symmetric-zero-sum-game}) a alors les conséquences
+suivantes :
+
+\begin{prop}\label{minimax-for-games} Pour un jeu à somme nulle défini
+par une matrice de gains $u \colon A_1 \times A_2 \to \mathbb{R}$ :
+\begin{itemize}
+\item[(i)] Un profil $(x_0,y_0) \in S_1\times S_2$ de stratégies
+  mixtes est un équilibre de Nash si et seulement si $x_0$ et $y_0$
+  sont chacun une stratégie optimale pour le joueur correspondant.
+\item[(ii)] Tous les équilibres de Nash ont la même valeur de gain
+  espéré, à savoir la valeur du jeu $v$ (pour le joueur 1).
+\item[(iii)] Une stratégie mixte $x_0 \in S_1$ du joueur $1$ est une
+  stratégie optimale pour celui-ci si et seulement si $u(x_0,b) \geq
+  v$ pour tout $b\in A_2$ (où $v$ désigne la valeur du jeu).  Une
+  stratégie mixte $y_0 \in S_2$ du joueur $2$ est une stratégie
+  optimale pour celui-ci si et seulement si $u(a,y_0) \leq v$ pour
+  tout $a\in A_1$.
+\item[(iv)] L'ensemble $T_1$ des stratégies optimales du joueur $1$
+  est un convexe, de même que l'ensemble $T_2$ des stratégies
+  optimales du joueur $2$.  (L'ensemble des équilibres de Nash est
+  donc aussi un convexe, à savoir $T_1 \times T_2$.)
+\item[(v)] Si le jeu est symétrique, c'est-à-dire $A_2 = A_1 =: A$ et
+  $u(b,a) = -u(a,b)$ (matrice de gains antisymétrique), alors la
+  valeur du jeu est nulle.
+\end{itemize}
+\end{prop}
+
+\begin{proof}
+(i) : On a vu au cours de la preuve de \ref{theorem-minimax} que si
+  $(x_0,y_0)$ est un équilibre de Nash, alors $\max_{x\in S_1}
+  \min_{y\in S_2} u(x,y) \geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0) =
+  \max_{x\in S_1} u(x,y_0) \geq \min_{y\in S_2} \max_{x\in S_1}
+  u(x,y)$, mais comme les deux termes extrêmes sont égaux, en fait
+  toutes ces inégalités sont des égalités, donc $x_0$ réalise bien le
+  maximum $\max_{x\in S_1} \min_{y\in S_2} u(x,y)$ et $y_0$ le minimum
+  $\min_{y\in S_2} \max_{x\in S_1} u(x,y)$, i.e., ils sont des
+  stratégies optimales.  Réciproquement, si $x_*$ est une stratégie
+  optimale du joueur $1$ et $y_*$ du joueur $2$, on a vu au cours de
+  la même preuve qu'on a $\max_{x\in S_1} \min_{y\in S_2} u(x,y) =
+  \min_{y\in S_2} u(x_*,y) \leq u(x_*,y_*) \leq \max_{x\in S_1}
+  u(x,y_*) = \min_{y\in S_2} \max_{x\in S_1} u(x,y)$, et, de nouveau,
+  totues ces inégalités sont des égalités, donc $x_*$ est une
+  meilleure réponse possible pour le joueur $1$ contre $y_*$ et $y_*$
+  est une meilleure réponse possible pour le joueur $2$ contre $x_*$,
+  ce qui signifie que $(x_*,y_*)$ est un équilibre de Nash.
+
+Le point (ii) résulte de ce qui vient d'être dit.
+
+(iii) : Par définition, $x_0$ est optimale ssi $\min_{y\in S_2}
+u(x_0,y) = v$, ou, comme on ne peut pas faire plus que le maximum,
+$\min_{y\in S_2} u(x_0,y) \geq v$.  Mais on a vu
+en \ref{affine-functions-take-extrema-at-boundary} que $\min_{y\in
+  S_2} u(x_0,y) = \min_{b\in A_2} u(x_0,b)$, c'est-à-dire que $x_0$
+est optimale si et seulement si $\min_{b\in A_2} u(x_0,b) \geq v$, ce
+qui revient bien à dire $u(x_0,b) \geq v$ pour tout $b$.  Le cas de
+l'autre joueur est analogue.
+
+(iv) : Il résulte du point précédent que $T_1$ est l'intersections des
+ensembles $\{x \in S_1 : u(x,b)\geq v\}$ où $b$ parcourt $A_2$ : mais
+chacun de ces ensembles est convexe, donc leur intersection l'est
+aussi.  Le cas de $T_2$ est analogue.  La parenthèse est une redite du
+point (i).
+
+Le point (v) n'est qu'une redite du
+corollaire \ref{symmetric-zero-sum-game}.
+\end{proof}
+
+Répétons : \emph{dans un jeu à somme nulle, un profil de stratégies
   est un équilibre de Nash si et seulement si chaque joueur joue une
-  stratégie optimale} (l'ensemble des stratégies optimales étant
-défini pour chaque joueur indépendamment).
-
-Le corollaire \ref{symmetric-zero-sum-game} nous apprend (de façon peu
-surprenante) que si le jeu à somme nulle est \emph{symétrique} (ce qui
-signifie que $u$ est antisymétrique), alors la valeur du jeu est
-nulle.
-
-\thingy Dans le contexte ci-dessus, on peut légèrement reformuler le
-minimax : si on se rappelle (cf. \ref{stupid-remark-best-mixed-strategies})
-qu'une fonction affine sur un
-  simplexe prend son maximum (ou son minimum) sur un des sommets du
-simplexe, cela signifie que, quel que soit $x\in S_1$ fixé, le minimum
-$\min_{y\in S_2} u(x,y)$ est en fait atteint sur une stratégie
-\emph{pure}, $\min_{y\in S_2} u(x,y) = \min_{b\in A_2} u(x,b)$ (avec
-$A_2$ l'ensemble des sommets de $S_2$, i.e., l'ensemble des stratégies
-pures du joueur $2$), et de même $\max_{x\in S_1} u(x,y) = \max_{a\in
-  A_1} u(a,y)$ quel que soit $y \in S_2$.  \emph{Ceci ne signifie pas}
-qu'il existe un équilibre de Nash en stratégies pures (penser à
-pierre-papier-ciseaux).  Néanmoins, cela signifie que pour calculer la
-pire valeur possible $\min_{y\in S_2} u(x,y)$ d'une stratégie $x$ du
-joueur $1$, celui-ci peut ne considérer que les réponses en stratégies
-pures du joueur $2$.
-
-Si on appelle $v$ la valeur du jeu, l'ensemble des $x$ tels que
-$u(x,y) \geq v$ pour tout $y\in S_2$, c'est-à-dire l'ensemble des
-stratégies optimales pour le joueur $1$, coïncide donc avec l'ensemble
-des $x$ tels que $u(x,b) \geq v$ pour tout $b\in A_2$.  En
-particulier, c'est un convexe compact dans $S_1$ (puisque chaque
-inégalité $u(x,b) \geq v$ définit un convexe compact dans $S_1$ vu que
-$x \mapsto u(x,b)$ est affine) : \emph{en moyennant deux stratégies
-  optimales pour un joueur on obtient encore une telle stratégie}
-(notamment, l'ensemble des équilibres de Nash est un convexe de
-$S_1\times S_2$ — puisque c'est le produit du convexe des stratégies
-optimales pour le premier joueur par celui des stratégies optimales
-pour le second — affirmation qui n'est pas vraie en général pour des
-jeux qui ne sont pas à somme nulle).
+  stratégie optimale}, l'ensemble des stratégies optimales étant un
+convexe (défini pour chaque joueur indépendamment).
+
+L'ensemble des stratégies optimales d'un joueur donné est « très
+souvent » un singleton, ce qui fait qu'on parle parfois abusivement de
+« la » stratégie optimale.
+
+Reste maintenant à expliquer comment calculer les stratégies
+optimales :
 
 \begin{algo}\label{zero-sum-games-by-linear-programming-algorithm}
 Donnée une fonction $u\colon A_1 \times A_2 \to \mathbb{R}$ (avec
@@ -1877,6 +1934,9 @@ $\#A_1 + 1$ variables avec des contraintes de positivité sur $\#A_1$
 d'entre elles, une contrainte d'égalité et $\#A_2$ inégalités affines.
 \end{algo}
 
+(La correction de cet algorithme découle à peu près immédiatement du
+point (iii) ci-dessus.)
+
 \thingy Pour ramener ce problème à un problème de programmation
 linéaire en \emph{forme normale} (maximiser $\textbf{p} x$ sous les
 contraintes $\textbf{M} x \leq \textbf{q}$ et $x\geq 0$), on sépare la
-- 
cgit v1.2.3