%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} \usepackage[francais]{babel} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} %\usepackage{ucs} \usepackage{times} % A tribute to the worthy AMS: \usepackage{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsthm} % \usepackage{mathrsfs} \usepackage{wasysym} \usepackage{url} % \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} \usepackage{hyperref} % %\externaldocument{notes-mitro206}[notes-mitro206.pdf] % \theoremstyle{definition} \newtheorem{comcnt}{Tout} \newcommand\thingy{% \refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% \refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} \renewcommand{\qedsymbol}{\smiley} % \newcommand{\outnb}{\operatorname{outnb}} \newcommand{\downstr}{\operatorname{downstr}} \newcommand{\precs}{\operatorname{precs}} \newcommand{\mex}{\operatorname{mex}} \newcommand{\id}{\operatorname{id}} \newcommand{\limp}{\Longrightarrow} \newcommand{\gr}{\operatorname{gr}} \newcommand{\rk}{\operatorname{rk}} \newcommand{\fuzzy}{\mathrel{\|}} % \DeclareUnicodeCharacter{00A0}{~} % \DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} \DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} % \DeclareFontFamily{U}{manual}{} \DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} \newcommand{\manfntsymbol}[1]{% {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} \newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped \newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% \hbox to0pt{\hskip-\hangindent\dbend\hfill}} % \newcommand{\spaceout}{\hskip1emplus2emminus.5em} \newif\ifcorrige \corrigetrue \newenvironment{corrige}% {\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\par\smallbreak\else\egroup\par\fi} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} \date{12 avril 2021} \maketitle \pretolerance=8000 \tolerance=50000 \vskip1truein\relax \noindent\textbf{Consignes.} 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 : d'une part, l'énoncé est long parce que des rappels ont été faits et que la rédaction des questions cherche à éviter toute ambiguïté ; d'autre part, il ne sera pas nécessaire de tout traiter pour obtenir la totalité des points. \medbreak L'usage de tous les documents (notes de cours manuscrites ou imprimées, feuilles d'exercices, livres) est autorisé. L'usage des appareils électroniques est interdit. \medbreak Durée : 2h Barème \emph{indicatif} : chaque question numérotée aura approximativement la même valeur (environ $1$ à $1.5$ points). \ifcorrige Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse). \else Cet énoncé comporte 5 pages (page de garde incluse). \fi \vfill {\noindent\tiny \immediate\write18{sh ./vc > vcline.tex} Git: \input{vcline.tex} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pagebreak % % % \exercice On considère le jeu en forme normale, à deux joueurs, à somme nulle, dont la matrice de gains est la suivante, où $x$ est un réel (la table donne les gains d'Alice, qui choisit la ligne, ceux de Bob, qui 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$\\ \end{tabular} \end{center} On rappelle qu'une \emph{stratégie optimale} est une stratégie mixte qui réalise un gain espéré au moins égal à la valeur du jeu contre toute stratégie (pure donc mixte) de l'adversaire. (0) Quelle est la valeur du jeu dans ce cas ? (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 à choisir R avec probabilité $\frac{x}{x+2}$, et chacun de P et S avec probabilité $\frac{1}{x+2}$) est-elle optimale ? (3) Donner une stratégie optimale lorsque $x\leq 0$. (4) Dans chacun des cas $x=0$ et $x=1$, exhiber une infinité de stratégies optimales distinctes. (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 ? % % % \exercice Dans cet exercice, on va d'abord définir les ordinaux $\varepsilon_\iota$, puis on va s'intéresser à ceux qui sont $<\varepsilon_1$. Les parties de cet exercice sont indépendantes à l'exception de ce qui est explicitement rappelé. \medskip \underline{Première partie.} 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$ alors $\varphi(\alpha) < \varphi(\beta)$). (1) Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie par définition la chose suivante : si $\delta$ est un ordinal limite, alors $\lim_{\xi\to\delta} \varphi(\xi) = \varphi(\delta)$, où $\lim_{\xi\to\delta} \varphi(\xi)$ est une notation pour $\sup\{\varphi(\xi) : \xi < \delta\}$. Pour éviter de partir dans des fausses directions, il est conseillé, jusqu'à la question (5) incluse, d'oublier la définition de $\varphi$ et de retenir simplement que $\varphi$ est strictement croissante et continue. (2) Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour tout $\alpha$. On dira qu'un ordinal $\gamma$ est un \emph{point fixe} de $\varphi$ lorsque $\varphi(\gamma) = \gamma$. (3) Soit dans cette question $\alpha$ un ordinal quelconque : considérons la suite $(\gamma_n)$ (indicée par les entiers naturels $n$) définie par $\gamma_0 = \alpha$ et $\gamma_{n+1} = \varphi(\gamma_n)$. Montrer que $(\gamma_n)$ est croissante (c'est-à-dire que $m\leq n$ implique $\gamma_m \leq \gamma_n$). Montrer que sa limite $\gamma_\omega := \lim_{n\to\omega} \gamma_n := \sup\{\gamma_n : n \in \mathbb{N}\}$ est un point fixe de $\varphi$. Montrer qu'il s'agit du plus petit point fixe de $\varphi$ qui soit $\geq\alpha$ (c'est-à-dire que si $\delta$ est un point fixe de $\varphi$ et $\delta\geq\alpha$ alors $\delta\geq\gamma_\omega$ : on pourra pour cela montrer que $\delta\geq\gamma_n$ pour tout $n$). La question (3) implique notamment : \emph{pour tout ordinal $\alpha$ il existe un point fixe de $\varphi$ qui soit $\geq\alpha$}. On définit maintenant $\varepsilon_\iota$ pour tout ordinal $\iota$ par : \begin{itemize} \item $\varepsilon_0$ est le plus petit point fixe de $\varphi$ (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq 0$) ; \item pour $\iota+1$ ordinal successeur, $\varepsilon_{\iota+1}$ est le plus petit point fixe de $\varphi$ qui soit $>\varepsilon_\iota$ (c'est-à-dire, si on veut, le plus petit point fixe qui soit $\geq (\varepsilon_\iota)+1$), \item pour $\delta$ ordinal limite, $\varepsilon_\delta$ est $\lim_{\xi\to\delta} \varepsilon_\xi$ (c'est-à-dire $\sup\{\varepsilon_\xi : \xi < \delta\}$). \end{itemize} (4) Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement croissante. Montrer que $\varepsilon_\delta$ est un point fixe de $\varphi$ aussi pour $\delta$ limite (c'est vrai pour les autres cas par la définition) : pour cela, on expliquera pourquoi $\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$. (5) Montrer que tout ordinal $\gamma$ qui est un point fixe de $\varphi$ est de la forme $\varepsilon_\iota$ pour un certain ordinal $\iota$ (on pourra montrer qu'il existe $\iota$ tel que $\varepsilon_\iota\geq\gamma$ puis considérer le plus petit tel $\iota$). \medskip \underline{Deuxième partie.} \nobreak On appelle $\varepsilon_0$ le plus petit ordinal tel que $\varepsilon = \omega^\varepsilon$, et $\varepsilon_1$ le suivant, c'est-à-dire le plus petit ordinal $>\varepsilon_0$ vérifiant cette même équation $\varepsilon = \omega^\varepsilon$ (l'existence de ces ordinaux résulte de la première partie de cet exercice). On a vu en cours que les ordinaux $<\varepsilon_0$ possèdent une représentation unique sous forme normale de Cantor itérée, et que celle-ci permet de les comparer, de les ajouter et de les multiplier. On va se pencher ici sur \emph{deux} systèmes différents d'écriture des ordinaux $<\varepsilon_1$, qu'on appellera « écriture 1 » et « écriture 2 ». (6) Soit $\alpha < \varepsilon_1$ un ordinal différent de $\varepsilon_0$ : montrer que dans sa forme normale de Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$, tous les exposants $\gamma_i$ sont $<\alpha$ (on pourra utiliser le fait, démontré en (2), que $\omega^\gamma \geq \gamma$ pour tout ordinal $\gamma$). On appellera \emph{écriture 1} d'un ordinal $\alpha < \varepsilon_1$ l'écriture qui est \underline{ou bien} $\varepsilon_0$ (considéré comme un symbole spécial), \underline{ou bien} une forme normale de Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ où les exposants $\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et eux-mêmes écrits en écriture 1 (ceci a bien un sens par (6)). À titre d'exemple, $\omega^\omega\,2$ ou $\varepsilon_0$ ou bien $\omega^{\varepsilon_0} + 1$ ou encore $\omega^{\omega^{\varepsilon_0}+1}\,2$ sont des écritures 1. En revanche, $\omega^{\varepsilon_0}$ n'en est pas une (elle ne vérifie pas la contrainte sur les exposants), ni $\varepsilon_0 + 1$ (ce n'est ni le symbole spécial $\varepsilon_0$ ni une forme normale de Cantor), ni $(\varepsilon_0)^2$. (7) Il est facile de voir que cette écriture 1 permet algorithmiquement de manipuler les ordinaux $<\varepsilon_1$ : c'est-à-dire de les comparer, de les ajouter et de les multiplier (on ne demande pas de le justifier, les algorithmes étant essentiellement les mêmes que vus en cours pour les ordinaux $<\varepsilon_0$) : il faut simplement bien se rappeler que le fait que $\varepsilon_0 = \omega^{\varepsilon_0}$. À titre d'exemple, calculer $\varepsilon_0\cdot \omega$ et $\varepsilon_0^2 = \varepsilon_0\cdot\varepsilon_0$ en écriture 1. Expliquer comment calculer $(\varepsilon_0)^\alpha$ en écriture 1 lorsque $\alpha$ est lui-même donné en écriture 1. À titre d'exemple, écrire $(\varepsilon_0)^{\omega 2}$ en écriture 1. (8) Indépendamment des questions précédentes, rappeler pourquoi tout ordinal $\alpha$ possède une écriture unique sous la forme $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + (\varepsilon_0)^{\gamma_1}\, \xi_1$ où $\gamma_s > \cdots > \gamma_1$ sont des ordinaux et où $\xi_s,\ldots,\xi_1$ sont des ordinaux tous non nuls et strictement inférieurs à $\varepsilon_0$. (9) Indépendamment des questions précédentes, montrer que $\varepsilon_0 + \varepsilon_1 = \varepsilon_1$ (on rappelle que $\omega^\gamma + \omega^{\gamma'} = \omega^{\gamma'}$ lorsque $\gamma < \gamma'$). En déduire que $\varepsilon_0 \cdot \varepsilon_1 = \varepsilon_1$. En déduire que $(\varepsilon_0)^{\varepsilon_1} = \varepsilon_1$. Réciproquement, montrer que si $\delta$ est un ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors on a aussi $\omega^\delta = \delta$ (on pourra montrer $\delta \leq \omega^\delta \leq \omega^{\varepsilon_0 \delta} \leq \delta$) et en déduire que $\delta \geq \varepsilon_1$. En déduire que $\varepsilon_1$ est le plus petit ordinal tel que $(\varepsilon_0)^{\delta} = \delta$. On appellera \emph{écriture 2} d'un ordinal $\alpha < \varepsilon_1$ une écriture $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + (\varepsilon_0)^{\gamma_1}\, \xi_1$ comme en (7), où les exposants $\gamma_s > \cdots > \gamma_1$ sont tous $<\alpha$ et eux-mêmes écrits en écriture 2, et où les $\xi_s,\ldots,\xi_1$ (qui sont $<\varepsilon_0$) sont écrits en forme normale de Cantor itérée. À titre d'exemple, $\omega^\omega\,2$ (il faut sous-entendre $(\varepsilon_0)^0$ devant, qui vaut $1$) ou $(\varepsilon_0)^2 + 1$ ou bien $\varepsilon_0\,2 + \omega^\omega$ ou encore $(\varepsilon_0)^{\varepsilon_0}\,\omega^\omega\,3$ sont des écritures 2. En revanche, $\omega^{\varepsilon_0+1}$ n'en est pas une (les puissances de $\omega$ ne peuvent apparaître qu'au sein d'une forme normale de Cantor itérée, donc ne faisant jamais intervenir $\varepsilon_0$). (10) Esquisser un algorithme permettant de convertire l'écriture 2 d'un ordinal $<\varepsilon_1$ en écriture 1 (on utilisera la question (7)). \medskip \underline{Troisième partie.} \nobreak On aura besoin ici des définitions des ordinaux $\varepsilon_0$ et $\varepsilon_1$ données en tête de la première partie, mais pas plus. On s'intéresse à un jeu de Hercule et de l'hydre qui est analogue au jeu considéré en cours mais avec une extension : comme en cours, l'hydre est un arbre fini enraciné, mais l'hydre a maintenant deux types de têtes (= feuilles de l'arbre) : des têtes normales, et des \emph{œufs} (pouvant donner naissance à de nouvelles hydres). Quand Hercule coupe une tête $x$ normale, l'hydre se reproduit exactement comme on l'a vu en cours, c'est-à-dire qu'elle reproduit autant d'exemplaires qu'elle le veut de tout le sous-arbre partant du nœud $y$ parent de $x$ dans l'arbre (ces copies étant ajoutées comme filles du nœud $z$ parent de $y$), à condition que $y$ ne soit pas la racine (sinon, l'hydre ne joue pas). En revanche, si Hercule coupe un œuf, cet œuf est remplacé par une nouvelle hydre, c'est-à-dire par un sous-arbre, arbitrairement complexe, mais ne comportant pas lui-même d'œuf. (11) En associant à toute position du jeu (= tout arbre enraciné dont certaines feuilles sont qualifiées d'œufs) un ordinal $<\varepsilon_1$, montrer que Hercule gagne toujours, c'est-à-dire qu'il va toujours réduire l'hydre à sa seule racine en temps fini. (12) Donner un exemple de position du jeu associé à l'ordinal $(\varepsilon_0)^{\varepsilon_0}$ par le système proposé en (11). % % % \end{document}