From 589989d9cf9c450d18f648a2f298447adf51ad3c Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Thu, 4 Apr 2019 21:02:19 +0200 Subject: Write answers to third exercise. --- controle-20190408.tex | 68 ++++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 62 insertions(+), 6 deletions(-) (limited to 'controle-20190408.tex') diff --git a/controle-20190408.tex b/controle-20190408.tex index 795695c..cef74cc 100644 --- a/controle-20190408.tex +++ b/controle-20190408.tex @@ -625,20 +625,76 @@ nulle a une valeur de $0$ pour les deux joueurs.) matrice de gains dans le cas $n=5$. Pour des raisons de symétrie, quelle est la valeur du jeu ? -(2) Montrer qu'une stratégie mixte optimale consiste à jouer chacune -des options $0$, $n-2$ et $n-1$ avec probabilité $\frac{1}{3}$ (et -jamais les autres). On l'appellera $s_0$. +\begin{corrige} +Il s'agit d'un jeu en forme normale et à somme nulle. Pour $n=5$, la +matrice des gains d'Alice vaut : + +\begin{center} +\begin{tabular}{r|ccccc} +$\downarrow$Alice, Bob$\rightarrow$&$\mathtt{0}$&$\mathtt{1}$&$\mathtt{2}$&$\mathtt{3}$&$\mathtt{4}$\\\hline +$\mathtt{0}$&$0$&$-1$&$-1$&$-1$&$+1$\\ +$\mathtt{1}$&$+1$&$0$&$-1$&$-1$&$-1$\\ +$\mathtt{2}$&$+1$&$+1$&$0$&$-1$&$-1$\\ +$\mathtt{3}$&$+1$&$+1$&$+1$&$0$&$-1$\\ +$\mathtt{4}$&$-1$&$+1$&$+1$&$+1$&$0$\\ +\end{tabular} +\end{center} + +Pour des raisons de symétrie (la matrice étant antisymétrique, +c'est-à-dire que les deux joueurs sont dans la même situation +vis-à-vis du jeu), la valeur du gain vaut $0$. +\end{corrige} + +(2) On considère la stratégie mixte consistant à jouer chacune des +options $0$, $n-2$ et $n-1$ avec probabilité $\frac{1}{3}$ (et jamais +les autres). On l'appellera $s_0$. Si Alice joue selon cette +stratégie $s_0$ et si Bob joue l'option $i$, quel est le gain espéré +d'Alice en fonction de $i$ ? + +\begin{corrige} +Si Bob joue $0$, Alice obtient le gain espéré $\frac{1}{3}(0 + 1 - 1) += 0$. Si Bob joue une option entre $1$ et $n-3$ inclus, Alice obtient +le gain espéré $\frac{1}{3}(-1 + 1 + 1) = \frac{2}{3} > 0$. Si Bob +joue $n-2$, Alice obtient le gain espéré $\frac{1}{3}(-1 + 0 + 1) = +0$. Si Bob joue $n-1$, Alice obtient le gain espéré $\frac{1}{3}(+1 - +1 + 0) = 0$. +\end{corrige} -(3) Si Alice joue selon la stratégie $s_0$ décrite en (2) et si Bob -joue l'option $i$, quel est le gain espéré de Bob en fonction de $i$ ? +(3) Pourquoi $s_0$ est-elle une stratégie optimale ? -(4) Déduire de (3) qu'aucune stratégie optimale ne peut avoir une +\begin{corrige} +Pour vérifier que $s_0$ est optimale, il s'agit de vérifier qu'elle +réalise au moins la valeur du jeu contre toute option (=stratégie +pure) de l'adversaire. C'est ce qu'on vient de faire puisque la +valeur du jeu est $0$. +\end{corrige} + +(4) Déduire de (2) qu'aucune stratégie optimale ne peut avoir une option autre que $0$, $n-2$ ou $n-1$ dans son support. (On pourra faire jouer une telle stratégie contre $s_0$.) +\begin{corrige} +Si $t$ est une stratégie ayant une autre option que $0$, $n-2$ +et $n-1$ dans son support, les espérances trouvées en (2) montrent que +son espérance de gain contre $s_0$ est strictement négative +(strictement positive pour le joueur qui applique $s_0$, donc +strictement négative pour celui qui applique $t$). Donc $t$ ne peut +pas être optimale. +\end{corrige} + (5) Montrer que la stratégie $s_0$ décrite en (2) est la seule stratégie optimale de ce jeu. +\begin{corrige} +On vient de voir que toute stratégie optimale $s$ a un support inclus +dans $\{0, n-2, n-1\}$. Si on appelle $p_0, p_{-2}, p_{-1}$ les +probabilités respectives de ces options dans $s$, on sait que $s$ doit +avoir une espérance de gain nulle contre $s_0$, donc contre chacune +des options pures $0$, $n-2$ et $n-1$, ce qui donne $p_{-2} = p_{-1}$, +$p_{-1} = p_0$ et $p_0 = p_{-2}$, bref, la seule possibilité est +$p_{-2} = p_{-1} = p_0 = \frac{1}{3}$. +\end{corrige} + % % -- cgit v1.2.3