%% 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{xr-hyper} % \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}\smallbreak\noindent\textbf{\thecomcnt.} } \newcommand\exercice{% \refstepcounter{comcnt}\bigbreak\noindent\textbf{Exercice~\thecomcnt.}} \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\relax\else\egroup\fi\par} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théorie des jeux}} \fi \author{} \date{19 avril 2017} \maketitle %% {\footnotesize %% \immediate\write18{sh ./vc > vcline.tex} %% \begin{center} %% Git: \input{vcline.tex} %% \end{center} %% \immediate\write18{echo ' (stale)' >> vcline.tex} %% \par} \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 : 1h30 \vfill {\noindent\tiny \immediate\write18{sh ./vc > vcline.tex} Git: \input{vcline.tex} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pagebreak % % % \exercice On s'intéresse dans cet exercice au jeu de \emph{Hackenbush impartial en arbre}, défini comme suit. L'état du jeu est 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.}). Deux joueurs alternent, et chacun, quand vient son tour, choisit une arête de l'arbre 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). Le jeu se termine lorsque plus aucun coup n'est possible (c'est-à-dire que l'arbre est réduit à sa seule racine), auquel cas, selon la convention habituelle, le joueur qui ne peut plus jouer a perdu. \begin{center} \begin{tikzpicture}[baseline=0] \fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; \node (P1) at (0,1) {}; \node (P2) at (-1.5,2) {}; \node (P3) at (-2.0,3) {}; \node (P4) at (-1.0,3) {}; \node (P5) at (1.5,2) {}; \node (P6) at (0.75,3) {}; \node (P7) at (1.5,3) {}; \node (P8) at (2.25,3) {}; \node (P9) at (1.75,1) {}; \end{scope} \begin{scope}[line width=1.5pt] \draw (P0) -- (P1); \draw (P1) -- (P2); \draw (P1) -- (P5); \draw (P2) -- (P3); \draw (P2) -- (P4); \draw (P5) -- (P6); \draw (P5) -- (P7); \draw (P5) -- (P8); \draw (P0) -- (P9); \end{scope} \begin{scope}[line width=3pt,red] \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] (-1.5,0) rectangle (1.5,-0.2); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; \node (P1) at (0,1) {}; \node (P2) at (-1.5,2) {}; \node (P3) at (-2.0,3) {}; \node (P4) at (-1.0,3) {}; \node (P9) at (1.75,1) {}; \end{scope} \begin{scope}[line width=1.5pt] \draw (P0) -- (P1); \draw (P1) -- (P2); \draw (P2) -- (P3); \draw (P2) -- (P4); \draw (P0) -- (P9); \end{scope} \end{tikzpicture} \end{center} (1) Expliquer pourquoi une position de ce jeu peut être représentée comme une somme de nim de différents jeux du même type. Plus exactement, soit $T$ un arbre 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$ (avec une arête entre $x$ et $y_i$) : expliquer pourquoi la position (représentée par l'arbre) $T$ est la somme de nim de (celles représentées par) $T'_1,\ldots,T'_r$. Qu'en déduit-on sur la valeur de Grundy de la position $T$ ? \smallbreak Indépendamment de ce qui précède, on va considérer une nouvelle opération sur les jeux : si $G$ est un jeu combinatoire impartial, vu comme un graphe orienté (bien-fondé), on définit un jeu noté $*{:}G$ défini en ajoutant une unique position à $G$ comme on va l'expliquer. Pour chaque position $z$ de $G$ il y a une position notée $*{:}z$ de $*{:}G$, et il y a une unique autre position, notée $0$, dans $*{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête $*{:}z\, \to \, *{:}z'$ dans $*{:}G$, et il y a de plus une arête $*{:}z\, \to 0$ dans $*{:}G$ pour chaque $z$ (en revanche, $0$ est un puits, c'est-à-dire qu'aucune arête n'en part) ; la position initiale de $*{:}G$ est $*{:}z_0$ où $z_0$ est celle de $G$. De façon plus informelle, pour jouer au jeu $*{:}G$, chaque joueur peut soit faire un coup normal ($*{:}z\, \to \, *{:}z'$) dans $G$, soit appliquer un coup « destruction totale » $*{:}z\, \to 0$ qui fait terminer immédiatement le jeu (et celui qui l'applique a gagné\footnote{Ce jeu considéré tout seul n'est donc pas très amusant puisqu'on a toujours la possibilité de gagner instantanément.}). \smallbreak (2) Montrer par induction bien-fondée que si $G$ est un jeu combinatoire impartial (bien-fondé) de valeur de Grundy $\alpha$, alors $*{:}G$ a pour valeur de Grundy $1+\alpha$. \smallbreak (3) On revient au jeu de Hackenbush impartial en arbre. Soit $T$ un arbre de racine $y$ et $T'$ l'arbre obtenu en ajoutant une nouvelle racine $x$ à $T$, c'est-à-dire que les sommets de $T'$ sont ceux de $T$ plus $x$, qui en est la racine, avec une arête entre $x$ et $y$. Expliquer pourquoi le jeu de Hackenbush représenté par $T'$ s'obtient par la construction « $*{:}$ » considérée en (2) à partir de celui représenté par $T$. Qu'en déduit-on sur la valeur de Grundy de la position $T'$ par rapport à celle de $T$ ? \smallbreak (4) Déduire des questions précédentes une méthode pour calculer la valeur de Grundy d'une position quelconque au Hackenbush impartial en arbre. \smallbreak (5) Quelle est la valeur de Grundy de la position représentée ci-dessous ? (Il s'agit de la position utilisée en exemple plus haut.) Quel coup préconiseriez-vous dans cette situation ? \begin{center} \begin{tikzpicture}[baseline=0] \fill [gray!50!white] (-1.5,0) rectangle (1.5,-0.2); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; \node (P1) at (0,1) {}; \node (P2) at (-1.5,2) {}; \node (P3) at (-2.0,3) {}; \node (P4) at (-1.0,3) {}; \node (P5) at (1.5,2) {}; \node (P6) at (0.75,3) {}; \node (P7) at (1.5,3) {}; \node (P8) at (2.25,3) {}; \node (P9) at (1.75,1) {}; \end{scope} \begin{scope}[line width=1.5pt] \draw (P0) -- (P1); \draw (P1) -- (P2); \draw (P1) -- (P5); \draw (P2) -- (P3); \draw (P2) -- (P4); \draw (P5) -- (P6); \draw (P5) -- (P7); \draw (P5) -- (P8); \draw (P0) -- (P9); \end{scope} \end{tikzpicture} \end{center} \smallbreak (La question qui suit est indépendante des questions précédentes.) (6) On remarque que la construction $*{:}G$ définie avant la question (2) peut se définir de façon identique lorsque $G$ est un jeu partisan, en donnant à une arête $*{:}z\, \to \, *{:}z'$ la même couleur que $z\to z'$ et à une arête $*{:}z\, \to 0$ la couleur verte (ce qui signifie : à la fois bleue et rouge). En décrivant une stratégie, montrer que si $G \geq H$ on a aussi $*{:}G \geq *{:}H$, et en déduire que si $G\doteq H$ alors $*{:}G \doteq *{:}H$ (où $\doteq$ désigne l'égalité au sens de Conway des jeux partisans). % % % \exercice On considère le jeu en forme normale suivant : \emph{trois} joueurs (Alice, Bob et Charlie, par exemple) choisissent indépendamment les uns des autres un élément de l'ensemble $\{\mathtt{0},\mathtt{1}\}$ : \begin{itemize} \item s'ils ont tous les trois choisi la même option, ils gagnent tous $0$, \item si l'un d'entre eux a choisi une option différente des deux autres, celui qui a choisi cette option gagne $2$ et chacun des deux autres gagne $-1$. \end{itemize} Il sera utile de remarquer que les joueurs ont des rôles complètement symétriques, et que les options sont également symétriques. (Attention, même si la somme des gans des trois joueurs vaut toujours $0$, ce n'est pas un « jeu à somme nulle » au sens classique, car ces derniers ne sont définis que pour \emph{deux} joueurs.) \smallbreak (1) Donner le tableau des gains du jeu considéré. (On choisira une façon raisonnable de présenter un tableau à trois entrées, par exemple comme plusieurs tableaux à deux entrées mis côte à côte.) \smallbreak Si $p \in [0;1]$, on notera simplement $p$ la stratégie mixte d'un joueur qui consiste à choisir $\mathtt{1}$ avec probabilité $p$ et $\mathtt{0}$ avec probabilité $1-p$. (2) Vérifier que l'espérance de gain d'Alice si elle joue selon la stratégie mixte $p$ tandis que Bob joue selon la stratégie mixte $q$ et Charlie selon la stratégie mixte $r$ vaut : $-2pq -2pr +4qr + 2p - q -r$. (Ici, $p,q,r$ sont trois réels entre $0$ et $1$.) \smallbreak (3) On se demande à quelle condition sur la stratégie mixte $q$ jouée par Bob et la stratégie mixte $r$ jouée par Charlie les options $\mathtt{0}$ et $\mathtt{1}$ d'Alice sont indifférentes pour elle (c'est-à-dire, lui apportent la même espérance de gain). Montrer que c'est le cas ssi $q + r = 1$. \smallbreak (4) Déduire de la question (3) que si un profil $(p,q,r)$ de stratégies mixtes est un équilibre de Nash et que $0