Prove the existence of Nash equilibria.

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}
+
 %
 %
 %