diff options
| -rw-r--r-- | controle-20220413.tex | 439 |
1 files changed, 439 insertions, 0 deletions
diff --git a/controle-20220413.tex b/controle-20220413.tex new file mode 100644 index 0000000..66dfbfd --- /dev/null +++ b/controle-20220413.tex @@ -0,0 +1,439 @@ +%% 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 de $u>v$, ce qu'on supposera désormais. + +(1) Expliquer brièvement pourquoi il ne change rien à l'analyse du jeu +(p.ex., le 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 $(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). + +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 $n' < n_i$, soit par \emph{deux} +$n',n''$ tels que $n' + n'' < n_i$ (on peut d'ailleurs ne considérer +que ce deuxième type de coup vu que 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 +(bleue pour Blaise, 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) > 0$ si et seulement si Blaise possède une + stratégie gagnante à partir de la position $T$ (qui que soit le + joueur qui commence), et $v(T) < 0$ lorsque c'est Roxane, et $v(T) = + 0$ lorsque c'est le second joueur. +\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. + +\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} |