diff options
| -rw-r--r-- | notes-mitro206.tex | 233 |
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 |