path: root/controle-20210412.tex

%% 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}