From ddab94fdd5e11d796ab79e11eb86bb37bbf27b36 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 7 Apr 2021 14:46:56 +0200 Subject: Write answers to first exercise. --- controle-20210412.tex | 108 +++++++++++++++++++++++++++++++++++++++++++++----- 1 file changed, 99 insertions(+), 9 deletions(-) diff --git a/controle-20210412.tex b/controle-20210412.tex index dd3f016..450422f 100644 --- a/controle-20210412.tex +++ b/controle-20210412.tex @@ -134,11 +134,11 @@ choisit la colonne, sont opposés) : \begin{center} \begin{tabular}{r|rrrr} -$\downarrow$Alice, Bob$\rightarrow$&P&Q&R&S\\\hline -P&$0$&$1$&$-1$&$x$\\ -Q&$-1$&$0$&$2$&$-1$\\ -R&$1$&$-2$&$0$&$-1$\\ -S&$-x$&$1$&$1$&$0$\\ +$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline +$\mathrm{P}$&$0$&$1$&$-1$&$x$\\ +$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ +$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ +$\mathrm{S}$&$-x$&$1$&$1$&$0$\\ \end{tabular} \end{center} @@ -148,26 +148,115 @@ toute stratégie (pure donc mixte) de l'adversaire. (0) Quelle est la valeur du jeu dans ce cas ? +\begin{corrige} +On a affaire à un jeu à somme nulle \emph{symétrique} (c'est-à-dire +que sa matrice de gains est antisymétrique), donc la valeur du jeu est +nulle. +\end{corrige} + (1) À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$ (consistant à choisir P avec probabilité $\frac{1}{2}$, et chacun de Q et R avec probabilité $\frac{1}{4}$) est-elle optimale ? -(2) À quelle condition sur $x$ la stratégie $\frac{1}{x+2}\mathrm{P} + -\frac{x}{x+2}\mathrm{R} + \frac{1}{x+2}\mathrm{S}$ (consistant à +\begin{corrige} +Ajoutons à la matrice des gains du jeu une ligne correspondant à la +stratégie considérée : +\begin{center} +\begin{tabular}{r|rrrr} +$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline +$\mathrm{P}$&$0$&$1$&$-1$&$x$\\ +$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ +$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ +$\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline +\hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$& +$0$&$0$&$0$&$\frac{x-1}{2}$\\ +\end{tabular} +\end{center} +Pour qu'elle réalise un gain au moins égal à la valeur du jeu, +c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de +l'adversaire, il faut et il suffit donc que $\frac{x-1}{2} \geq 0$, +c'est-à-dire $x\geq 1$. +\end{corrige} + +(2) À quelle condition sur $x$ l'expression $\frac{1}{x+2}\,\mathrm{P} + +\frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$ (consistant à choisir R avec probabilité $\frac{x}{x+2}$, et chacun de P et S avec -probabilité $\frac{1}{x+2}$) est-elle optimale ? +probabilité $\frac{1}{x+2}$) définit-elle une stratégie optimale ? + +\begin{corrige} +L'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + +\frac{1}{x+2}\,\mathrm{S}$ définit une stratégie mixte lorsque ses +coefficients sont positifs de somme $1$ : le fait qu'ils soient de +somme $1$ est toujours vrai, et ils sont tous positifs lorsque $x\geq +0$. + +Ajoutons à la matrice des gains du jeu une ligne correspondant à la +stratégie en question : +\begin{center} +\begin{tabular}{r|rrrr} +$\downarrow$Alice, Bob$\rightarrow$&$\mathrm{P}$&$\mathrm{Q}$&$\mathrm{R}$&$\mathrm{S}$\\\hline +$\mathrm{P}$&$0$&$1$&$-1$&$x$\\ +$\mathrm{Q}$&$-1$&$0$&$2$&$-1$\\ +$\mathrm{R}$&$1$&$-2$&$0$&$-1$\\ +$\mathrm{S}$&$-x$&$1$&$1$&$0$\\\hline +\hbox{\vrule height12pt depth5pt width0pt}$\frac{1}{x+2}\,\mathrm{P} + +\frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$& +$0$&$\frac{2(1-x)}{x+2}$&$0$&$0$\\ +\end{tabular} +\end{center} +Pour qu'elle réalise un gain au moins égal à la valeur du jeu, +c'est-à-dire $\geq 0$, contre toute stratégie (pure donc mixte) de +l'adversaire, il faut et il suffit donc que $\frac{2(1-x)}{x+2} \geq +0$, c'est-à-dire $x\leq 1$, donc finalement $0\leq x\leq 1$. +\end{corrige} (3) Donner une stratégie optimale lorsque $x\leq 0$. +\begin{corrige} +Lorsque $x\leq 0$, la stratégie pure $\mathrm{S}$ est optimale +puisqu'elle réalise un gain $\geq 0$ contre toute stratégie (pure donc +mixte) de l'adversaire. +\end{corrige} + (4) Dans chacun des cas $x=0$ et $x=1$, exhiber une infinité de stratégies optimales distinctes. +\begin{corrige} +Lorsque $x = 0$, on a trouvé deux stratégies optimales, à savoir +$\frac{1}{2}\mathrm{P} + \frac{1}{2}\mathrm{S}$ (trouvée en (2)) et +$\mathrm{S}$ (trouvée en (3)). Toute combinaison convexe de ces deux +stratégies optimales est donc encore optimale, c'est-à-dire +$\frac{t}{2}\,\mathrm{P} + \frac{2-t}{2}\,\mathrm{S}$ +pour $t\in[0;1]$. + +Lorsque $x = 1$, on a trouvé deux stratégies optimales, à savoir +$\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + +\frac{1}{4}\mathrm{R}$ (trouvée en (1)) et $\frac{1}{3}\mathrm{P} + +\frac{1}{3}\mathrm{R} + \frac{1}{3}\mathrm{S}$ (trouvée en (2)). +Toute combinaison convexe de ces deux stratégies optimales est donc +encore optimale, c'est-à-dire $\frac{2+t}{6}\,\mathrm{P} + +\frac{t}{4}\,\mathrm{Q} + \frac{4-t}{12}\,\mathrm{R} + +\frac{1-t}{3}\,\mathrm{S}$ pour $t\in[0;1]$. +\end{corrige} + (5) En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au hasard} selon une loi uniforme entre $0$ et $1$ une fois que les joueurs ont joué (autrement dit, si un joueur choisit P et l'autre S, le joueur qui a choisi P reçoit un gain aléatoire uniforme entre -$0$ et $1$), quelle stratégie adopteriez-vous dans ce jeu ? +$0$ et $1$ ; cet aléa est, évidemment, indépendant de tous ceux que +les joueurs auraient pu utiliser dans la détermination de leur propre +stratégie !), quelle stratégie adopteriez-vous dans ce jeu ? + +\begin{corrige} +On cherche à maximiser le gain \emph{espéré} minimal contre toute +stratégie de l'adversaire ; mais comme $x$ est indépendant des choix +qu'ont pu faire les joueurs, on peut le remplacer par son espérance, +c'est-à-dire que le jeu considéré revient à prendre $x = \frac{1}{2}$. +D'après la question (2), une stratégie optimale est donnée par +$\frac{2}{5}\mathrm{P} + \frac{1}{5}\mathrm{R} + +\frac{2}{5}\,\mathrm{S}$. +\end{corrige} % @@ -185,6 +274,7 @@ sont $<\varepsilon_1$. Les parties de cet exercice sont indépendantes \underline{Première partie.} +\nobreak On définit une fonction $\varphi$ des ordinaux vers les ordinaux par $\varphi(\alpha) = \omega^\alpha$. On rappelle que $\varphi$ est \emph{strictement croissante} (c'est-à-dire que si $\alpha < \beta$ -- cgit v1.2.3