path: root/controle-20240422.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2.5cm]{geometry}
\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{\dur}{\operatorname{dur}}
\newcommand{\fuzzy}{\mathrel{\|}}
%
\newcommand{\dblunderline}[1]{\underline{\underline{#1}}}
%
\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{22 avril 2024}
\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.

\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

\ifcorrige
Ce corrigé comporte \textcolor{red}{xxx} pages (page de garde incluse).
\else
Cet énoncé comporte \textcolor{red}{xxx} 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

\textbf{(1)} On considère le jeu en forme normale défini par la
matrice de gain suivante :
\begin{center}
\begin{tabular}{r|cc}
$\downarrow$Alice, Bob$\rightarrow$&$X$&$Y$\\\hline
$X$&$1$&$0$\\
$Y$&$0$&$2$\\
\end{tabular}
\end{center}
Un seul nombre a été inscrit dans chaque case car les gains des deux
joueurs sont \emph{égaux}, et c'est ce nombre-là qui est écrit
(attention, il ne s'agit pas d'un jeu à somme nulle, au contraire : au
lieu d'être antagonistes, les intérêts des deux joueurs sont
parfaitement alignés).

Étudier et déterminer tous les équilibres de Nash de ce jeu : on
commencera par considérer ceux en stratégies pures, puis par
considérer les cas où un joueur, ou l'autre, ou les deux, joue une
stratégie strictement mixte (i.e., ayant pour support $\{X,Y\}$).

\textbf{(2)} Plus généralement, on considère un jeu de la forme
suivante : les deux joueurs ont le même ensemble d'options, notons-le
$\{X_1,\ldots,X_N\}$, et ils ont le même gain $u_A(a,b) = u_B(a,b)$
pour $a,b\in \{X_1,\ldots,X_N\}$, et de plus ce gain vaut $0$ lorsque
$b\neq a$ et il vaut $g_i$ lorsque $a = b = X_i$, où tous les $g_i$
sont des strictement positifs et distincts, disons $0 < g_1 < g_2 <
\cdots < g_N$ pour fixer les idées.  Pour résumer :
\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$Alice, Bob$\rightarrow$&$X_1$&$\cdots$&$X_N$\\\hline
$X_1$&$g_1$&$\cdots$&$0$\\
$\vdots$&$\vdots$&$\ddots$&$\vdots$\\
$X_N$&$0$&$\cdots$&$g_N$\\
\end{tabular}
\end{center}

\textbf{(a)} Montrer que, dans un équilibre de Nash d'un jeu comme on
vient de le dire, si $I \subseteq \{X_1,\ldots,X_N\}$ est le
support\footnote{On rappelle que le support d'une stratégie mixte est
l'ensemble des options qu'elle choisit avec une probabilité $>0$.} de
la stratégie d'Alice, le support $J$ de la stratégie de Bob est inclus
dans $I$.  (\emph{Indication :} toute option hors de $I$ apporte un
gain espéré nul, donc strictement moins bon que n'importe quelle
combinaison convexe d'options dans $I$.)  En déduire par symétrie
que $I=J$.

\textbf{(b)} Toujours en considérant un équilibre de Nash d'un tel
jeu, en notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie (mixte)
d'Alice, montrer que les $g_i p_i$ tels que $p_i > 0$ (c'est-à-dire
$X_i \in I$) sont tous égaux entre eux.  En déduire par symétrie le
résultat analogue pour la stratégie de Bob.  En déduire qu'il existe
au plus $2^N - 1$ équilibres de Nash, un pour chaque partie non vide
$I$ de $\{X_1,\ldots,X_N\}$.

\textbf{(c)} Vérifier que les stratégies mixtes décrites en (b) sont
bien des équilibres de Nash du jeu, et conclure qu'il a exactement
$2^N - 1$ équilibres de Nash, qu'on décrira explicitement.


%
%
%

\exercice

On considère un jeu de la forme suivante.  Soit $A \subseteq
\mathbb{R}$ un ensemble de réels, soit $X \subseteq \mathbb{R}$ un
ensemble \emph{fini} de réels, et soit enfin $b>1$ un réel.  (Toutes
ces données sont fixées à l'avance et sont des paramètres définissant
le jeu.  Ils sont supposés connus des deux joueurs.)

Chaque joueur quand vient son tour choisit un élément $x_i \in X$ :
plus exactement, Alice choisit $x_0$, puis Bob choisit $x_1$, puis
Alice choisit $x_2$, et ainsi de suite.  Il n'y a aucune contrainte
sur le choix du $x_i$.

Au bout d'un nombre infini de tours, on considère le réel
\[
u = x_0 + \frac{x_1}{b} + \frac{x_2}{b^2} + \frac{x_3}{b^3} + \cdots
\]
c'est-à-dire la somme de la série
$\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$.  Cette série converge car elle
converge absolument\footnote{\label{footnote-series-converges}Preuve :
$\sum_{i=0}^{+\infty}\left|\frac{x_i}{b^i}\right| \leq
\sum_{i=0}^{+\infty}\frac{M}{b^i} = \frac{M}{1-b}$ où $M$ est un
majorant des $|x|$ pour $x\in X$, qui existe car $X$ est fini.}.  Si
$u\in A$ alors Alice a gagné ; sinon, Bob a gagné.

(Un cas particulier qu'on peut garder à l'esprit est celui où $X =
\{0,1\}$ et $b = 2$, auquel cas Alice et Bob construisent un nombre
binaire entre $0$ et $2$ en choisissant alternativement ses chiffres :
$u = x_0.x_1 x_2 x_3\cdots$ en binaire.)

On cherche à montrer que sous certaines conditions sur $A$, l'un des
joueurs a une stratégie gagnante.

\textbf{(1)} On considère l'application $\psi\colon X^{\mathbb{N}} \to
\mathbb{R}$ qui à une suite $\dblunderline{x} = (x_i)_{i\in\mathbb{N}}
\in X^{\mathbb{N}}$ associe $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$.
Montrer que si $\psi(\dblunderline{x}) = u$ et $\varepsilon > 0$,
alors il existe $\ell \in \mathbb{N}$ tel que toute suite
$\dblunderline{y}$ commençant par $x_0,\ldots,x_{\ell-1}$ vérifie
$|\psi((y_i))-u| < \varepsilon$.  (Autrement dit, il existe $\ell$ tel
que l'image du $\ell$-ième voisinage fondamental
$V_\ell(\dblunderline{x})$ de $\dblunderline{x}$ par $\psi$ soit
incluse dans la boule ouverte $B_\varepsilon(u) =
\mathopen]u-\varepsilon,u+\varepsilon\mathclose[$.
\emph{Indication :} s'inspirer de la note en bas de
page \ref{footnote-series-converges}.)

\textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au
sens de la topologie usuelle des réels), alors l'image réciproque
$\psi^{-1}(U) \subseteq X^{\mathbb{N}}$ est ouverte (au sens de la
topologie produit de la topologie discrète sur $X^{\mathbb{N}}$, qu'on
a considérée en cours).

\textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé, l'un des
deux joueurs possède une stratégie gagnante au jeu qu'on a décrit.

\textbf{(4)} Montrer ce résultat lorsque $A = \mathbb{Q}$ (autrement
dit, Alice gagne si la somme $u$ de la série est
rationnelle\footnote{Merci d'avance de ne pas prétendre que
$\mathbb{Q}$ est ouvert, ni qu'il est fermé.}).  Plus généralement,
montrer ce résultat lorsque $A$ est borélien.


%
%
%

\exercice

On va développer dans cet exercice un algorithme pour calculer la
somme et le produit d'ordinaux écrits en forme normale de Cantor
(itérée).

\textbf{(1)} On rappelle que $1 + \omega = \omega$.  En déduire que si
un ordinal $\alpha$ vérifie $\alpha \geq \omega$, alors on a $1 +
\alpha = \alpha$ (\emph{indication :} pourquoi peut-on écrire $\alpha
= \omega + \beta$ ?).  En déduire que $1 + \omega^\gamma =
\omega^\gamma$ lorsque $\gamma > 0$, puis que $\omega^{\gamma_1} +
\omega^{\gamma_2} = \omega^{\gamma_2}$ lorsque $\gamma_1 < \gamma_2$,
et enfin que $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 =
\omega^{\gamma_2} n_2$ si $n_1,n_2$ sont deux entiers naturels non
nuls (et toujours avec $\gamma_1 < \gamma_2$).

\textbf{(2)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots +
\omega^{\gamma_1} n_1$ (avec $\gamma_s > \cdots > \gamma_1$ et
$n_1,\ldots,n_s$ des entiers naturels non nuls) et $\alpha' =
\omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$
(idem) sont deux ordinaux écrits en forme normale de Cantor, en
utilisant les résultats de la question précédente, expliquer comment
calculer $\alpha + \alpha'$, en supposant qu'on sache
algorithmiquement comparer les $\gamma_i$ et les $\gamma'_j$.

\textbf{(3)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot
3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha +
\alpha'$ et $\alpha' + \alpha$.

\textbf{(4)} Déduire de la question (2) que si $\alpha =
\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ en forme
normale de Cantor et $k \geq 1$ est un entier naturel, alors
$\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}}
n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ (c'est-à-dire que seul le
coefficient $n_s$ de la plus haute puissance de $\omega$ est multiplié
par $k$ ; \emph{indication} : on a $\alpha\cdot k = \alpha + \cdots +
\alpha$ avec $k$ termes identiques).

\textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s}
n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\omega =
\omega^{\gamma_s+1}$ (\emph{indication} : on pourra calculer
$\lim_{k\to\omega} \alpha \cdot k$), et plus généralement
$\alpha\omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq
1$ (\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$).

\textbf{(6)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots +
\omega^{\gamma_1} n_1$ et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} +
\cdots + \omega^{\gamma'_1} n'_1$ sont deux ordinaux écrits en forme
normale de Cantor, en utilisant les résultats de la question
précédente, expliquer comment calculer $\alpha \cdot \alpha'$, en
supposant qu'on sache algorithmiquement comparer et ajouter les
$\gamma_i$ et les $\gamma'_j$.

\textbf{(7)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot
3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha \cdot
\alpha'$ et $\alpha' \cdot \alpha$.



%
%
%
\end{document}