State and prove von Neumann's minimax theorem.

1 files changed, 137 insertions, 16 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 132c476..183307a 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -568,23 +568,23 @@ Nash.
 
 Pour démontrer le théorème en question, on utilise (et on admet) le
 théorème du point fixe de Brouwer, qui affirme que si $K$ est un
-convexe compact de $\mathbb{R}^m$, et que $f \colon K \to K$ est
-continue, alors il existe $x\in K$ tel que $f(x) = x$ (un \emph{point
-  fixe} de $f$, donc).
+convexe compact de $\mathbb{R}^m$, et que $T \colon K \to K$ est
+continue, alors il existe $x\in K$ tel que $T(x) = x$ (un \emph{point
+  fixe} de $T$, donc).
 
 L'idée intuitive de la démonstration suivante est : partant d'un
 profil $s$ de stratégies, on peut définir continûment un nouveau
-profil $s'$ en donnant plus de poids aux options qui donnent un
-meilleur gain au joueur correspondant — si bien que $s'$ sera
-différent de $s$ dès que $s'$ n'est pas un équilibre de Nash.  Comme
-la fonction $f \colon s \to s'$ doit avoir un point fixe, ce point
+profil $s^\sharp$ en donnant plus de poids aux options qui donnent un
+meilleur gain au joueur correspondant — si bien que $s^\sharp$ sera
+différent de $s$ dès que $s^\sharp$ n'est pas un équilibre de Nash.  Comme
+la fonction $T \colon s \to s^\sharp$ doit avoir un point fixe, ce point
 fixe sera un équilibre de Nash.
 
 \begin{proof}[Démonstration de \ref{theorem-nash-equilibria}]
 Si $s \in S$ et $1\leq i\leq N$, convenons de noter $s_{?i}$
 l'effacement de la composante $s_i$ (c'est-à-dire le profil pour les
 joueurs autres que $i$).  Si de plus $b \in A_i$, notons
-$\varphi_{i,b}(s) = \max\{0, u_i(s_{?i},b) - u_i(s)\}$ l'augmentation
+$\varphi_{i,b}(s) = \max(0,\; u_i(s_{?i},b) - u_i(s))$ l'augmentation
 du gain du joueur $i$ si on remplace sa stratégie $s_i$ par la
 stratégie pure $b$ en laissant le profil $s_{?i}$ des autres joueurs
 inchangé (ou bien $0$ s'il n'y a pas d'augmentation).  On remarquera
@@ -594,15 +594,18 @@ A_i$ (faire appel à la proposition précédente pour le « si »).  On
 remarquera aussi que chaque $\varphi_{i,b}$ est une fonction continue
 sur $S$.
 
-Définissons maintenant $f\colon S\to S$ de la façon suivante : si $s
-\in S$, on pose $f(s) = s'$, où $s' = (s'_1,\ldots,s'_N)$ avec
+Définissons maintenant $T\colon S\to S$ de la façon suivante : si $s
+\in S$, on pose $T(s) = s^\sharp$, où $s^\sharp =
+(s^\sharp_1,\ldots,s^\sharp_N)$ avec $s^\sharp_i$ le barycentre de
+$s_i$ avec coefficient $1$ et des $a_i$ avec les coefficients
+$\varphi_{i,a}(s)$, autrement dit :
 \[
 \begin{aligned}
-s'_i(a) &= \frac{s_i(a) + \varphi_{i,a}(s)}{\sum_{b\in A_i}(s_i(b) + \varphi_{i,b}(s))}\\
+s^\sharp_i(a) &= \frac{s_i(a) + \varphi_{i,a}(s)}{\sum_{b\in A_i}(s_i(b) + \varphi_{i,b}(s))}\\
 &= \frac{s_i(a) + \varphi_{i,a}(s)}{1 + \sum_{b\in A_i}\varphi_{i,b}(s)}
 \end{aligned}
 \]
-(L'important est que $s'_i$ augmente strictement le poids des options
+(L'important est que $s^\sharp_i$ augmente strictement le poids des options
 $a\in A_i$ telles que $u_i(s_{?i},a) > u_i(s)$ ; en fait, on pourrait
 composer $\varphi$ à gauche par n'importe quelle fonction $\mathbb{R}
 \to \mathbb{R}$ croissante, continue, nulle sur les négatifs et
@@ -611,8 +614,8 @@ l'identité ci-dessus pour rendre l'expression plus simple à écrire,
 mais elle peut donner l'impression qu'on commet une « erreur
   d'homogénéité » en ajoutant un gain à une probabilité.)
 
-D'après la première expression donnée, il est clair qu'on a bien $s'_i
-\in S_i$, et qu'on a donc bien défini une fonction $f\colon S\to S$.
+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$.  On va
 montrer que $s$ est un équilibre de Nash.
 
@@ -621,15 +624,133 @@ u_i(s)$ (car, comme dans la preuve
 de \ref{stupid-remark-best-mixed-strategies}, $u_i(s)$ est combinaison
 convexe des $u_i(s_{?i},a)$ dont est supérieur au plus petit d'entre
 eux) : c'est-à-dire $\varphi_{i,a}(s) = 0$.  Pour un tel $a$, la
-seconde expression $s'_i(a) = s_i(a) / \big(1 + \sum_{b\in
+seconde expression $s^\sharp_i(a) = s_i(a) / \big(1 + \sum_{b\in
   A_i}\varphi_{i,b}(s)\big)$ montre, en tenant compte du fait que
-$s'_i = s_i$ puisque $s$ est un point fixe, que $\sum_{b\in A_i}
+$s^\sharp_i = s_i$ puisque $s$ est un point fixe, que $\sum_{b\in A_i}
 \varphi_{i,b}(s) = 0$, donc $\varphi_{i,b}(s) = 0$ pour tout $b$.  On
 vient de voir que les $\varphi_{i,b}(s)$ sont nuls pour tout $i$ et
 tout $b$, et on a expliqué que ceci signifie que $s$ est un équilibre
 de Nash.
 \end{proof}
 
+\textcolor{red}{Dire quelque chose sur l'algorithme de Lemke-Howson ?}
+
+
+%
+%
+%
+
+\section{Jeux à somme nulle en forme normale}
+
+\subsection{Le théorème du minimax}
+
+\begin{thm}[« du minimax », 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
+\[
+\max_{x\in C} \min_{y\in C'} u(x,y) =
+\min_{y\in C'} \max_{x\in C} u(x,y)
+\]
+\end{thm}
+\begin{proof}
+Tout d'abord, l'inégalité dans un sens est évidente : 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)
+\]
+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 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
+\[
+\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)
+\]
+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.
+\end{proof}
+
+\begin{cor}
+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$).
+\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}y
+\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) =
+0$, ce qu'on voulait prouver.
+\end{proof}
+
+Avec les hypothèses et notations du corollaire, l'ensemble des $x$
+tels que $u(x,y)\geq 0$ pour tout $y\in C$ est un convexe
+compact $C_0 \neq \varnothing$ inclus dans $C$.
+
 %
 %
 %