diff options
| -rw-r--r-- | controle-20230417.tex | 123 |
1 files changed, 70 insertions, 53 deletions
diff --git a/controle-20230417.tex b/controle-20230417.tex index 34925af..fce95a1 100644 --- a/controle-20230417.tex +++ b/controle-20230417.tex @@ -76,7 +76,7 @@ \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} -\date{13 avril 2022} +\date{17 avril 2023} \maketitle \pretolerance=8000 @@ -90,6 +90,11 @@ Les exercices sont totalement indépendants. Ils pourront être traités dans un ordre quelconque, mais on demande de faire apparaître de façon très visible dans les copies où commence chaque exercice. +La longueur du sujet ne doit pas effrayer : l'énoncé est long parce +que des rappels ont été faits et que la rédaction des questions +cherche à éviter toute ambiguïté. De plus, il ne sera pas nécessaire +de traiter la totalité pour avoir la note maximale. + \medbreak L'usage de tous les documents (notes de cours manuscrites ou @@ -101,7 +106,7 @@ L'usage des appareils électroniques est interdit. Durée : 2h -Barème \emph{indicatif} : \textcolor{red}{XXX}. +Barème \emph{indicatif} : $5+5+5+7$ (sur $20$) \ifcorrige Ce corrigé comporte 8 pages (page de garde incluse). @@ -256,10 +261,10 @@ n_3$ et de façon analogue pour les trois autres. On cherche donc, par exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$. Ceci n'est pas difficile en prenant par exemple pour $n_1$ une puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et -de $n_3$ mais telle qu'en enlevant on obtient des nombres strictement -plus petits. Par exemple, la position $(2,6,7)$ (de valeur de Grundy -$2\oplus 6\oplus 7 = 3 =: g$) admet des coups gagnants vers $(2,5,7)$ -ou $(2,6,4)$ ou même $(1,6,7)$. +de $n_3$ mais telle qu'en l'enlevant on obtienne des nombres +strictement plus petits. Par exemple, la position $(2,6,7)$ (de +valeur de Grundy $2\oplus 6\oplus 7 = 3 =: g$) admet des coups +gagnants vers $(2,5,7)$ ou $(2,6,4)$ ou même $(1,6,7)$. \end{corrige} @@ -374,7 +379,7 @@ fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} - +\vskip-\baselineskip Si on joue à partir du sommet A comme position initiale et que, comme suggéré dans la définition de $\dur$, le joueur perdant cherche à perdre aussi lentement que possible tandis que le joueur gagnant @@ -409,6 +414,7 @@ inversé. On trouve, pour le rang : \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} +\vskip-\baselineskip Pour la valeur de Grundy : @@ -433,6 +439,7 @@ Pour la valeur de Grundy : \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} +\vskip-\baselineskip Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à suivre, on a entouré en double les sommets de valeur de Grundy $0$) : @@ -458,6 +465,7 @@ suivre, on a entouré en double les sommets de valeur de Grundy $0$) : \draw[->] (nE) to[out=0,in=90] (nG); \end{tikzpicture} \end{center} +\vskip-\baselineskip Si on joue à partir de la position A, le premier joueur, appelons-la Alice, est en position perdante car la valeur de Grundy est nulle, et @@ -480,10 +488,10 @@ par hypothèse d'induction (il est clair qu'augmenter au sens large tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens large), et ceci vaut $\rk(x)$ par définition. Dans le cas où $\gr(x) \neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 : -y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \min\,\{\dur(y)+1 : -y\in\outnb(x)\} \leq \sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ de façon -évidente (en notant bien que les $\min$ portent sur des ensembles -non-vides), et pour la même raison que précédemment, ceci est $\leq +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\}$ de façon évidente ($\min S \leq \sup S$ est clair), +et pour la même raison que précédemment, ceci est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$. \end{corrige} @@ -508,9 +516,10 @@ autrement dit, il choisit un élément de $\outnb(x) \cup \{x\}$. (Pour être parfaitement clair : au premier tour, le Fugueur choisit $x_1 \in \outnb(x_0) \cup \{x_0\}$, puis le Borneur choisit $x_2 \in \outnb(x_1) \cup \{x_1\}$, et ainsi de suite.) Le jeu dure infiniment -longtemps (manifestement, chaque joueur permettent toujours de faire -un coup). Au bout d'un nombre infini de coups, on considère la suite -$(x_n)_{n\in\mathbb{N}}$ de toutes les positions traversées : +longtemps (manifestement, les règles permettent toujours à chaque +joueur de faire un coup). Au bout d'un nombre infini de coups, on +considère la suite $(x_n)_{n\in\mathbb{N}}$ de toutes les positions +traversées : \begin{itemize} \item si cette suite est d'image finie (c'est-à-dire que l'ensemble $\{x_n : n\in\mathbb{N}\}$ de toutes les positions traversées est @@ -522,21 +531,21 @@ $(x_n)_{n\in\mathbb{N}}$ de toutes les positions traversées : joueurs a nécessairement une stratégie gagnante (on ne demande pas de préciser lequel). On pourra préalablement montrer que pour toute partie $F \subseteq G$, la partie $F^{\mathbb{N}} \subseteq -G^{\mathbb{N}}$ est \emph{fermée} pour la topologie sur +G^{\mathbb{N}}$ est \emph{fermée} (pour la topologie sur $G^{\mathbb{N}}$ produit de la topologie -discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}, et -en déduire une propriété de $\bigcup_{F\text{~fini~}\subseteq G} -F^{\mathbb{N}}$ (c'est-à-dire la réunion des $F^{\mathbb{N}}$ où $F$ -parcourt toutes les parties \emph{finies} de $G$). +discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}), et +en déduire une propriété de l'ensemble +$\bigcup_{F\text{~fini~}\subseteq G} F^{\mathbb{N}}$ réunion des +$F^{\mathbb{N}}$ où $F$ parcourt toutes les parties \emph{finies} +de $G$. \begin{corrige} Pour commencer, montrons que si $F$ est une partie de $G$ alors $F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée. Ceci revient à montrer que son complémentaire est ouvert, autrement dit, que si $\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, -alors il existe un voisinage fondamental de $\dblunderline{x}$ qui est -inclus dans le complémentaire de $F^{\mathbb{N}}$ (autrement dit, ne -rencontre pas $F^{\mathbb{N}}$). Or si $\dblunderline{x} \in +alors il existe un voisinage fondamental de $\dblunderline{x}$ qui ne +rencontre pas $F^{\mathbb{N}}$. Or si $\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, c'est qu'elle a une valeur $x_\ell$ qui n'est pas dans $F$, et toute suite commençant par $x_0,\ldots,x_\ell$ n'est pas dans $F^{\mathbb{N}}$, c'est-à-dire que @@ -572,9 +581,11 @@ au même, qu'elle appartient à $\bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$. On a donc affaire à un jeu de Gale-Stewart défini par l'ensemble de -suites $A := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien. Le -théorème de détermination borélienne de Martin assure que l'un des -joueurs a forcément une stratégie gagnante. +suites $B := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien (ou +par son complémentaire $A := G^{\mathbb{N}} \setminus B$ si on prend +le point de vue du Fugueur). Le théorème de détermination borélienne +de Martin assure que l'un des joueurs a forcément une stratégie +gagnante. \end{corrige} (2) Indépendamment de la question précédente, donner un exemple de @@ -588,7 +599,7 @@ gagne trivialement (la suite sera la suite constante). Si $G$ est le graphe formé des entiers naturels avec une arête $i \to j$ lorsque $i<j$ (autrement dit des petits entiers naturels vers les -grands), ou même simplement $i \to i+1$, alors le Fugueur a une +grands), ou même seulement $i \to i+1$, alors le Fugueur a une stratégie gagnante consistant à jouer de $i$ vers $i+1$, ce qui assure que la suite $(x_{2i+1})$ des positions choisies par le Fugueur est strictement croissante quoi que fasse le Borneur (il ne peut pas @@ -614,8 +625,11 @@ $W$&$-1,+1$&$+1,-1$&$x,x$\\ \end{tabular} \end{center} où $x$ est un réel et, pour plus de commodité, on a écrit $U$ pour -« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ». Le but de -l'exercice est d'étudier les équilibres de Nash de ce jeu. +« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ». (La ligne +correspond à l'option choisie par Alice, la colonne à l'option de Bob, +et chaque case indique le gain d'Alice suivi du gain de Bob.) + +Le but de l'exercice est d'étudier les équilibres de Nash de ce jeu. (On prendra bien note, pour simplifier les raisonnements en cas, du fait que les options ont une symétrie cyclique\footnote{C'est-à-dire @@ -625,9 +639,9 @@ symétriques.) (1) Considérons le profil de stratégies mixtes dans lequel les deux joueurs choisissent chacun chaque option avec probabilité -$\frac{1}{3}$ (on rappelle que c'est ça la stratégie optimale dans le -cas à somme nulle). Pour quelle(s) valeur(s) de $x$ ce profil est-il -un équilibre de Nash ? +$\frac{1}{3}$ (c'est-à-dire la stratégie qui est optimale dans le cas +à somme nulle). Pour quelle(s) valeur(s) de $x$ ce profil est-il un +équilibre de Nash ? \begin{corrige} Pour des raisons de symétrie, si l'un des joueurs joue cette stratégie @@ -647,9 +661,9 @@ de $x$. \emph{On suppose dorénavant que $x<-1$.} (2) Existe-t-il un équilibre de Nash dans lequel Alice joue purement -$U$ (Pierre) ? (On raisonnera sur le support de la stratégie de Bob -en réponse.) En déduire tous les équilibres de Nash dans lesquels au -moins un joueur joue une stratégie pure. +$U$ ? (On raisonnera les options pouvant être dans le support de la +stratégie de Bob en réponse.) En déduire tous les équilibres de Nash +dans lesquels au moins un joueur joue une stratégie pure. \begin{corrige} Si Alice joue purement $U$, les gains de Bob pour les différentes @@ -659,18 +673,19 @@ seule option qui peut faire partie du support d'une meilleure réponse de Bob est $V$, autrement dit, si Alice joue purement $U$ dans un équilibre de Nash, Bob répond forcément purement $V$. Mais par le même raisonnement (compte tenu de la symétrie cyclique des options et -de la symétrie des joueurs), si Bob joue purement $V$, Alice répond -purement $W$. Il ne peut donc pas y avoir d'équilibre de Nash dans -lequel Alice joue purement $U$. Et de nouveau par symétrie cyclique -des options et symétrie des joueurs, il ne peut y avoir aucun -équilibre de Nash dans lequel un joueur jouerait une stratégie pure. +de la symétrie des joueurs), si Bob joue purement $V$, Alice joue $W$ +(et pas $U$ comme supposé). Il ne peut donc pas y avoir d'équilibre +de Nash dans lequel Alice joue purement $U$. Et de nouveau par +symétrie cyclique des options et symétrie des joueurs, il ne peut y +avoir aucun équilibre de Nash dans lequel un joueur jouerait une +stratégie pure. \end{corrige} (3) Dans cette question et la suivante, envisageons un équilibre de -Nash dans lequel Alice joue une stratégie mixte $pU + (1-p)V$ avec +Nash dans lequel Alice joue la stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons dans cette question que Bob réponde avec un une stratégie mixte ayant elle aussi $\{U,V\}$ comme support. Montrer que -$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$ ; en +$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$. En utilisant le fait que $\frac{x^2+1}{2x} < -\frac{1}{x}$ lorsque $x<-1$ (qu'on admettra pour ne pas perdre son temps en calculs inutiles), en déduire qu'un tel équilibre de Nash n'existe pas. @@ -690,13 +705,14 @@ fournit un meilleur gain espéré pour Bob, donc $\{U,V\}$ ne peut pas d'Alice. \end{corrige} -(4) Toujours en considérant un équilibre de Nash dans lequel Alice -joue une stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons -maintenant que Bob réponde avec un une stratégie mixte ayant -$U$ et $W$ dans son support support. Montrer que $p = \frac{2}{x+3}$ -(et que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ -lorsque $-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (qu'on -admettra aussi), en déduire qu'un tel équilibre de Nash n'existe pas. +(4) On considère toujours un équilibre de Nash dans lequel Alice joue +la stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons maintenant +que Bob réponde avec une stratégie mixte ayant (au moins) $U$ et $W$ +dans son support support. Montrer que $p = \frac{2}{x+3}$ (et +que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ lorsque +$-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (de nouveau, on +admettra ces faits pour ne pas perdre de temps en calculs), en déduire +qu'un tel équilibre de Nash n'existe pas. \begin{corrige} On a dit dans la question (3) que si Alice joue $pU + (1-p)V$, les @@ -728,17 +744,18 @@ on a exclu $\{U,V\}$ ; dans la question (4), on a exclu $\{U,W\}$ et $\{U,V,W\}$. Reste le cas où le support de la stratégie de Bob est $\{V,W\}$ (tandis que celui d'Alice est, on le rappelle, $\{U,V\}$). Mais quitte à effectuer une symétrie cyclique des options ($U\to W\to -V\to U$) et permuter les joueurs, cela revient au cas où le support de -la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : -mais on a déjà exclu ce cas. Il ne reste donc aucune possibilité. +V\to U$) et échanger les joueurs, cela revient au cas où le support de +la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : or +on a déjà exclu ce cas. Il ne reste donc aucune possibilité. \end{corrige} (6) Envisageons maintenant un équilibre de Nash dans lequel Alice joue une stratégie mixte $pU + p'V + (1-p-p')W$ avec $p>0$, $p'>0$ et $1-p-p'>0$ et Bob répond par une stratégie ayant elle aussi $\{U,V,W\}$ comme support. Écrire un système de deux équations -linéaires sur $p,p'$, justifier que ce système est non-dégéné et -conclure. +linéaires vérifié par $p,p'$, justifier que ce système est +non-dégénéré et conclure. Quels sont tous les équilibres de Nash du +jeu ? \begin{corrige} Si Alice joue $pU + p'V + (1-p-p')W$, les gains espérés de Bob pour |