Rework the part about the minimax theorem.

1 files changed, 144 insertions, 90 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 4df00fb..237e5c9 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1283,12 +1283,12 @@ Néanmoins, ce double point de vue ne devrait pas causer de confusion.
 
 Ceci conduit à faire la définition suivante :
 
-\begin{defn}
+\begin{defn}\label{definition-mixed-strategy-gain}
 Donné un jeu en forme normale comme
 en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in
 S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on
-appelle \defin[gain espéré]{gain [espéré]} du joueur $i$ selon ce profil la
-quantité
+appelle \defin[gain espéré]{gain [espéré]} du joueur $i$ selon ce
+profil la quantité
 \[
 u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a)
 \]
@@ -1629,107 +1629,161 @@ dire que $(s_1,\ldots,s_N)$ est un équilibre de Nash.  Autrement dit :
 
 \subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games}
 
+Plaçons nous maintenant dans le cadre d'un jeu à somme nulle,
+c'est-à-dire qu'il y a $N=2$ joueurs, et qu'ils ont des gains
+opposés : disons qu'on appelle $u = u_1$ le gain du joueur $1$
+(« Alice »), le gain du joueur $2$ (« Bob ») étant alors $u_2 = -u$ et
+n'a pas besoin d'être écrit dans le tableau.  Ainsi, Alice cherche à
+\emph{maximiser} $u$ et Bob cherche à le \emph{minimiser} (puisque
+maximiser $-u$ revient à minimiser $u$).
+
+En considérant le jeu du point de vue de sa matrice de gains (où, de
+nouveau, on n'a écrit que le gain d'Alice), Alice cherche à choisir
+une ligne qui maximiser la valeur écrite dans le tableau et Bob
+cherche à choisir une colonne qui mimimise la valeur écrite.  Mais en
+général, si $u\colon A_1 \times A_2 \to \mathbb{R}$ est un tableau
+fini de nombres réels, $\max_{a \in A_1} \min_{b\in A_2} u(a,b)$ ne
+coïncide pas avec $\min_{b\in A_2} \max_{a \in A_1} u(a,b)$ (on a
+seulement l'inégalité $\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)$, qui sera démontrée ci-dessus
+au début de la démonstration de \ref{theorem-minimax}).  L'observation
+cruciale est que, quand on passe des ensembles finis $A_i$ de
+stratégies pures aux simplexes $S_i$ de stratégies mixtes, on a alors
+une égalité :
+
 \begin{thm}[« du minimax », J. von Neumann, 1928]\label{theorem-minimax}
-Soient $C$ et $C'$ deux convexes compacts dans des espaces affines
-réels de dimension finie, et $u\colon C\times C' \to \mathbb{R}$
-une application bi-affine (c'est-à-dire, affine en chaque variable
-séparément).  Alors
+Soient $A_1,A_2$ deux ensembles finis et $S_1,S_2$ les simplexes de
+stratégies mixtes (cf. \ref{definition-mixed-strategy-abst})
+sur $A_1,A_2$ ; soit $u\colon A_1\times A_2 \to \mathbb{R}$ une
+fonction quelconque, et on notera encore $u$ son unique extension
+(explicitée en \ref{definition-mixed-strategy-gain}) en une fonction
+$S_1\times S_2 \to \mathbb{R}$ affine en chaque variable.  On a
+alors :
 \[
-\max_{x\in C} \min_{y\in C'} u(x,y) =
-\min_{y\in C'} \max_{x\in C} u(x,y)
+\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)
 \]
+
+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
+S_2 \to \mathbb{R}$ une application affine en chaque variable
+séparément, alors on a l'égalité ci-dessus.
 \end{thm}
 \begin{proof}
-Tout d'abord, l'inégalité dans un sens est évidente : on a
+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
 \[
-\max_{x\in C} \min_{y\in C'} u(x,y)
-= \min_{y\in C'} u(x_*,y)
-\leq u(x_*,y_*) \leq \max_{x\in C} u(x,y_*) =
-\min_{y\in C'} \max_{x\in C} u(x,y)
+\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 C$ est un point où $\max_{x\in C} \min_{y\in C'}
-u(x,y)$ est atteint et $y_* \in C'$ un point où $\min_{y\in C'}
-\max_{x\in C} u(x,y)$ l'est.  Il s'agit donc de prouver
-l'inégalité de sens contraire.
-
-Commençons par supposer que $C$ est l'enveloppe convexe d'un nombre
-fini de points $(x_i)_{i\in I}$ et $C'$ de $(y_j)_{j\in J}$, et on
-expliquera plus loin comment se ramener à ce cas (même si c'est le
-seul qui servira dans le cadre de la théorie des jeux).  Lorsque cette
-hypothèse est vérifiée, on va définir une fonction $T\colon C\times C'
-\to C\times C'$ de la façon suivante.  Donnons-nous $(x,y) \in C\times
-C'$.  Pour chaque $i\in I$, on définit $\varphi_i(x,y) = \max (0,\;
-u(x_i,y)-u(x,y))$, et de même on pose $\psi_j(x,y) = \max (0,\;
-u(x,y)-u(x,y_j))$.  Posons enfin $T(x,y) = (x^\sharp,y^\sharp)$ où
-$x^\sharp$ et $y^\sharp$ (qui dépendent tous les deux de $x$ et $y$ à
-la fois, malgré la notation) sont définis comme suit.  On appelle
-$x^\sharp$ le barycentre de $x$ affecté du coefficient $1$ et des
-$x_i$ (pour $i\in I$) affectés des coefficients respectifs
-$\varphi_i(x,y)$, c'est-à-dire $x^\sharp = \frac{x + \sum_{i\in I}
-  \varphi_i(x,y)\,x_i}{1 + \sum_{i\in I} \varphi_i(x,y)}$ ; et soit de
-même $y^\sharp$ le barycentre de $y$ avec coefficient $1$ et des $y_i$
-avec les coefficients $\psi_i(x,y)$.  Clairement, $x^\sharp$ et
-$y^\sharp$ sont dans $C$ et $C'$ respectivement (il s'agit de
-barycentres à coefficients positifs, c'est-à-dire de combinaisons
-convexes).  La fonction $T\colon C\times C' \to C\times C'$ définie
-par $T(x,y) = (x^\sharp,y^\sharp)$ est continue.  Par ailleurs, on a
-$x^\sharp = x$ si et seulement si $x$ réalise $\max_{\tilde x\in C}
-u(\tilde x,y)$ (un sens est évident, et pour l'autre il suffit de se
-convaincre que s'il existe $\tilde x$ tel que $u(\tilde x,y) > u(x,y)$
-alors il y a un $i$ tel que ceci soit vrai en remplaçant $\tilde x$
-par $x_i$, et on a alors $\varphi_i(x,y)>0$ donc $u(x^\sharp,y) >
-u(x,y)$) ; et on a un résultat analogue pour $y$.  La fonction $T$
-continue du compact convexe $C\times C'$ vers lui-même y admet
-d'après \ref{brouwer-fixed-point-theorem} un
-point fixe $(x_0,y_0)$, vérifiant donc $(x_0^\sharp, y_0^\sharp) =
-(x_0,y_0)$, c'est-à-dire que $u (x_0,y_0) = \max_{x\in C} u(x,y_0) =
-\min_{y\in C'} u(x_0, y)$.  On a donc maintenant
+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.)
+
+Il s'agit maintenant de prouver l'inégalité de sens contraire.
+
+Considérons $(x_0,y_0)$ un équilibre de Nash du jeu à somme nulle dont
+la matrice de gains est donnée par $u$ pour le joueur $1$ (et $-u$
+pour le joueur $2$) : on sait qu'un tel équilibre existe
+d'après \ref{theorem-nash-equilibria}.  On a alors
 \[
-\max_{x\in C} \min_{y\in C'} u(x,y)
-\geq \min_{y\in C'} u(x_0,y) = u(x_0,y_0)
-= \max_{x\in C} u(x,y_0) \geq
-\min_{y\in C'} \max_{x\in C} u(x,y)
+\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)
 \]
-ce qu'on voulait.
-
-Pour se ramener au cas où $C$ et $C'$ sont enveloppes convexes d'un
-nombre fini de points, on observe que pour tout $\varepsilon>0$ il
-existe $\Sigma$ et $\Sigma'$ des enveloppes convexes d'un nombre fini
-de points (= polytopes) contenues dans $C$ et $C'$ respectivement et
-telles que pour tout $x\in C$ on ait $\min_{y\in C'} u(x,y) >
-\min_{y\in\Sigma'} u(x,y)-\varepsilon$ et $\max_{x\in C} u(x,y) <
-\max_{x\in\Sigma} u(x,y)+\varepsilon$ (explication : il est trivial
-que pour chaque $x$ il existe un $\Sigma'$ vérifiant la condition
-demandée, le point intéressant est qu'un unique $\Sigma'$ peut
-convenir pour tous les $x$ ; mais pour chaque $\Sigma'$ donné,
-l'ensemble des $x$ pour lesquels il convient est un ouvert de $C$, qui
-est compact, donc un nombre fini de ces ouverts recouvrent $C$, et on
-prend l'enveloppe convexe de la réunion des $\Sigma'$ en question ; on
-procède de même pour $\Sigma$).  On a alors $\max_{x\in C} \min_{y\in
-  C'} u(x,y) > \max_{x\in \Sigma} \min_{y\in \Sigma'} u(x,y) -
-\varepsilon$ et une inégalité analogue pour l'autre membre : on en
-déduit l'inégalité recherchée à $2\varepsilon$ près, mais comme on
-peut prendre $\varepsilon$ arbitrairement petit, on a ce qu'on
-voulait.
+Ici, la première relation est la définition du $\max$, la seconde
+traduit le fait que (dans la définition de l'équilibre de Nash) Bob
+fait une meilleure réponse possible à $x_0$, la troisième traduit le
+fait qu'Alice fait une meilleure réponse possible à $y_0$, et la
+quatrième est la définition du $\min$.
+
+Ceci achève de montrer $\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)$ lorsque $S_1$ et $S_2$ sont
+deux simplexes dans $\mathbb{R}^n$, et $u\colon S_1\times S_2 \to
+\mathbb{R}$ une application affine en chaque variable séparément.  Si
+maintenant $S_1$ et $S_2$ sont deux polytopes, c'est-à-dire chacun
+l'enveloppe d'un nombre fini de points $A_1$ et $A_2$
+dans $\mathbb{R}^n$, mais plus forcément des simplexes (c'est-à-dire
+qu'on ne suppose plus les points de $A_i$ affinement indépendants), la
+même conclusion vaut encore : en effet, si on appelle $S'_i$ le
+simplexe construit abstraitement sur $A_i$ (i.e., l'ensemble des
+fonctions $s\colon A_i \to \mathbb{R}$ positives de somme $1$), et
+$\varpi_i \colon S'_i \to S_i$ la fonction (affine et surjective)
+envoyant $s\colon A_i \to \mathbb{R}$ positive de somme $1$ sur la
+somme des $s(a)\cdot a$ (dans le $\mathbb{R}^n$ où vivent $A_i$
+et $S_i$), alors la fonction $u\colon S_1\times S_2 \to \mathbb{R}$
+donnée définit une fonction $u'\colon S'_1\times S'_2 \to \mathbb{R}$,
+elle aussi affine en chaque variable, par $u'(x,y) = u(\varpi_1(x),
+\varpi_2(y))$, et il est évident que les extrema de $u'$ sur $S'_1
+\times S'_2$ coïncident avec ceux de $u$ sur $S_1 \times S_2$, donc la
+conclusion qui précède, appliquée à $u'$, donne la conclusion désirée
+sur $u$.
+
+Enfin, si $S_1$ et $S_2$ sont seulement supposés être des convexes
+compacts dans $\mathbb{R}^n$, on observe que pour tout $\varepsilon>0$
+il existe $\Sigma_1$ et $\Sigma_2$ des polytopes contenus dans $S_1$
+et $S_2$ respectivement et tels que pour tout $x\in S_1$ on ait
+$\min_{y\in S_2} u(x,y) > \min_{y\in\Sigma_2} u(x,y)-\varepsilon$ et
+$\max_{x\in S_1} u(x,y) < \max_{x\in\Sigma_1} u(x,y)+\varepsilon$
+(explication : il est trivial que pour chaque $x$ il existe un
+$\Sigma_2$ vérifiant la condition demandée, le point intéressant est
+qu'un unique $\Sigma_2$ peut convenir pour tous les $x$ ; mais pour
+chaque $\Sigma_2$ donné, l'ensemble des $x$ pour lesquels il convient
+est un ouvert de $S_1$, qui est compact, donc un nombre fini de ces
+ouverts recouvrent $S_1$, et on prend l'enveloppe convexe de la
+réunion des $\Sigma_2$ en question ; on procède de même pour
+$\Sigma_1$).  On a alors $\max_{x\in S_1} \min_{y\in S_2} u(x,y) >
+\max_{x\in \Sigma_1} \min_{y\in \Sigma_2} u(x,y) - \varepsilon$ et une
+inégalité analogue pour l'autre membre : on en déduit l'inégalité
+recherchée à $2\varepsilon$ près, mais comme on peut prendre
+$\varepsilon$ arbitrairement petit, on a ce qu'on voulait.
 \end{proof}
 
+Le corollaire suivant explicite la situation particulière où, en
+outre, le jeu est symétrique entre les deux joueurs (c'est-à-dire que
+sa matrice de gains écrite pour un seul joueur est, elle,
+\emph{anti}symétrique) :
+
 \begin{cor}\label{symmetric-zero-sum-game}
-Soit $C$ un convexe compact dans un espace affine réel de dimension
-finie, et $u\colon C^2 \to \mathbb{R}$ une application bi-affine
-antisymétrique (i.e., $u(y,x) = -u(x,y)$).  Alors il
-existe $x\in C$ tel que pour tout $y\in C$ on ait $u(x,y)\geq 0$
-(et la valeur commune des deux membres de l'égalité du
-théorème \ref{theorem-minimax} est $0$).
+Soient $A$ un ensemble fini et $S$ le simplexe de stratégies mixtes
+sur $A$ ; soit $u\colon A^2 \to \mathbb{R}$ une application
+antisymétrique (i.e., $u(b,a) = -u(a,b)$), et on notera encore $u$ son
+unique extension affine en chaque variable en une fonction $S^2 \to
+\mathbb{R}$ affine en chaque variable.  Alors la valeur commune des
+deux membres de l'égalité du théorème \ref{theorem-minimax} est $0$ :
+il existe $x\in S$ tel que pour tout $y\in S$ on ait $u(x,y)\geq 0$.
+
+Plus généralement, si $S$ est un convexe compact dans un espace affine
+réel de dimension finie, et $u\colon S^2 \to \mathbb{R}$ une
+application antisymétrique (i.e., $u(y,x) = -u(x,y)$) et affine en
+chaque variable séparément, la même conclusion vaut.
 \end{cor}
 \begin{proof}
-On applique le théorème : il donne $\max_{x\in C}\penalty0 \min_{y\in
-  C} u(x,y) = \min_{y\in C}\penalty0 \max_{x\in C} u(x,y)$.  Mais
-puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in C}
-\max_{x\in C} (-u(y,x))$, soit, en renommant les variables liées,
-$\min_{x\in C}\penalty0 \max_{y\in C} (-u(x,y)) = -\max_{x\in
-  C}\penalty0 \min_{y\in C} u(x,y)$.  Par conséquent, $\max_{x\in
-  C}\penalty0 \min_{y\in C} u(x,y) = 0$ (il est son propre opposé), et
-en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in C} u(x,y) =
+On applique le théorème : il donne $\max_{x\in S}\penalty0 \min_{y\in
+  S} u(x,y) = \min_{y\in S}\penalty0 \max_{x\in S} u(x,y)$.  Mais
+puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in S}
+\max_{x\in S} (-u(y,x))$, soit, en renommant les variables liées,
+$\min_{x\in S}\penalty0 \max_{y\in S} (-u(x,y)) = -\max_{x\in
+  S}\penalty0 \min_{y\in S} u(x,y)$.  Par conséquent, $\max_{x\in
+  S}\penalty0 \min_{y\in S} u(x,y) = 0$ (il est son propre opposé), et
+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}