diff options
| -rw-r--r-- | notes-mitro206.tex | 174 |
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} |