Rework the section on normal form games (convex sets and generalities).

1 files changed, 177 insertions, 56 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index fb055b0..c125348 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1022,7 +1022,9 @@ surréels de Conway.
 
 \section{Jeux en forme normale}\label{section-games-in-normal-form}
 
-\setcounter{comcnt}{0}
+\setcounter{subsection}{-1}
+
+\subsection{Rappels sur les convexes}
 
 \thingy Pour cette section, on rappelle les définitions suivants : une
 \index{affine (combinaison)|see{combinaison affine}}\defin{combinaison
@@ -1037,7 +1039,17 @@ $\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$).
 
-Une \index{convexe (combinaison)|see{combinaison
+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
+$\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
+revient au même de dire que $x_2-x_1,\ldots,x_m-x_1$ sont linéairement
+indépendants.
+
+\thingy Une \index{convexe (combinaison)|see{combinaison
     convexe}}\defin{combinaison convexe} est une combinaison affine
 $\sum_{i=1}^m \lambda_i x_i$ où $\lambda_1,\ldots,\lambda_m$ sont
 \emph{positifs} ($\lambda_1,\ldots,\lambda_m \geq 0$) et vérifient
@@ -1048,16 +1060,86 @@ Un \defin{convexe} de $\mathbb{R}^m$ est une partie stable par
 combinaisons convexes (c'est-à-dire que $C$ est dit convexe lorsque si
 $x_1,\ldots,x_m \in C$ et $\lambda_1,\ldots\lambda_m\geq 0$ vérifient
 $\sum_{i=1}^m \lambda_i = 1$ alors $\sum_{i=1}^m \lambda_i x_i \in
-C$).
-
-Une \index{affine (application)}\textbf{application affine} $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 d'une
-constante (dans $\mathbb{R}^q$) et d'une application linéaire
+C$).  Par associativité du barycentre, il revient au même d'imposer
+cette condition pour $m=2$, c'est-à-dire que $C \subseteq
+\mathbb{R}^m$ est convexe ssi on a $[x,y] \subseteq C$ pour tous
+$x,y\in C$, où $[x,y] := \{\lambda x + (1-\lambda) y : \lambda \in
+[0;1]\}$.
+
+Une intersection quelconque de convexes étant manifestement un
+convexe, on peut parler du plus petit convexe contenant une partie $A
+\subseteq \mathbb{R}^m$, appelé \index{convexe
+  (enveloppe)|see{enveloppe convexe}}\defin{enveloppe convexe}
+de $A$ : il s'agit simplement de l'ensemble de toutes les combinaisons
+convexes des points de $A$ (i.e., des ensembles \emph{finis} de points
+de $A$).  L'enveloppe convexe d'une partie finie s'appelle un
+\defin{polytope} (convexe).  L'enveloppe convexe d'une partie $A$
+affinement libre et finie\footnote{Une partie affinement libre de
+  $\mathbb{R}^m$ a au plus $m+1$ points, donc le mot « fini » est
+  redondant dans ce cadre, mais la définition peut s'étendre en
+  dimension infinie auquel cas il n'est plus inutile.} s'appelle
+\defin{simplexe} de sommets $A$.
+
+\thingy Une \index{affine (application)}\textbf{application affine}
+$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
+d'une constante (dans $\mathbb{R}^q$) et d'une application linéaire
 $\mathbb{R}^p \to \mathbb{R}^q$.
 
+On aura fréquemment besoin du fait évident suivant :
+\begin{prop}\label{affine-functions-take-extrema-at-boundary}
+Soit $A \subseteq \mathbb{R}^m$ un ensemble fini et $C$ son enveloppe
+convexe, et soit $u \colon \mathbb{R}^m \to \mathbb{R}$ une
+application affine.  Alors $u(a) \leq M$ pour tout $a \in A$ implique
+$u(s) \leq M$ pour tout $s \in C$.  Ou, si on préfère, $\max\{u(s) :
+s\in C\}$ existe et vaut $\max\{u(a) : a\in A\}$ (et la même
+affirmation en remplaçant $\max$ par $\min$ vaut aussi).
+\end{prop}
+
+En français : « une fonction affine sur un polytope atteint ses bornes
+sur un sommet de ce dernier ».
+
+\begin{proof}
+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
+$u(a) \leq M$ pour tout $a\in A$, ceci implique $u(s) \leq
+\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
+puisque $A$ est fini) : on a $u(s) \leq M$ pour tout $s \in C$, et
+comme les éléments de $A$ sont dans $C$, ceci montre bien $\max\{u(s)
+: s\in C\} = \max\{u(a) : a\in A\}$.
+\end{proof}
+
+\begin{prop}\label{affine-functions-take-no-strict-extrema-inside}
+Reprenons le contexte de la proposition précédente ($A \subseteq
+\mathbb{R}^m$ un ensemble fini, $C$ son enveloppe convexe, et $u
+\colon \mathbb{R}^m \to \mathbb{R}$ affine), et soit $M := \max_{a \in
+  A} u$ (dont on vient de voir que c'est aussi $\max_{s\in C} u$) : si
+une combinaison convexe $s$ à coefficients \emph{strictement positifs}
+de points de $A$ (i.e., $s = \sum_{i=1}^n \lambda_i x_i$ avec $x_i \in
+A$ et $\lambda_i > 0$ vérifiant $\sum_{i=1}^n \lambda_i = 1$) vérifie
+$u(s) = M$, alors chacun des points en question vérifie aussi cette
+propriété (i.e., on a $u(x_i) = M$ pour tout $i$).
+\end{prop}
+
+\begin{proof}
+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$.
+\end{proof}
+
+On peut aussi reformuler ce résultat en affirmant que la partie de $C$
+où $u$ prend sa valeur maximale $M$ est l'enveloppe convexe de la
+partie de $A$ où elle prend cette valeur.
+
+
 \subsection{Généralités}
 
 \begin{defn}\label{definition-game-in-normal-form}
@@ -1086,36 +1168,49 @@ fait que les joueurs peuvent également jouer de façon probabiliste, ce
 qui amène à introduire la notion de stratégie mixte :
 
 \begin{defn}\label{definition-mixed-strategy-abst}
-Donné un ensemble $B$ fini d'« options », on appelle \index{mixte (stratégie)}\defin{stratégie
-  mixte} sur $B$ une fonction $s\colon B\to\mathbb{R}$ telle que
-$s(b)\geq 0$ pour tout $b\in B$ et $\sum_{b\in B} s(b) = 1$ :
-autrement dit, il s'agit d'une distribution de probabilités sur $B$.
-
-Le \defin[support (d'une stratégie mixte)]{support} de $s$ est l'ensemble des options $b\in B$ pour
-lesquelles $s(b) > 0$.
-
-Parfois, on préférera considérer la stratégie comme la combinaison
-formelle $\sum_{b\in B} s(b)\cdot b$ (« formelle » signifiant que le
-produit $t\cdot b$ utilisé ici n'a pas de sens intrinsèque : il est
-défini par son écriture ; l'écriture $\sum_{b\in B} s(b)\cdot b$ est
-donc une simple notation pour $s$).  Autrement dit, ceci correspond à
-voir une stratégie mixte comme une combinaison convexe d'éléments
-de $B$, i.e., un point du simplexe affine dont les sommets sont les
-éléments de $B$.  En particulier, un élément $b$ de $B$ (stratégie
-pure) sera identifié à l'élément de $S_B$ qui affecte le poids $1$
-à $b$ et $0$ à tout autre élément.
+Donné un ensemble $B$ fini d'« options », on appelle \index{mixte
+  (stratégie)}\defin{stratégie mixte} sur $B$ une fonction $s\colon
+B\to\mathbb{R}$ telle que $s(b)\geq 0$ pour tout $b\in B$ et
+$\sum_{b\in B} s(b) = 1$ : autrement dit, il s'agit d'une distribution
+de probabilités sur $B$.
+
+Le \defin[support (d'une stratégie mixte)]{support} de $s$ est
+l'ensemble des options $b\in B$ pour lesquelles $s(b) > 0$.
+\end{defn}
+
+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
+  $\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$.
 
 En tout état de cause, l'ensemble $S_B$ des stratégies mixtes sur $B$
-sera vu (notamment comme espace topologique) comme le fermé de
-$\mathbb{R}^B$ défini par l'intersection des demi-espaces de
-coordonnées positives et de l'hyperplan défini par la somme des
-coordonnées égale à $1$.
-\end{defn}
+sera vu comme la partie de $\mathbb{R}^B$ définie par l'intersection
+des demi-espaces de coordonnées positives et de l'hyperplan défini par
+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$.
 
 \begin{defn}\label{definition-mixed-strategy-game}
 Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une
 stratégie mixte pour le joueur $i$ est donc une fonction $s\colon A_i
-\to\mathbb{R}$ comme on vient de le dire.  On notera parfois $S_i$
+\to\mathbb{R}$ comme on vient de le dire
+en \ref{definition-mixed-strategy-abst}.  On notera parfois $S_i$
 l'ensemble des stratégies mixtes du joueur $i$.  Un \defin{profil de
   stratégies mixtes} est un élément du produit cartésien $S := S_1
 \times \cdots \times S_N$.
@@ -1131,25 +1226,46 @@ parler de profil de stratégies pures.
 \end{defn}
 
 \thingy\label{remark-mixed-stragy-profile-versus-correlated-profile}
-Il va de soi qu'un profil de stratégies mixtes, i.e., un
-élément de $S := S_1 \times \cdots \times S_N$, i.e., la donnée d'une
-distribution de probabilité sur chaque $A_i$, n'est pas la même chose
-qu'une distribution de probabilités sur $A := A_1 \times \cdots \times
-A_N$.  Néanmoins, on peut voir les profils de stratégies mixtes comme
-des distributions particulières sur $A$, à savoir celles pour
-lesquelles les marginales (i.e., les projections sur un des $A_i$)
-sont indépendantes.  Concrètement, ceci signifie que donné
-$(s_1,\ldots,s_N) \in S$, on en déduit un $s\colon A\to\mathbb{R}$,
-aussi une distribution de probabilité, par la définition suivante :
-$s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ (produit des
-$s_i(a_i)$).  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 n'est pas un problème car $s_i$ se déduit
-de $s$ : précisément, $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$).
-
-\danger (Il faudra prendre garde au fait qu'on peut voir $S$ soit
-comme une partie $S_1\times\cdots\times S_N$ de
+Il va de soi qu'un profil de stratégies mixtes, i.e., un élément de $S
+:= S_1 \times \cdots \times S_N$, i.e., la donnée d'une distribution
+de probabilité sur chaque $A_i$, \emph{n'est pas la même chose} qu'une
+distribution de probabilités sur $A := A_1 \times \cdots \times A_N$.
+
+Néanmoins, si $(s_1,\ldots,s_N) \in S$, on définit une distribution de
+probabilités $s\colon A\to\mathbb{R}$ (un élément de $S_A$, si on
+veut) de la façon suivante :
+\[
+s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)
+\tag{$*$}
+\]
+(produit des $s_i(a_i)$).
+
+Probabilistiquement, cette formule revient à dire qu'on tire un
+élément $a_i$ de $A_i$ selon la distribution $s_i$ \emph{de façon
+  indépendante} pour chaque $i$ de manière à former un $N$-uplet
+$(a_1,\ldots,a_N)$.  La formule ($*$) servira donc à représenter
+l'hypothèse que les joueurs ont accès à des sources de hasard qui sont
+indépendantes (si Alice tire son coup à pile ou face et que Bob fait
+de même, les pièces tirées par Alice et Bob sont des variables
+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{marginales}\footnote{\label{footnote-marginals}La $i$-ième
+  marginale d'une distribution de probabilités $s \colon A \to
+  \mathbb{R}$ est 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
+n'est pas un problème car $s_i$ se déduit de $s$ : précisément,
+$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
 $\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
@@ -1158,7 +1274,8 @@ 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$.)
+\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 :
 
@@ -1171,8 +1288,12 @@ quantité
 \[
 u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a)
 \]
-(ceci définit $u_i$ comme fonction de $S_1\times\cdots \times S_N$
-vers $\mathbb{R}$).
+c'est-à-dire selon la distribution de probabilités définie par la
+formule ($*$)
+de \ref{remark-mixed-stragy-profile-versus-correlated-profile}.  Ceci
+étend $u_i$ en une function de $S := S_1\times\cdots \times S_N$
+vers $\mathbb{R}$, qu'on dénotera par le même symbole car il n'en
+résultera pas de confusion.
 \end{defn}
 
 Selon l'approche qu'on veut avoir, on peut dire qu'on a défini