Full determination of Nash equilibria in the simple game of an exercise.upload-20160407

1 files changed, 136 insertions, 38 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index dfc3ad0..b54d3a1 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -5305,11 +5305,11 @@ problème de programmation linéaire suivant :
 \left\{
 \begin{aligned}
 \text{maximiser\ }v&\text{\ avec}\\
-x_U \geq 0\;, \;\; x_V \geq 0\;, \;\; x_W \geq 0&\\
-x_U + x_V + x_W &= 1\\
-v - 6x_U - 0x_V - 2x_W &\leq 0\;\;\text{(X)}\\
-v - 0x_U - 6x_V - 2x_W &\leq 0\;\;\text{(Y)}\\
-v - 4x_U - 4x_V - 7x_W &\leq 0\;\;\text{(Z)}\\
+p_U \geq 0\;, \;\; p_V \geq 0\;, \;\; p_W \geq 0&\\
+p_U + p_V + p_W &= 1\\
+v - 6p_U - 0p_V - 2p_W &\leq 0\;\;\text{(X)}\\
+v - 0p_U - 6p_V - 2p_W &\leq 0\;\;\text{(Y)}\\
+v - 4p_U - 4p_V - 7p_W &\leq 0\;\;\text{(Z)}\\
 \end{aligned}
 \right.
 \]
@@ -5318,8 +5318,8 @@ $v_+,v_- \geq 0$, mais on gagne un petit peu en remarquant que $v$
 sera forcément positif puisque tous les gains du tableau le sont, donc
 on peut ajouter la contrainte $v \geq 0$.  Une application de
 l'algorithme du simplexe donne finalement l'optimum $v = 3$ atteint
-pour $x_U = \frac{1}{2}$ et $x_V = \frac{1}{2}$ et $x_W = 0$, avec
-pour le dual $y_X = \frac{1}{2}$ et $y_Y = \frac{1}{2}$ et $y_Z = 0$
+pour $p_U = \frac{1}{2}$ et $p_V = \frac{1}{2}$ et $p_W = 0$, avec
+pour le dual $q_X = \frac{1}{2}$ et $q_Y = \frac{1}{2}$ et $q_Z = 0$
 (les inégalités (X) et (Y) sont saturées et (Z) ne l'est pas).
 
 Autrement dit, Alice joue les options U et V de façon équiprobable,
@@ -5332,39 +5332,137 @@ forme normale considéré ici.
 
 (5) On suppose maintenant que Bob cherche à \emph{maximiser} le gain
 d'Alice (i.e., il n'est plus son adversaire comme dans les questions
-(1), (2) et (4), mais son allié).  Quels sont les équilibres de Nash
-possibles (on commencera par en chercher en stratégies pures, puis on
-discutera selon les supports possibles des stratégies) ?  Quel est le
-gain (espéré) d'Alice dans chacun ?
+(1), (2) et (4), mais son allié).  On cherche à déterminer quels sont
+les équilibres de Nash possibles.  On notera $(p_U,p_V,p_W,
+q_X,q_Y,q_Z)$ un profil de stratégies mixtes général, où $p_U,p_V,p_W$
+(positifs de somme $1$) sont les poids des trois options d'Alice
+(=probabilités qu'elle les joue), et $q_X,q_Y,q_Z$ (positifs,
+également de somme $1$) les poids des trois options de Bob.  On va
+discuter selon le support des stratégies (i.e., selon les ensembles
+d'options qui ont un poids strictement positif).\spaceout (a) Pour
+commencer, quelles sont les équilibres de Nash évidents en stratégies
+pures ?  Expliquer pourquoi ce sont bien les seuls équilibres de Nash
+où l'un des deux joueurs a une stratégie pure.\spaceout (b) Rappeler
+pourquoi dans un équilibre de Nash où $q_X > 0$ et $q_Y > 0$ (i.e.,
+les options X et Y sont dans le support), on a $6 p_U + 2 p_W = 6 p_V
++ 2 p_W$ (les stratégies pures X et Y de Bob sont forcément
+indifférentes compte tenu de la stratégie d'Alice), et comment on
+obtient des égalités de ce genre pour toute autre hypothèse sur le
+support.\spaceout (c) Montrer que l'hypothèse $q_X,q_Y,q_Z > 0$
+(toutes les options de Bob sont dans le support) conduit à une valeur
+impossible pour $p_U,p_V,p_W$, et en déduire qu'aucun équilibre de
+Nash n'a les trois options de Bob dans le support.  Montrer ensuite
+qu'aucun équilibre de Nash n'a les trois options d'Alice dans le
+support (procéder de même et se ramener à ce qu'on vient de
+montrer).\spaceout (d) Trouver les équilibres de Nash avec
+$q_X,q_Y>0$, en étudiant chacun des cas $p_U=0$, $p_V=0$ et
+$p_W=0$.\spaceout (e) Trouver les équilibres de Nash avec $q_X,q_Z>0$,
+en étudiant chacun des cas $p_U=0$, $p_V=0$ et $p_W=0$.\spaceout
+(f) Conclure quant à l'ensemble des équilibres de Nash du jeu
+considéré.
 
 \begin{corrige}
-Trois équilibres de Nash sont évidents : si Alice joue (purement) U et
-Bob joue (purement) X, aucun n'a intérêt à changer puisque $6$ est
-maximum sur la ligne et sur la colonne ; si Alice joue (purement) V et
-Bob joue (purement) Y, aucun n'a intérêt à changer puisque $6$ est
-maximum sur la ligne et sur la colonne ; et si Alice joue (purement) W
-et Bob joue (purement) Z, aucun n'a intérêt à changer puisque $7$ est
-maximum sur la ligne et sur la colonne.  Les gains d'Alice (et de Bob)
-dans chacun de ces trois cas sont donc $6$, $6$ et $7$ respectivement.
-
-Cherchons maintenant d'autres équilibre de Nash.  Supposons qu'Alice
-joue une combinaison convexe de U, V et W, disons avec poids
-(=probabilités) $p_U, p_V, p_W$ respectivement, et de même Bob une
-combinaison de X, Y et Z avec poids $q_X, q_Y, q_Z$ respectivement.
-Si la stratégie $x$ d'Alice est pure (i.e., un des $p_i$ est
-strictement positif, les autres valent $0$), celle de Bob l'est aussi
-car il est évident que chaque option d'Alice admet une unique
-meilleure réponse de Bob (un nombre est strictement le plus grand dans
-chaque ligne) ; et de même, si la stratégie de Bob est pure, celle
-d'Alice l'est aussi.  Si $q_X$ et $q_Y$ sont tous les deux strictement
-positifs, c'est forcément que les réponses X et Y de Bob donnent le
-même gain espéré (car si l'une était strictement meilleure que
-l'autre, Bob choisirait purement celle-là) : c'est-à-dire $6 p_U + 2
-p_W = 6 p_V + 2 p_W$ ; de même, si $q_X$ et $q_Z$ sont tous les deux
-strictement positifs, on a $6 p_U + 2 p_W = 4 p_U + 4 p_V + 2 p_W$, et
-ainsi de suite.
-
-\textcolor{red}{(À finir)}
+(a) Trois équilibres de Nash sont évidents : si Alice joue
+  (purement) U et Bob joue (purement) X, aucun n'a intérêt à changer
+  puisque $6$ est maximum sur la ligne et sur la colonne ; si Alice
+  joue (purement) V et Bob joue (purement) Y, aucun n'a intérêt à
+  changer puisque $6$ est maximum sur la ligne et sur la colonne ; et
+  si Alice joue (purement) W et Bob joue (purement) Z, aucun n'a
+  intérêt à changer puisque $7$ est maximum sur la ligne et sur la
+  colonne.  Les gains d'Alice (et de Bob) dans chacun de ces trois cas
+  sont donc $6$, $6$ et $7$ respectivement.
+
+Il s'agit là de l'ensemble des équilibres de Nash où l'un des deux
+joueurs a une stratégie pure : par exemple, si Alice joue purement U,
+Bob ne peut que répondre par purement X puisque le gain $6$ est
+strictement plus grand que tout autre gain sur la ligne (i.e., donner
+un poids non nul à une autre option de Bob ne pourrait que diminuer le
+gain).
+
+(b) Si $q_X > 0$ et $q_Y > 0$, les stratégies pures X et Y de Bob
+donnent forcément le même gain, car si l'une d'elle donnait un gain
+strictement supérieure à l'autre, Bob aurait intérêt à augmenter le
+poids $q$ correspondant et améliorerait ainsi strictement sa réponse.
+Autrement dit, l'espérance de gain contre la stratégie pure X,
+c'est-à-dire $6 p_U + 2 p_W$, est égale à l'espérance de gain contre
+la stratégie pure Y, soit $6 p_V + 2 p_W$.  De même, si $q_X > 0$ et
+$q_Z > 0$, on a $6 p_U + 2 p_W = 4 p_U + 4 p_V + 7 p_W$, et ainsi de
+suite.  Ceci vaut aussi dans l'autre sens : si $p_U > 0$ et $p_V > 0$
+alors $6 q_X + 4 q_Z = 6 q_Y + 4 q_Z$ par exemple (les stratégies
+pures U et V d'Alice sont indifférentes).
+
+(c) Si $q_X,q_Y,q_Z > 0$, d'après ce qu'on vient de dire en (b), on a
+$6 p_U + 2 p_W = 6 p_V + 2 p_W = 4 p_U + 4 p_V + 7 p_W$, et comme
+aussi $p_U + p_V + p_W = 1$ on trouve $(p_U, p_V, p_W) = (\frac{5}{8},
+\frac{5}{8}, -\frac{1}{4})$ en résolvant le système.  Une de ces
+valeurs est strictement négative, donc un tel équilibre de Nash n'est
+pas possible.  Bref, ceci montre que tout équilibre de Nash omet
+forcément une des options X, Y ou Z de Bob.
+
+De même, si $p_U,p_V,p_W > 0$, d'après ce qu'on a dit en (b), on a $6
+q_X + 4 q_Z = 6 q_Y + 4 q_Z = 2 q_X + 2 q_Y + 7 q_Z$, ce qui avec $q_X
++ q_Y + q_Z = 1$ se résout en $(q_X, q_Y, q_Z) = (\frac{3}{8},
+\frac{3}{8}, \frac{1}{4})$.  Ces valeurs sont \textit{a priori}
+possibles, mais comme on a montré ci-dessus que $q_X,q_Y,q_Z$ ne
+peuvent pas être simultanément strictemnet positifs, cette possibilité
+est exclue.  Bref, ceci montre que tout équilibre de Nash omet
+forcément une des options U, V ou W d'Alice.
+
+(d) Si $q_X,q_Y > 0$, on a $6 p_U + 2 p_W = 6 p_V + 2 p_W$, et on a
+toujours $p_U + p_V + p_W = 1$.  On résout séparément chacun des
+systèmes obtenu en ajoutant une des équations $p_U = 0$, $p_V = 0$ et
+$p_W = 0$ (on sait qu'on a forcément une de ces égalités en vertu de
+la conclusion de la question (c)).  Pour $p_U = 0$ ou $p_V = 0$ on
+trouve $(p_U, p_V, p_W) = (0,0,1)$, c'est-à-dire une stratégie pure,
+qu'on a déjà traitée.  Pour $p_W = 0$, on trouve $(p_U, p_V, p_W) =
+(\frac{1}{2},\frac{1}{2},0)$, ce qui implique à son tour $(q_X, q_Y,
+q_Z) = (\frac{1}{2},\frac{1}{2},0)$ (en résolvant $6 q_X + 4 q_Z = 6
+q_Y + 4 q_Z$ avec $q_Z = 0$ et $q_X + q_Y + q_Z = 1$), or ceci n'est
+pas un équilibre de Nash car le gain espéré est $3$ (pour Alice comme
+pour Bob, bien sûr) et Bob fera mieux en répondant Z (pour un gain
+espéré de $4$).
+
+(e) Si $q_X,q_Z > 0$, on a $6 p_U + 2 p_W = 4 p_U + 4 p_V + 7 p_W$, et
+on a toujours $p_U + p_V + p_W = 1$.  On résout séparément chacun des
+systèmes obtenu en ajoutant une des équations $p_U = 0$, $p_V = 0$ et
+$p_W = 0$ (on sait qu'on a forcément une de ces égalités en vertu de
+la conclusion de la question (c)).  Pour $p_U = 0$, on trouve une
+solution impossible (un des poids est strictement négatif).  Pour $p_W
+= 0$, on trouve $(p_U, p_V, p_W) = (\frac{2}{3},\frac{1}{3},0)$, ce
+qui implique à son tour $(q_X, q_Y, q_Z) = (0,0,1)$, c'est-à-dire une
+stratégie pure, qu'on a déjà traitée.  Reste $p_V = 0$ : on trouve
+alors $(p_U, p_V, p_W) = (\frac{5}{7},0,\frac{2}{7})$, ce qui implique
+à son tour $(q_X, q_Y, q_Z) = (\frac{3}{7},0,\frac{4}{7})$, donnant un
+gain espéré de $\frac{34}{7}$ ; on vérifie que la stratégie pure V
+d'Alice donne un gain strictement inférieure contre celle
+$(\frac{3}{7},0,\frac{4}{7})$ de Bob (à savoir, $\frac{16}{7}$) et que
+la stratégie pure Y de Bob donne un gain strictement inférieur contre
+celle $(\frac{5}{7},0,\frac{2}{7})$ d'Alice (en l'occurrence,
+$\frac{4}{7}$), donc aucun des joueurs n'a intérêt à changer
+unilatéralement sa stratégie (les deux options du support sont
+indifférentes, et la troisième diminue strictement le gain).  Bref, on
+a bien trouvé un équilibre de Nash en stratégies mixtes.
+
+Comme le jeu est symétrique par échange simultané des options U et V
+d'Alice et X et Y de Bob, on a aussi traité le cas $q_Y,q_Z > 0$.
+Bref, on a traité les six possibilités de support de la stratégie de
+Bob (les stratégies pures en (a), celles ayant les trois options dans
+le support en (c), et celles ayant deux options dans le support en
+(d) et (e)).
+
+(f) Les cinq équilibres de Nash trouvés sont récapitulés par le
+tableau (triés par ordre de gain espéré décroissant) :
+\begin{center}
+\begin{tabular}{ccc|ccc|c}
+$p_U$&$p_V$&$p_W$&$q_X$&$q_Y$&$q_Z$&gain\\\hline
+$0$&$0$&$1$&$0$&$0$&$1$&$7\phantom{\strut+\frac{0}{1}}$\\
+$1$&$0$&$0$&$1$&$0$&$0$&$6\phantom{\strut+\frac{0}{1}}$\\
+$0$&$1$&$0$&$0$&$1$&$0$&$6\phantom{\strut+\frac{0}{1}}$\\
+$\frac{5}{7}$&$0$&$\frac{2}{7}$&$\frac{3}{7}$&$0$&$\frac{4}{7}$&$4+\frac{6}{7}$\\
+$0$&$\frac{5}{7}$&$\frac{2}{7}$&$0$&$\frac{3}{7}$&$\frac{4}{7}$&$4+\frac{6}{7}$\\
+\end{tabular}
+\end{center}
+et on a prouvé que c'étaient bien les seuls.
 \end{corrige}
 
 \subsection{Jeux de Gale-Stewart et détermination}