diff options
Diffstat (limited to 'controle-20260622.tex')
| -rw-r--r-- | controle-20260622.tex | 322 |
1 files changed, 322 insertions, 0 deletions
diff --git a/controle-20260622.tex b/controle-20260622.tex new file mode 100644 index 0000000..cbd6973 --- /dev/null +++ b/controle-20260622.tex @@ -0,0 +1,322 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\usepackage[french]{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}{Whatever} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercise{% +\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{\|}} +% +\newcommand{\dblunderline}[1]{\underline{\underline{#1}}} +% +\renewcommand{\thefootnote}{\fnsymbol{footnote}} +% +\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{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} +\else +\title{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} +\fi +\author{} +\date{2026-06-22} +\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. + +Une traduction anglaise indicative suit l'énoncé en français. + +\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 + + +% +% +% + +\exercise + +L'expérience de pensée suivante a circulé sur divers réseaux sociaux +en avril–mai 2026 : + +\begin{narrower} +« Devant chaque personne sur Terre apparaissent deux boutons, un bleu + et un rouge. Chacun doit appuyer en secret sur l'un des deux. Si + au moins 50\% appuient sur le bouton bleu, tout le monde survit. + Sinon, seuls ceux qui ont appuyé sur le bouton rouge survivent. Que + feriez-vous ? »\par +\end{narrower} + +Nous allons étudier ce problème sous l'angle de la pure théorie des +jeux\footnote{En supposant, entre autres hypothèses simplificatrices +critiquables, que chacun n'est préoccupé que par sa propre survie.}. +On considère donc le jeu en forme normale suivant : $n\geq 2$ joueurs +doivent fait un choix simultané entre deux options, $B$ (bleu) et +$R$ (rouge) ; par ailleurs, on a fixé à l'avance\footnote{On suppose +tacitement que ce seuil, comme l'ensemble des règles du jeu, sont +connus de tous les joueurs. Dans l'expérience de pensée du texte cité +ci-dessus ce serait $s = \lceil n/2\rceil$, le plus petit entier $\geq +n/2$, mais ceci n'aura pas d'impact sur le raisonnement donc on ne +supposera rien.} un nombre $2 \leq s \leq n$. Le gain des joueurs est +déterminé par les règles suivantes : +\begin{itemize} +\item si $\geq s$ joueurs ont choisi l'option $B$, alors le gain de + chaque joueur est $0$ ; +\item sinon (c'est-à-dire : si $> n-s$ joueurs ont choisi + l'option $R$), alors le gain des joueurs ayant choisi $R$ est $0$ et + celui des joueurs ayant choisi l'option $B$ est $-1$. +\end{itemize} + +Le but de l'exercice est de déterminer les équilibres de Nash de ce +jeu. + +On rappelle qu'on dit que $R$ est dans le \textbf{support} d'une +stratégie (mixte) $(1-p) B + p R$ lorsque $p>0$, et que $B$ est dans +le support de $(1-p) B + p R$ lorsque $p<1$. + +\medskip + +\textbf{(1)} Considérons un joueur $i$ particulier.\quad +\textbf{(a)} Montrer que si $> n-s$ des $n-1$ autres joueurs jouent +une stratégie ayant $R$ dans son support, alors le joueur $i$ +considéré a une espérance de gain strictement plus grande en +jouant $R$ qu'en jouant $B$. (On demande une démonstration +mathématiquement précise ici.)\quad\textbf{(b)} Montrer qu'au +contraire si $\leq n-s$ des autres joueurs jouent une stratégie ayant +$R$ dans son support, alors le joueur $i$ a une espérance de gain +égale à $0$ quel que soit son choix. + +\begin{corrige} +\textbf{(a)} Appelons $\mathscr{R}$ l'ensemble des joueurs $j \neq i$ +qui jouent une stratégie $(1-p_j) B + p_j R$ ayant $R$ dans son +support (les autres jouent donc la stratégie pure $B$). Le gain du +joueur $i$ est $0$ s'il joue $R$ ; s'il joue $B$, son gain est +l'opposé de la probabilité (appelons-la $q$) que $> n-s$ joueurs +jouent $R$. Si le cardinal $\#\mathscr{R}$ de $\mathscr{R}$ vaut $> +n-s$, alors cette probabilité $q$ vaut $\geq\prod_{j\in\mathscr{R}} +p_j > 0$ (puisque au moins dans le cas où chaque joueur +$j\in\mathscr{R}$ joue effectivement $R$, l'événement « $> +n-s$ joueurs jouent $R$ » se sera produit) ; et alors l'espérance du +gain du joueur $i$ considéré est strictement plus grande (à +savoir $0$) en jouant $R$ que s'il joue $B$ (à savoir $-q$). C'est ce +qui était demandé. + +\textbf{(b)} Si le joueur $i$ considéré joue $R$, son gain vaut de +toute façon $0$ donc il n'y a rien à prouver. Mais s'il joue $B$, +comme on a supposé que $\leq n-s$ des autres joueurs jouent $R$, on +est dans le cas où $\geq s$ joueurs jouent $B$, et le gain de tous les +joueurs vaut $0$, donc l'affirmation de l'énoncé est vraie aussi. +\end{corrige} + +\medskip + +\textbf{(2)} En déduire que, dans un équilibre de Nash, si $B$ est +dans le support de la stratégie d'un certain joueur $i$, alors $\leq +n-s$ des autres joueurs jouent une stratégie ayant $R$ dans le +support. + +\begin{corrige} +Si $B$ est dans le support de la stratégie du joueur $i$, alors c'est +une meilleure réponse possible au profil de stratégie des autres +joueurs, et d'après (1)(a), ceci implique que $\leq n-s$ des autres +joueurs jouent une stratégie ayant $R$ dans son support. +\end{corrige} + +\medskip + +\textbf{(3)} Considérons un équilibre de Nash et appelons +respectivement : $n_B$ le nombre de joueurs qui jouent la stratégie +pure $B$ ; $n_R$ ceux qui jouent la stratégie pure $R$, et $n_M$ ceux +qui jouent une stratégie mixte $(1-p) B + p R$ ayant à la fois +$B$ et $R$ dans le support (i.e., telle que $0<p<1$). En appliquant +la question (2) à un joueur bien choisi, montrer que : +\begin{itemize} +\item[\textbf{(a)}] si $n_B > 0$, alors $n_M + n_R \leq n-s$ + (c'est-à-dire $n_B \geq s$) ; +\end{itemize} +et, d'autre part, que : +\begin{itemize} +\item[\textbf{(b)}] si $n_M > 0$, alors $n_M + n_R \leq n-s+1$ + (c'est-à-dire $n_B \geq s-1$). +\end{itemize} + +\begin{corrige} +Observons avant tout que $n_B + n_M + n_R = n$ de façon évidente. + +Pour montrer (a) : si $n_B > 0$, on peut appliquer la question (2) à +un joueur $i$ qui joue la stratégie pure $B$ ; elle nous permet de +dire que $\leq n-s$ des autres joueurs jouent une stratégie ayant $R$ +dans le support, et comme $i$ lui-même joue purement $B$, on voit que +$\leq n-s$ parmi tous les joueurs jouent une stratégie ayant $R$ dans +le support, c'est-à-dire $n_M + n_R \leq n-s$, c'est-à-dire $n_B \geq +s$. + +Pour montrer (b) : si $n_M > 0$, on peut appliquer la question (2) à +un joueur $i$ qui joue une stratégie ayant à la fois $B$ et $R$ dans +le support ; elle nous permet de dire que $\leq n-s$ des autres +joueurs jouent une stratégie ayant $R$ dans le support, et comme $i$ +lui-même compte aussi, on voit que $\leq n-s+1$ parmi tous les joueurs +jouent une stratégie ayant $R$ dans le support, c'est-à-dire $n_M + +n_R \leq n-s+1$, c'est-à-dire $n_B \geq s-1$. +\end{corrige} + +\medskip + +\textbf{(4)} Conclure qu'il y a deux sortes d'équilibres de Nash : +\begin{itemize} +\item ceux où $\geq s$ joueurs jouent la stratégie pure $B$, +\item celui où \emph{tous} les joueurs jouent la stratégie pure $R$. +\end{itemize} +On vérifiera que ce sont bien des équilibres de Nash. + +\begin{corrige} +Si on garde la notation $(n_B,n_M,n_R)$ de la question (3) pour un +équilibre de Nash, on a soit $n_R < n$ soit $n_R = n$. Le second cas +correspond bien à la situation où tous les joueurs jouent la stratégie +pure $R$. Dans le second cas, $n_B + n_M > 0$ donc soit $n_B > 0$ +soit $n_M > 0$. Si $n_B > 0$, alors (3)(a) donne $n_B \geq s$, +c'est-à-dire qu'on est dans la situation où $\geq s$ joueurs jouent la +stratégie pure $B$ ; mais si $n_M > 0$, alors (3)(b) donne $n_B \geq +s-1 > 0$ car $s \geq 2$, et on est ramené au cas qu'on vient de +traiter. Ceci achève de démontrer que tout équilibre de Nash est +d'une des deux sortes qu'on a dites. + +Montrons enfin que ce sont effectivement des équilibres de Nash : pour +ce qui est de la première sorte, il y a $\leq n-s$ joueurs jouant une +stratégie ayant $R$ dans son support, donc c'est exactement ce +qu'affirme la question (1)(b). Et pour la seconde sorte, c'est +évident (l'option $R$ est une meilleure réponse à n'importe quel +profil de stratégies des autres joueurs). +\end{corrige} + +\medskip + +\textbf{(5)} Pour $n=3$ et $s=2$, faire un dessin dans l'espace +$(p_1,p_2,p_3)$ (où $(1-p_i) B + p_i R$ est la stratégie du +joueur $i$) où on montrera le domaine des profils de stratégies mixtes +possibles, et la partie correspondant aux équilibres de Nash. + +\begin{corrige} +On dessine un cube de côté $1$ : l'ensemble du cube $[0,1]^3$ +correspond aux profils de stratégies mixtes $(p_1,p_2,p_3)$ +possibles ; la partie correspondant aux équilibres de Nash est le +sommet $(1,1,1)$ (tous les joueurs jouent purement $R$) ainsi que la +réunion des trois arêtes passant par $(0,0,0)$ (correspond aux +situations où deux joueurs jouent purement $B$ et le troisième suit +une stratégie quelconque). +\end{corrige} + +\medskip + +\textbf{(6)} La conclusion de la question (4) est fausse pour $s=1$ : +expliquer pourquoi, et indiquer à quel endroit dans le raisonnement on +a utilisé l'hypothèse $s\geq 2$. + +\begin{corrige} +Pour $s=1$, le jeu est trivial : le gain de chaque joueur est +toujours $0$ (en effet, si tous les joueurs jouent $R$, leur gain +est $0$ de toute façon, et si un joueur joue $B$ alors le gain de tous +les joueurs est $0$ par la première clause des règles). Il s'ensuit +que n'importe quel profil de stratégies mixtes est un équilibre de +Nash, et ils ne sont pas tous d'une des deux sortes qu'on a dites +en (4). L'hypothèse $s\geq 2$ a été utilisée en (4), juste après +l'utilisation de la question (3)(b), pour passer de $n_B \geq s-1$ à +$n_B > 0$. +\end{corrige} + + + +% +% +% +\end{document} |