diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 904 |
1 files changed, 618 insertions, 286 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index e1f37eb..d5fb37f 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 @@ -1035,9 +1037,19 @@ $\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$). - -Une \index{convexe (combinaison)|see{combinaison +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'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 +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,88 @@ 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} +Reprenant 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), soit $M := \max_{a \in A} +u$ (dont on vient de voir que c'est aussi $\max_{s\in C} u$) : alors +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$, si et seulement si 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} +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$. +\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 +1170,51 @@ 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 +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}$ (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 (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$ (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 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,55 +1230,86 @@ 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{distributions + 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 +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 +\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$-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 : -\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) \] -(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 -$u_i(s)$ comme l'espérance de $u_i(a)$ si chaque $a_j$ est tiré 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$. +$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$ +(« multi-affine »). @@ -1188,26 +1318,37 @@ 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 +stratégies mixtes de l'ensemble des joueurs dans lequel \emph{aucun + joueur n'a intérêt à changer unilatéralement sa stratégie} (au sens +où faire un tel changement lui apporterait une espérance de gain +strictement supérieure). Un équilibre de Nash \emph{strict} +correspond à la situation où tout changement unilatéral de stratégie +d'un joueur lui apporterait une espérance de gain strictement +inférieure. + \begin{prop}\label{stupid-remark-best-mixed-strategies} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si @@ -1223,28 +1364,58 @@ En particulier, une meilleure réponse stricte est nécessairement une stratégie pure. \end{prop} \begin{proof} -Tout ceci résulte du fait que le gain espéré $u_i(s_?,t)$ est une -fonction affine de $t \in S_i$ (et une fonction affine sur un simplexe -prend son maximum — ou son minimum — sur un des sommets de ce -simplexe, et ne peut le prendre à l'intérieur que si elle prend aussi -cette valeur sur les sommets). - -Plus précisément : $u_i(s_?,t)$ (pour $t \in S_i$) est combinaison -convexe avec pour coefficients $t(a)$ pour $a\in A_i$, des -$u_i(s_?,a)$. Si $v$ est le maximum des $u_i(s_?,a)$ (qui sont en -nombre fini donc ce maximum existe), alors $v$ est aussi le maximum de -toute combinaison convexe $u_i(s_?,t)$ des $u_i(s_?,a)$ : c'est-à-dire -que $t\in S_i$ est une meilleure réponse possible contre $s_?$ si et -seulement si $u_i(s_?,t) = v$. En particulier, tout $a \in A_i$ qui -réalise ce maximum $v$ est une meilleure réponse possible -(contre $s_?$) qui est une stratégie pure. D'autre part, une -combinaison convexe $u_i(s_?,t)$ de valeurs $\leq v$ ne peut être -égale à $v$ que si toutes les valeurs $u_i(s_?,a)$ entrant -effectivement (c'est-à-dire avec un coefficient $>0$) dans la -combinaison sont égales à $v$ (s'il y en avait une $<v$, elle -entraînerait forcément une moyenne pondérée $<v$), et réciproquement. +Tout ceci résulte essentiellement des propositions +\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-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-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 +être tenté d'en conclure, mais ce serait une erreur, que les +stratégies mixtes n'apportent donc rien à l'histoire, et qu'un +équilibre de Nash existe forcément en stratégies pures : \emph{ce + n'est pas le cas}. Néanmoins, les équilibres de Nash existent bien +en stratégies mixtes, et c'est le résultat central du domaine (ayant +essentiellement valu à son auteur le prix d'économie de la banque de +Suède à la mémoire d'Alfred Nobel en 1994) : + \begin{thm}[John Nash, 1951]\label{theorem-nash-equilibria} Pour un jeu en forme normale comme en \ref{definition-game-in-normal-form}, il existe un équilibre de @@ -1265,7 +1436,7 @@ profil $s$ de stratégies, on peut définir continûment un nouveau 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 +la fonction $T \colon s \mapsto s^\sharp$ doit avoir un point fixe, ce point fixe sera un équilibre de Nash. \begin{proof}[Démonstration de \ref{theorem-nash-equilibria}] @@ -1304,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. @@ -1340,17 +1512,18 @@ Pour $N=2$, une méthode qui peut fonctionner dans des cas suffisamment petits consiste à énumérer tous les supports (cf. \ref{definition-mixed-strategy-abst}) possibles des stratégies mixtes des joueurs dans un équilibre de Nash, c'est-à-dire toutes les -$(2^{\#A_1}-1)\times(2^{\#A_2}-1)$ données de parties non vides de -$A_1$ et $A_2$, et, pour chacune, appliquer le raisonnement suivant : -si $s_i$ est une meilleure réponse possible pour le joueur $i$ (contre -la stratégie $s_{?i}$ de l'autre joueur) alors \emph{toutes les - options du support de $s_i$ ont la même espérance de gain} -(contre $s_{?i}$ ; cf. \ref{stupid-remark-best-mixed-strategies}), ce -qui fournit un jeu d'égalités linéaires sur les valeurs de $s_{?i}$. -En rassemblant ces inégalités (ainsi que celles qui affirment que la -somme des valeurs de $s_i$ et de $s_{?i}$ valent $1$), on arrive -« normalement » à trouver tous les équilibres de Nash possibles : voir -les exercices +$(2^{\#A_1}-1)\penalty0\times\penalty0(2^{\#A_2}-1)$ données de +parties non vides de $A_1$ et $A_2$, et, pour chacune, appliquer le +raisonnement suivant : si $s_i$ est une meilleure réponse possible +pour le joueur $i$ (contre la stratégie $s_{?i}$ de l'autre joueur) +alors \emph{toutes les options du support de $s_i$ ont la même + espérance de gain} (contre $s_{?i}$ ; +cf. \ref{stupid-remark-best-mixed-strategies}), ce qui fournit un jeu +d'égalités linéaires sur les valeurs de $s_{?i}$. En rassemblant ces +inégalités (ainsi que celles qui affirment que la somme des valeurs de +$s_i$ et de $s_{?i}$ valent $1$), on arrive « normalement » à trouver +tous les équilibres de Nash possibles : voir \ref{dove-or-hawk} +ci-dessous, ainsi que les exercices \ref{normal-form-game-exercise-two-by-two} et \ref{normal-form-game-exercise-three-by-three} (dernières questions) pour des exemples. @@ -1360,6 +1533,67 @@ algorithmiquement possible en théorie en vertu d'un théorème de Tarski et Seidenberg sur la décidabilité des systèmes d'équations algébriques réels, mais possiblement inextricable dans la pratique.) +\thingy\label{dove-or-hawk-redux} Pour donner un exemple, revenons sur +le \index{trouillard (jeu du)}jeu du trouillard défini +en \ref{dove-or-hawk} et dressons un tableau de l'espérance de gain +pour quelques stratégies mixtes ainsi que la stratégie mixte +« générique » : + +{\footnotesize +\begin{center} +\begin{tabular}{r|c|c|c|c|c|} +$\downarrow$Alice, Bob$\rightarrow$&Colombe&Faucon&$\frac{2}{3}C+\frac{1}{3}F$&$\frac{1}{2}C+\frac{1}{2}F$&$qC+(1-q)F$\\\hline +Colombe&$2,2$&\textcolor{blue}{$0,4$}&$\frac{4}{3},\frac{8}{3}$&$1,3$&{\tiny $2q, 4-2q$}\\\hline +Faucon&\textcolor{blue}{$4,0$}&$-4,-4$&$\frac{4}{3},-\frac{4}{3}$&$0,-2$&{\tiny $-4+8q, -4+4q$}\\\hline +$\frac{2}{3}C+\frac{1}{3}F$&$\frac{8}{3},\frac{4}{3}$&$-\frac{4}{3},\frac{4}{3}$&\textcolor{blue}{$\frac{4}{3},\frac{4}{3}$}&$\frac{2}{3},\frac{4}{3}$&{\tiny $-\frac{4}{3}+4q, \frac{4}{3}$}\\\hline +$\frac{1}{2}C+\frac{1}{2}F$&$3,1$&$-2,0$&$\frac{4}{3},\frac{2}{3}$&$\frac{1}{2},\frac{1}{2}$&$-2+5q,q$\\\hline +$pC+(1-p)F$&{\tiny $4-2p,2p$}&{\tiny $-4+2p,-4+8p$}&{\tiny $\frac{4}{3},-\frac{4}{3}+4p$}&{\tiny $p,-2+5p$}&$(\dagger)$\\\hline +\end{tabular} +\end{center} +\par\noindent +où $(\dagger) = (-4 + 4p + 8q - 6pq, - 4 + 8p + 4q - 6pq)$. +\par} + +\smallskip + +Les trois profils $(C,F)$ (i.e., Alice joue Colombe et Bob joue +Faucon), $(F,C)$ et $(\frac{2}{3}C+\frac{1}{3}F, +\frac{2}{3}C+\frac{1}{3}F)$ sont des équilibres de Nash : cela résulte +du fait que, quand on regarde la case correspondante du tableau, le +premier nombre est maximum sur la colonne (c'est-à-dire qu'Alice n'a +pas intérêt à changer unilatéralement sa stratégie) et le second est +maximum sur la ligne (c'est-à-dire que Bob n'a pas intérêt à changer +unilatéralement sa stratégie) : chacun de ces maxima peut se tester +simplement contre les stratégies pures de l'adversaire (i.e., les deux +premières lignes ou colonnes). Pour trouver ces équilibres et +vérifier qu'il n'y en a pas d'autre, on peut : +\begin{itemize} +\item commencer par rechercher les équilibres de Nash où chacun des + deux joueurs joue une stratégie pure (ceci revient à regarder + chacune des quatre cases du tableau initial et chercher si le + premier nombre est maximal sur la colonne et le second maximal sur + la ligne) ; +\item considérer la possibilité d'un équilibre de Nash où l'un des + joueurs joue une stratégie pure et l'autre une stratégie mixte + supportée par les deux options : si par exemple Alice joue + $pC+(1-p)F$ avec $p>0$ et Bob joue $a \in \{C,F\}$, + 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 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 + $0<q<1$ : d'après \ref{stupid-remark-best-mixed-strategies} le gain + espéré d'Alice doit être le même contre $qC+(1-q)F$ indifféremment + qu'elle joue Colombe ou Faucon, ce qui implique $2q = -4+8q$ donc + $q=\frac{2}{3}$, et symétriquement, le gain espéré de Bob doit être + le même contre $pC+(1-p)F$ indifféremment qu'il joue Colombe ou + Faucon, ce qui implique $2p = -4+8p$ donc $p=\frac{2}{3}$, si bien + que le seul équilibre de Nash de cette nature est celui qu'on a + décrit (et il faut vérifier qu'il en est bien un). +\end{itemize} + \thingy Mentionnons en complément une notion plus générale que celle d'équilibre de Nash : si $s\colon A \to \mathbb{R}$ (où $A := A_1\times\cdots\times A_N$) est cette fois une distribution de @@ -1418,179 +1652,270 @@ 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) \] +(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 +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, 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 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 +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. + +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} -\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 @@ -1609,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 @@ -1619,7 +1947,7 @@ devient de maximiser $v_+ - v_-$ sous les contraintes \[-\sum_{a\in A_1} x_a \leq -1\] \[(\forall b\in A_2)\;v_+ - v_- - \sum_{a \in A_1} u(a,b)\, x_a \leq 0\] Le problème dual (minimiser ${^{\mathrm{t}}\textbf{q}} y$ sous les -contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{q}}$ +contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{p}}$ et $y\geq 0$) est alors de minimiser $w_+ - w_-$ sous les contraintes \[w_+\geq 0,\; w_- \geq 0,\;\; (\forall b\in A_2)\;y_b \geq 0\] \[\sum_{b\in A_2} y_b \geq 1\] @@ -4037,6 +4365,10 @@ y$ pour $y\geq x$ et $x<y$ pour $y>x$. Un ensemble partiellement ordonné est dit \defin[totalement ordonné (ensemble)]{totalement ordonné} lorsque pour tous $x\neq y$ on a soit $x>y$ soit $y>x$. +%% TODO: éclaircir le fait que dans ce qui suit, « bien-fondé » se +%% comprend pour le graphe reliant $x$ à $y$ ssi $x>y$ (voir aussi la +%% précédente occurrence du terme « bien-ordonné »). + Un ensemble totalement ordonné bien-fondé $W$ est dit \defin[bien-ordonné (ensemble)]{bien-ordonné}. D'après \ref{well-founded-induction}, ceci peut se reformuler de différentes façons : @@ -5053,7 +5385,7 @@ Soit $\alpha$ un ordinal. On appelle alors \defin{nimbre} associé l'ensemble $\alpha+1$), \item la relation d'arête (définissant le graphe) est $>$, c'est-à-dire que les voisins sortants de $\beta\leq\alpha$ sont les - ordinaux $\beta'<\alpha$, et + ordinaux $\beta'<\beta$, et \item la position initiale est $\alpha$. \end{itemize} Autrement dit, il s'agit du jeu où, partant de l'ordinal $\beta = @@ -5220,7 +5552,7 @@ L'ordinal $0$ est neutre pour $\oplus$. Par induction sur $\alpha$, on prouve $\alpha \oplus 0 = \alpha$ : en effet, $\alpha \oplus 0 = \mex \{\beta\oplus 0: \beta<\alpha\}$, et par hypothèse d'induction ceci vaut $\mex \{\beta: \beta<\alpha\} = -\mex \alpha = \alpha$. +\alpha$. \end{proof} \begin{proof}[Seconde démonstration] Cela résulte de l'observation que $\alpha\oplus 0 = \gr(*\alpha_1 @@ -5242,7 +5574,7 @@ ensemble contenant $\alpha_1\oplus\alpha_2'$, donc il ne peut pas lui \begin{thm}\label{nim-sum-for-games-versus-ordinals} Si $G_1,G_2$ sont deux jeux combinatoires impartiaux bien-fondés ayant valeurs de Grundy respectivement $\alpha_1,\alpha_2$, alors la valeur -de Grundy de $G_1\oplus G_2$ est $\alpha_2\oplus\alpha_2$. +de Grundy de $G_1\oplus G_2$ est $\alpha_1\oplus\alpha_2$. \end{thm} \begin{proof} On procède par induction bien-fondée sur les positions de $G_1\oplus @@ -5943,7 +6275,7 @@ est le jeu combinatoire partisan bien-fondé dont \alpha$, \item la relation d'arête (définissant le graphe) est $>$, c'est-à-dire que les voisins sortants de $\beta\leq\alpha$ sont les - ordinaux $\beta'<\alpha$, + ordinaux $\beta'<\beta$, \item l'arête $(\beta,\beta')$ est colorée en bleu si $\sigma(\beta') = +$ et en rouge si $\sigma(\beta') = -$, et \item la position initiale est $\alpha$. @@ -6969,20 +7301,20 @@ jeu où les coups de Bob sont purement et simplement ignorés). \smallbreak (7) Soit $u \colon \{0,1\}^{\mathbb{N}} \to \mathbb{R}$ qui à -$(x_0,x_1,x_2,\ldots)$ associe $\sum_{i=0} x_i 2^{-i}$ (le nombre réel +$(x_0,x_1,x_2,\ldots)$ associe $\sum_{i=0} x_i 2^{-i-1}$ (le nombre réel dont la représentation binaire est donnée par $0$ virgule la suite des $x_i$). Vérifier que $u$ est continue et calculer la valeur du jeu qu'elle définit (quelle est la stratégie optimale pour Alice et pour Bob ?). \begin{corrige} -La fonction $u$ est continue car si $\varepsilon < 2^{-\ell-1}$ +La fonction $u$ est continue car si $\varepsilon < 2^{-\ell}$ alors la valeur $u(\dblunderline{x})$ est définie à $\varepsilon$ près par la donnée des $\ell$ premiers termes de la suite $\dblunderline{x}$. Il est évident qu'Alice a intérêt à ne jouer que des $1$ (jouer autre chose ne ferait que diminuer son gain) et Bob que des $0$. La valeur du jeu est donc $u(0,1,0,1,0,1,\ldots) = - \frac{1}{2}$. + \frac{1}{3}$. \end{corrige} |