From fc5eaa31574e9199c35965500b251bc0b079b365 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Wed, 12 Apr 2023 22:47:20 +0200 Subject: Re-reading and minor changes. --- controle-20230417.tex | 123 ++++++++++++++++++++++++++++---------------------- 1 file 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 1$ -lorsque $-3 1$ lorsque +$-30$, $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 -- cgit v1.2.3