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