diff options
| -rw-r--r-- | notes-mitro206.tex | 376 |
1 files changed, 218 insertions, 158 deletions
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 |