path: root/controle-20260622.tex

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