diff options
| -rw-r--r-- | notes-mitro206.tex | 173 |
1 files changed, 141 insertions, 32 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 1c9edcf..132c476 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -433,50 +433,69 @@ a priori de faire forcément ce choix-là. Cette différence vient du 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} +\begin{defn}\label{definition-mixed-strategy-abst} Donné un ensemble $B$ fini d'« options », on appelle \textbf{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 \textbf{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 barycentrique -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. +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. 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} +\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$ l'ensemble des stratégies mixtes du joueur $i$. Un \textbf{profil de - stratégies mixtes} est un élément du produit cartésien $S_1 \times -\cdots \times S_N$. + stratégies mixtes} est un élément du produit cartésien $S := S_1 +\times \cdots \times S_N$. + +Plus généralement, si $I \subseteq \{1,\ldots,N\}$ est un ensemble de +joueurs, un élément du produit $S_I := \prod_{j\in I} S_j$ s'appellera +un profil de stratégies mixtes pour l'ensemble $I$ de joueurs ; ceci +sera notamment utilisé si $I = \{1,\ldots,N\}\setminus\{i\}$ est +l'ensemble de tous les joueurs sauf le joueur $i$, auquel cas on +notera $S_{?i} := \prod_{j\neq i} S_j$ l'ensemble des profils. +Naturellement, si chaque composante est une stratégie pure, on pourra +parler de profil de stratégies pures. \end{defn} \thingy Il va de soi qu'un profil de stratégies mixtes, i.e., un -élément de $S_1 \times \cdots \times S_N$, i.e., la donnée d'une +é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_1\times \cdots \times S_N$, 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)$). Ceci conduit à faire la définition -suivante : +$(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$). + +Ceci conduit à faire la définition suivante : \begin{defn} Donné un jeu en forme normale comme @@ -494,33 +513,123 @@ vers $\mathbb{R}$). 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$ de -sommets $A_i$ lui-même plongé multilinéairement dans le simplexe de -sommets $A$. +l'unique prolongement de $u_i$ au produit des simplexes $S_i$ qui soit +affine en chaque variable $s_i$. -\begin{defn} +\begin{defn}\label{definition-best-response-and-nash-equilibrium} Donné un jeu en forme normale comme -en \ref{definition-game-in-normal-form}, un profil de stratégies -mixtes $s = (s_1,\ldots,s_N)$ est dit être un \textbf{équilibre de - Nash} (resp., un équilibre de Nash \emph{strict}) lorsque pour tout -$1\leq i \leq N$ et tout $t \in S_i$, on a -\[ -u_i(s_1,\ldots,s_i,\ldots,s_N) \leq -u_i(s_1,\ldots,t,\ldots,s_N) -\] -(resp. $u_i(s_1,\ldots,s_i,\ldots,s_N) < -u_i(s_1,\ldots,t,\ldots,s_N)$), où ici $u_i(s_1,\ldots,t,\ldots,s_N)$ -désigne le gain espéré du joueur $i$ selon le profil de stratégies -mixtes obtenu en remplaçant la $i$-ième coordonnées $s_i$ de $s$ -par $t$ (et en laissant les autres inchangées). +en \ref{definition-game-in-normal-form}, si $1 \ldots 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 \textbf{meilleure + réponse} (resp. la meilleure réponse 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}$. + +Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble +des joueurs) est dit être un \textbf{équilibre de Nash} (resp., un +équilibre de Nash \emph{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$. \end{defn} -\begin{thm} +\begin{prop}\label{stupid-remark-best-mixed-strategies} +Donné un jeu en forme normale comme +en \ref{definition-game-in-normal-form}, si $1 \ldots i \leq N$ et si +$s_?$ est un profil de stratégies mixtes pour tous les joueurs autres +que le joueur $i$, il existe une meilleure réponse pour le joueur $i$ +qui est une stratégie pure. Et même, si $s_!$ (stratégie mixte) est +une meilleure réponse, alors il existe une meilleure réponse qui est +une stratégie pure appartenant au support de $s_!$. + +En particulier, une meilleure réponse stricte est nécessairement une +stratégie pure. +\end{prop} +\begin{proof} +Il suffit de se rappeler que $u_i(s_?,t)$ est une fonction affine +de $t \in S_i$, c'est-à-dire que sa valeur est combinaison convexe, à +coefficients les $t(a)$ pour $a\in S_i$, des $u_i(s_?,a)$. Comme une +combinaison convexe est majorée par la plus grande des valeurs +combinée (ici, des $u_i(s_?,a)$), il est clair que le maximum des +$u_i(s_?,t)$ existe et est égal au maximum des $u_i(s_?,a)$ ; les +autres affirmations sont tout aussi faciles. +\end{proof} + +\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 Nash. \end{thm} +Pour démontrer le théorème en question, on utilise (et on admet) le +théorème du point fixe de Brouwer, qui affirme que si $K$ est un +convexe compact de $\mathbb{R}^m$, et que $f \colon K \to K$ est +continue, alors il existe $x\in K$ tel que $f(x) = x$ (un \emph{point + fixe} de $f$, donc). + +L'idée intuitive de la démonstration suivante est : partant d'un +profil $s$ de stratégies, on peut définir continûment un nouveau +profil $s'$ en donnant plus de poids aux options qui donnent un +meilleur gain au joueur correspondant — si bien que $s'$ sera +différent de $s$ dès que $s'$ n'est pas un équilibre de Nash. Comme +la fonction $f \colon s \to s'$ doit avoir un point fixe, ce point +fixe sera un équilibre de Nash. + +\begin{proof}[Démonstration de \ref{theorem-nash-equilibria}] +Si $s \in S$ et $1\leq i\leq N$, convenons de noter $s_{?i}$ +l'effacement de la composante $s_i$ (c'est-à-dire le profil pour les +joueurs autres que $i$). Si de plus $b \in A_i$, notons +$\varphi_{i,b}(s) = \max\{0, u_i(s_{?i},b) - u_i(s)\}$ l'augmentation +du gain du joueur $i$ si on remplace sa stratégie $s_i$ par la +stratégie pure $b$ en laissant le profil $s_{?i}$ des autres joueurs +inchangé (ou bien $0$ s'il n'y a pas d'augmentation). On remarquera +que $s$ est un équilibre de Nash si et seulement si les +$\varphi_{i,b}(s)$ sont nuls pour tout $1\leq i\leq N$ et tout $b\in +A_i$ (faire appel à la proposition précédente pour le « si »). On +remarquera aussi que chaque $\varphi_{i,b}$ est une fonction continue +sur $S$. + +Définissons maintenant $f\colon S\to S$ de la façon suivante : si $s +\in S$, on pose $f(s) = s'$, où $s' = (s'_1,\ldots,s'_N)$ avec +\[ +\begin{aligned} +s'_i(a) &= \frac{s_i(a) + \varphi_{i,a}(s)}{\sum_{b\in A_i}(s_i(b) + \varphi_{i,b}(s))}\\ +&= \frac{s_i(a) + \varphi_{i,a}(s)}{1 + \sum_{b\in A_i}\varphi_{i,b}(s)} +\end{aligned} +\] +(L'important est que $s'_i$ augmente strictement le poids des options +$a\in A_i$ telles que $u_i(s_{?i},a) > u_i(s)$ ; en fait, on pourrait +composer $\varphi$ à gauche par n'importe quelle fonction $\mathbb{R} +\to \mathbb{R}$ croissante, continue, nulle sur les négatifs et +strictement positive sur les réels strictement positifs, on a choisi +l'identité ci-dessus pour rendre l'expression plus simple à écrire, +mais elle peut donner l'impression qu'on commet une « erreur + d'homogénéité » en ajoutant un gain à une probabilité.) + +D'après la première expression donnée, il est clair qu'on a bien $s'_i +\in S_i$, et qu'on a donc bien défini une fonction $f\colon S\to S$. +Cette fonction est continue, donc admet un point fixe $s$. On va +montrer que $s$ est un équilibre de Nash. + +Si $1\leq i\leq N$, il existe $a \in A_i$ tel que $u_i(s_{?i},a) \leq +u_i(s)$ (car, comme dans la preuve +de \ref{stupid-remark-best-mixed-strategies}, $u_i(s)$ est combinaison +convexe des $u_i(s_{?i},a)$ dont est supérieur au plus petit d'entre +eux) : c'est-à-dire $\varphi_{i,a}(s) = 0$. Pour un tel $a$, la +seconde expression $s'_i(a) = s_i(a) / \big(1 + \sum_{b\in + A_i}\varphi_{i,b}(s)\big)$ montre, en tenant compte du fait que +$s'_i = s_i$ puisque $s$ est un point fixe, que $\sum_{b\in A_i} +\varphi_{i,b}(s) = 0$, donc $\varphi_{i,b}(s) = 0$ pour tout $b$. On +vient de voir que les $\varphi_{i,b}(s)$ sont nuls pour tout $i$ et +tout $b$, et on a expliqué que ceci signifie que $s$ est un équilibre +de Nash. +\end{proof} + % % % |