From 8823f202c0820c4328f3942388c928b6a3e82c9d Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 16 Apr 2024 20:41:17 +0200 Subject: Write test for 2024. --- controle-20240422.tex | 318 ++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 318 insertions(+) create mode 100644 controle-20240422.tex diff --git a/controle-20240422.tex b/controle-20240422.tex new file mode 100644 index 0000000..e80dece --- /dev/null +++ b/controle-20240422.tex @@ -0,0 +1,318 @@ +%% 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} -- cgit v1.2.3