path: root/controle-20220413.tex

%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\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{\fuzzy}{\mathrel{\|}}
%
\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{13 avril 2022}
\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.

La longueur du sujet ne doit pas effrayer : l'énoncé est long parce
que des rappels ont été faits et que la rédaction des questions
cherche à éviter toute ambiguïté.  Les réponses attendues sont
généralement beaucoup plus courtes que les questions elles-mêmes
(notamment dans le dernier 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

Barème \emph{indicatif} : $8+6+6$.

\ifcorrige
Ce corrigé comporte 10 pages (page de garde incluse).
\else
Cet énoncé comporte 6 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

Le but de cet exercice est de tenter une classification des jeux en
forme normale, à deux joueurs, \emph{symétriques} (c'est-à-dire que
les deux joueurs ont les mêmes options et les mêmes gains sous l'effet
de la permutation qui les échange) et avec deux options.

On considère donc le jeu dont la matrice de gains est la suivante, où
$u,v,x,y$ sont des réels sur lesquels on va discuter (les options sont
étiquetées $C$ et $D$ ; le gain d'Alice est listé en premier, celui de
Bob en second) :

\begin{center}
\begin{tabular}{r|c|c|}
$\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline
$C$&$u$, $u$&$v$, $x$\\\hline
$D$&$x$, $v$&$y$, $y$\\\hline
\end{tabular}
\end{center}

On se limitera à l'étude du cas où $u>v$, ce qu'on supposera
désormais.

(1) Expliquer brièvement pourquoi il ne change rien à l'analyse du jeu
(p.ex., au calcul des équilibres de Nash) de remplacer tous les gains
$t$ d'un joueur donné par $at+b$ où $a>0$ et $b$ est quelconque.  En
déduire qu'on peut supposer, dans le jeu ci-dessus, que $u=1$ et
$v=0$, ce qu'on fera désormais :

\begin{center}
\begin{tabular}{r|c|c|}
$\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline
$C$&$1$, $1$&$0$, $x$\\\hline
$D$&$x$, $0$&$y$, $y$\\\hline
\end{tabular}
\end{center}

(2) À quelle condition le profil $(C,C)$ (c'est-à-dire : Alice
joue $C$ et Bob joue $C$) est-il un équilibre de Nash ?  À quelle
condition $(D,D)$ est-il un équilibre de Nash ?  À quelle condition
$(C,D)$ est-il un équilibre de Nash ?  Qu'en est-il de $(D,C)$ ?  (À
chaque fois, on demande des conditions sous forme d'inégalités portant
sur $x$ et $y$.)

On suppose dans la suite (pour écarter des cas limites pénibles) que
$x$ n'est pas exactement égal à $1$ et que $y$ n'est pas exactement
égal à $0$.

(3) Expliquer pourquoi il n'y a pas d'équilibre de Nash dans lequel un
joueur joue une stratégie pure (i.e., soit $C$ soit $D$) et l'autre
une stratégie strictement mixte (i.e., $pC + (1-p)D$ avec $0<p<1$).

(4) Analyser la possibilité que $(pC + (1-p)D, \; qC + (1-q)D)$, où
$0<p<1$ et $0<q<1$ soit un équilibre de Nash : que doivent valoir
$p$ et $q$ si c'est le cas ? et à quelle condition nécessaire et
suffisante obtient-on effectivement un équilibre de Nash de cette
forme ?  (On pourra tracer un graphique, par ailleurs demandé à la
question suivante, pour visualiser le signe de $1-x+y$.)

(5) Dans le plan de coordonnées $(x,y)$, représenter graphiquement les
domaines des paramètres dans lesquels existent les différents
équilibres de Nash trouvés dans l'analyse.  (On rappelle qu'il doit
toujours y en avoir au moins un, ce qui peut permettre de détecter
d'éventuelles erreurs.)  Dans quelle partie du diagramme se situent le
dilemme du prisonnier et le dilemme du trouillard respectivement ?

(La question (6) peut être traitée indépendamment des questions
précédentes.)

(6) On introduit le nouveau concept suivant : pour un jeu symétrique,
une \textbf{stratégie rationnelle commun} est une stratégie mixte,
donc ici, $rC + (1-r)D$ pour $0\leq 1\leq r$, qui quand elle est jouée
par l'ensemble des joueurs, conduit au gain (forcément le même pour
tous) le plus élevé sous cette contrainte\footnote{Autrement dit, une
  stratégie rationnelle commune est une stratégie mixte $s$ telle que
  si tous les joueurs jouent $s$, leur espérance de gain commune sera
  supérieure ou égale à celle s'ils jouent tous $s'$, quelle que
  soit $s'$.}.  Dans le jeu considéré ici, calculer l'espérance de
gain commune des joueurs s'ils jouent tous $rC + (1-r)D$ , et en
déduire pour quelle(s) valeur(s) de $r$ cette fonction est maximale,
en discutant éventuellement selon les valeurs de $x,y$.  Tracer un
nouveau graphique pour représenter, dans le plan de coordonnés
$(x,y)$, les domaines de paramètres dans lequels existent les
différentes stratégies rationnelles communes (on distinguera : $C$,
$D$ et $rC + (1-r)D$ avec $0<r<1$).


%
%
%

\exercice

On s'intéresse ici à la variation suivante du jeu de nim (fini) :
après avoir retiré des bâtonnets d'une ligne, un joueur peut en outre,
s'il le souhaite, \emph{couper} la ligne en deux, ce qui crée deux
lignes au lieu d'une, en répartissant comme il le veut les bâtonnets
de la ligne initiale (après en avoir retiré au moins un) entre ces
deux lignes.

De façon plus formelle, l'état du jeu est donné par la liste des
nombres $n_1,\ldots,n_r \in \mathbb{N}$ de bâtonnets des différentes
lignes du jeu (on peut ignorer ceux pour lesquels $n_i=0$) ; et un
coup du jeu consiste à choisir un $1\leq i\leq r$ et à remplacer $n_i$
dans la liste soit par un entier neturels $n' < n_i$, soit par
\emph{deux} entiers naturels $n',n''$ tels que $n' + n'' < n_i$ (on
peut d'ailleurs ne considérer que ce deuxième type de coup puisque
prendre $n''=0$ revient à n'avoir que $n'$).  Comme d'habitude, le
joueur qui ne peut pas jouer a perdu (i.e., le gagnant est celui qui
retire le dernier bâtonnet) ; et la disposition des lignes ou des
bâtonnets au sein d'une ligne n'a pas d'importance, seul compte leur
nombre (et tout est fini).

(1) Expliquer pourquoi la valeur de Grundy de la position
$(n_1,\ldots,n_r)$ du jeu est la somme de nim $f(n_1) \oplus \cdots
\oplus f(n_r)$ des valeurs de Grundy $f(n_i)$ des positions ayant une
seule ligne avec $n_i$ bâtonnets (où $f$ est une fonction qui reste à
calculer, avec évidemment $f(0)=0$).

(2) Expliquer pourquoi $f(n) = \mex\{f(n') \oplus f(n'') \; | \;
n'+n'' < n\}$ est le plus petit entier naturel qui n'est pas de la
forme $f(n') \oplus f(n'')$ où $n',n''$ parcourent les couples
d'entiers naturels tels que $n'+n'' < n$ (et comme d'habitude, $\mex
S$ est le plus petit entier naturel qui n'est pas dans $S$).

(3) Indépendamment de ce qui précède, expliquer pourquoi $k \oplus
\ell \leq k + \ell$ quels que soient $k,\ell \in \mathbb{N}$.

(4) Montrer que $f(n) = n$ pour tout $n$.

(5) Que conclure quant à la stratégie gagnante à la variante proposée
ici du jeu de nim par rapport au jeu de nim standard ?


%
%
%

\exercice

On s'intéresse dans cet exercice au jeu de \emph{Hackenbush bicolore
  en arbre}, défini comme suit.  L'état du jeu est représenté par un
arbre (fini, enraciné\footnote{C'est-à-dire que la racine fait partie
  de la donnée de l'arbre, ce qui est la convention la plus
  courante.}) dont chaque arête est soit coloriée \emph{bleue} soit
\emph{rouge}, mais jamais les deux à la fois (il y a exactement deux
types d'arêtes).  Deux joueurs, Blaise et Roxane, alternent et chacun
à son tour choisit une arête de l'arbre, bleue pour Blaise ou rouge
pour Roxane, et l'efface, ce qui fait automatiquement disparaître du
même coup tout le sous-arbre qui descendait de cette arête (voir
figure).  L'arête choisie doit avoir la couleur associée au joueur,
c'est-à-dire bleue pour Blaise ou rouge pour Roxane, mais toutes les
arêtes qui en descendent sont effacées quelle que soit leur couleur.
Le jeu se termine lorsque plus aucun coup n'est possible (c'est-à-dire
que le joueur qui doit jouer n'a plus d'arête de sa couleur), auquel
cas, selon la convention habituelle, le joueur qui ne peut plus jouer
a perdu.

À titre d'exemple, ceci illustre un coup possible de Roxane
(effacement d'une arête rouge et de tout le sous-arbre qui en
descend) :
\begin{center}
\begin{tikzpicture}[baseline=0]
\fill [gray!50!white] (-3.0,0) rectangle (2.0,-0.2);
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node (P0) at (0,0) {};
\node (P1) at (-0.75,1) {};
\node (P2) at (-2.25,2) {};
\node (P3) at (-2.75,3) {};
\node (P4) at (-1.75,3) {};
\node (P5) at (0.75,2) {};
\node (P6) at (0.00,3) {};
\node (P7) at (0.75,3) {};
\node (P8) at (1.50,3) {};
\node (P9) at (1.75,1) {};
\node (P10) at (1.75,2) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw[blue] (P0) -- (P1);
\draw[red] (P1) -- (P2);
\draw[red] (P1) -- (P5);
\draw[blue] (P2) -- (P3);
\draw[blue] (P2) -- (P4);
\draw[blue] (P5) -- (P6);
\draw[blue] (P5) -- (P7);
\draw[red] (P5) -- (P8);
\draw[red] (P0) -- (P9);
\draw[blue] (P9) -- (P10);
\end{scope}
\begin{scope}[line width=3pt,gray!50!black]
\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,-0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,0.2)$);
\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,-0.2)$);
\end{scope}
\end{tikzpicture}
~devient~
\begin{tikzpicture}[baseline=0]
\fill [gray!50!white] (-3.0,0) rectangle (2.0,-0.2);
\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}]
\node (P0) at (0,0) {};
\node (P1) at (-0.75,1) {};
\node (P2) at (-2.25,2) {};
\node (P3) at (-2.75,3) {};
\node (P4) at (-1.75,3) {};
\node (P9) at (1.75,1) {};
\node (P10) at (1.75,2) {};
\end{scope}
\begin{scope}[line width=1.5pt]
\draw[blue] (P0) -- (P1);
\draw[red] (P1) -- (P2);
\draw[blue] (P2) -- (P3);
\draw[blue] (P2) -- (P4);
\draw[red] (P0) -- (P9);
\draw[blue] (P9) -- (P10);
\end{scope}
\end{tikzpicture}
\end{center}

(1) Expliquer brièvement pourquoi une position de ce jeu peut être
considérée comme une somme disjonctive de différents jeux du même
type.  Plus exactement, soit $T$ un arbre bicolore de racine $x$,
soient $y_1,\ldots,y_r$ les fils de $x$, soient $T_1,\ldots,T_r$ les
sous-arbres ayant pour racines $y_1,\ldots,y_r$ et soient
$T'_1,\ldots,T'_r$ les arbres de racine $x$ où $T'_i$ est formé de $x$
et de $T_i$ (y comprise l'arête entre $x$ et $y_i$) : expliquer
brièvement pourquoi la position représentée par l'arbre $T$ est la
somme disjonctive de celles représentées par $T'_1,\ldots,T'_r$.

\smallskip

Si $T$ est un arbre de Hackenbush bicolore, notons $1{:}T$ l'arbre
$T'$ correspondant à placer $T$ au sommet d'une unique arête bleue
reliée à la racine (autrement dit, $T'$ est formé en ajoutant un
nouveau sommet, qui sera la racine, et en ajoutant une arête bleue
entre cette nouvelle racine et l'ancienne racine de $T$).

On \underline{admet} les résultats suivants : à tout arbre de
Hackenbush bicolore $T$ on peut associer un nombre réel $v(T)$ (sa
\emph{valeur}), de façon que :
\begin{itemize}
\item[(a)] Si $T$ et $T'_1, \ldots, T'_r$ sont comme dans l'énoncé de
  la question (1) alors $v(T) = v(T'_1) + \cdots + v(T'_r)$.
\item[(b)] On a $v(-T) = -v(T)$ où $-T$ est l'arbre obtenu en échangeant
  les couleurs rouge et bleue dans $T$.
\item[(c)] On a $v(1{:}T) = \varphi_+(v(T))$ où $\varphi_+$ est la
  fonction définie par\footnote{Les cas dans la définition de
    $\varphi_+$ se chevauchent un peu, et c'est normal : les
    définitions sont compatibles aux chevauchements.}
\[
\varphi_+(v) = \left\{
\begin{array}{ll}
v+1&\hbox{~si $v\geq 0$}\\
2^{-n}\,(v+n+1)&\hbox{~si $-n\leq v \leq -n+1$ où $n\in\mathbb{N}$}\\
\end{array}
\right.
\]
\item[(d)] On a $v(T) \geq 0$ si et seulement si Blaise possède une
  stratégie gagnante en jouant en second à partir de la position $T$,
  et $v(T) \leq 0$ lorsque Roxane en possède une.
\end{itemize}

(2) Utiliser ces règles admises pour calculer la valeur de l'arbre
tracé à gauche dans la figure ci-dessus (avant effacement).  Pour
éviter de se tromper, on recommande de reproduire l'arbre et
d'indiquer à côté de chaque sommet la valeur du sous-arbre qui en
descend, et à côté de chaque arête la valeur du sous-arbre avec
l'arête en question.  En déduire qui a une stratégie gagnante dans
cette position selon le joueur qui commence.

\smallbreak

\centerline{* * *}

Indépendamment de ce qui précède, on va considérer une opération sur
les jeux partisans : si $G$ est un jeu combinatoire partisan, vu comme
un graphe orienté (bien-fondé), on définit un jeu noté $1{:}G$ en
ajoutant une unique position $0$ à $G$ comme on va l'expliquer.  Pour
chaque position $z$ de $G$ il y a une position notée $1{:}z$ de
$1{:}G$, et il y a une unique autre position, notée $0$,
dans $1{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête
$1{:}z\, \to \, 1{:}z'$ dans $1{:}G$, coloriée de la même manière que
dans $G$, et il y a de plus une arête $1{:}z\, \to 0$ dans $1{:}G$
pour chaque $z$, coloriée en bleu (en revanche, $0$ est un puits,
c'est-à-dire qu'aucune arête n'en part) ; la position initiale de
$1{:}G$ est $1{:}z_0$ où $z_0$ est celle de $G$.  De façon plus
informelle, pour jouer au jeu $1{:}G$, chaque joueur peut faire un
coup normal ($1{:}z\, \to \, 1{:}z'$) de $G$, mais par ailleurs,
Blaise peut à tout moment appliquer un coup « destruction totale »
$1{:}z\, \to 0$ qui fait terminer immédiatement le jeu (et il a alors
gagné\footnote{Ce jeu considéré tout seul n'est donc pas très amusant
  puisque Blaise a toujours la possibilité de gagner
  instantanément.}).

(3) Montrer que si $G \geq H$ on a $1{:}G \geq 1{:}H$.  (On rappelle
que $G \geq H$ signifie : « Blaise a une stratégie gagnante s'il joue
en second au jeu $G - H$ défini comme la somme disjonctive du jeu $G$
et du jeu $-H$ obtenu en échangeant les deux joueurs au jeu $H$ ».
Pour cela, on expliquera comment Blaise peut gagner à $(1{:}G) -
(1{:}H)$ en jouant en second, en supposant qu'il sait gagner à $G - H$
en jouant en second.)  En déduire que si $G \doteq H$ alors $1{:}G
\doteq 1{:}H$.

{\footnotesize\textit{Remarque.} Ceci justifie partiellement
  l'affirmation (c) des règles admises ci-dessus en ce sens que cela
  explique que $v(1{:}G)$ ne dépende que de $v(G)$ et pas du détail
  de $G$, et aussi que la fonction $\varphi_+$ est croissante.\par}





%
%
%
\end{document}