diff options
Diffstat (limited to 'controle-20230417.tex')
-rw-r--r-- | controle-20230417.tex | 793 |
1 files changed, 793 insertions, 0 deletions
diff --git a/controle-20230417.tex b/controle-20230417.tex new file mode 100644 index 0000000..fce95a1 --- /dev/null +++ b/controle-20230417.tex @@ -0,0 +1,793 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\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{\dur}{\operatorname{dur}} +\newcommand{\fuzzy}{\mathrel{\|}} +% +\newcommand{\dblunderline}[1]{\underline{\underline{#1}}} +% +\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{17 avril 2023} +\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é. De plus, il ne sera pas nécessaire +de traiter la totalité pour avoir la note maximale. + +\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} : $5+5+5+7$ (sur $20$) + +\ifcorrige +Ce corrigé comporte 8 pages (page de garde incluse). +\else +Cet énoncé comporte 4 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 + +On considère le jeu de nim éventuellement transfini. (On rappelle +qu'il est défini de la manière suivante : une position du jeu est un +tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a +« $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à +décroître strictement \emph{un et un seul} des $\alpha_i$, autrement +dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers +$(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis +à la place de $\alpha_i$.) + +Pour chacune des positions suivantes, dire si c'est une position P +(c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N +(c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce +dernier cas, donner un coup gagnant possible pour le joueur en +question. + +(a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne +avec $2$, et une ligne avec $3$) + +\begin{corrige} +On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si +bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la +position est $0$, et c'est donc une position P. +\end{corrige} + +(b) $(3,6,9)$ + +\begin{corrige} +On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus +2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6 +\oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de +la position est $12$, et c'est donc une position N. + +Pour trouver un coup gagnant, c'est-à-dire un coup vers une +position P, on cherche à annuler la valeur de Grundy : autrement dit, +on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n +\oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus +12 < n$. On vérifie facilement que la seule possibilité est de +réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$ +bâtonnets. Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$. +\end{corrige} + +(c) $(\omega,\omega2,\omega3)$ + +\begin{corrige} +En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 = +2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on +a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de +Grundy de la position est $0$, et c'est donc une position P. +\end{corrige} + +(d) $(\omega,\omega^2,\omega^3)$ + +\begin{corrige} +En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 = +2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc +$\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} + +2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de +Grundy de la position est $\gamma \neq 0$, et c'est cdonc une +position N. + +Comme dans la question (b), on cherche à annuler la valeur de Grundy, +autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne +par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 + +\omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2} +\oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit. +On vérifie facilement que la seule possibilité est de réduire la ligne +ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 + +\omega$ bâtonnets. Bref, le seul coup gagnant est +$(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$. +\end{corrige} + +(e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$ + +\begin{corrige} +En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a +$\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} = +2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega} += 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} = +2^{\omega^\omega}$. Le raisonnement est alors exactement analogue à +la question (d) (car la seule chose qui importe dans cette question +ait qu'on ait affaire à trois puissances de $2$ distinctes) : la +valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} + +2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega + +\omega \neq 0$ donc c'est une position N, et le seul coup gagnant est +$(\omega,\omega^\omega,\omega^{\omega^\omega}) \to +(\omega,\omega^\omega,\omega^\omega + \omega)$. +\end{corrige} + +(f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0 +< \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre +premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme + la limite, c'est-à-dire la borne supérieure, de la suite + $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 = + (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1 + = \omega^{(\varepsilon_n) + 1}$ et $u_2 = + \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas + besoin de ce fait.} vérifiant $\varepsilon = \omega^\varepsilon$. + +\begin{corrige} +Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a +$\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} = +2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} = +2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} = +2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement +vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$). +Le raisonnement est alors exactement analogue aux questions (d) et (e) +(car la seule chose qui importe dans ces questions ait qu'on ait +affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de +la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} + +2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq +0$ donc c'est une position N, et le seul coup gagnant est +$(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1, +\varepsilon_2, \varepsilon_2 + \varepsilon_1)$. +\end{corrige} + +(g) Donner un exemple de position N du jeu de nim (de préférence fini) +avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les +$\alpha_i$ sont deux à deux distincts), où il existe strictement plus +qu'un coup gagnant pour le joueur qui doit jouer. (Pour indication, +ceci est possible à partir de trois lignes de bâtonnets.) + +\begin{corrige} +On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de +bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle +qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement +inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la +question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus +n_3$ et de façon analogue pour les trois autres. On cherche donc, par +exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$. +Ceci n'est pas difficile en prenant par exemple pour $n_1$ une +puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et +de $n_3$ mais telle qu'en l'enlevant on obtienne des nombres +strictement plus petits. Par exemple, la position $(2,6,7)$ (de +valeur de Grundy $2\oplus 6\oplus 7 = 3 =: g$) admet des coups +gagnants vers $(2,5,7)$ ou $(2,6,4)$ ou même $(1,6,7)$. +\end{corrige} + + +% +% +% + +\exercice + +Si $G$ est un graphe orienté bien-fondé (qu'on peut considérer comme +l'ensemble des positions d'un jeu combinatoire auquel il ne manque que +l'information, sans pertinence ici, de la position initiale), on +rappelle qu'on a défini la fonction rang +\[ +\rk(x) := \sup\nolimits^+\{\rk(y) : y\in\outnb(x)\} = \sup\,\{\rk(y)+1 : +y\in\outnb(x)\} +\] +(en notant $\sup^+ S$ le plus petit ordinal strictement supérieur à +tous les ordinaux de $S$ et $\sup S$ le plus petit ordinal supérieur +ou égal à tous les ordinaux de $S$, et $\outnb(x)$ l'ensemble des +voisins sortants de $x$), et la fonction de Grundy +\[ +\gr(x) := \mex\,\{\gr(y) : y\in\outnb(x)\} +\] +(où $\mex S$ désigne le plus petit ordinal qui n'est pas dans $S$), +— ces définitions ayant bien un sens par induction bien-fondée. La +première mesure en quelque sorte la durée du jeu si les deux joueurs +coopèrent pour le faire durer aussi longtemps que possible, et la +seconde nous donne notamment l'information de quel joueur a une +stratégie gagnante. + +On va maintenant définir une fonction qui mesure en quelque sorte la +durée du jeu si le joueur perdant cherche à perdre aussi lentement que +possible tandis que le joueur gagnant cherche à gagner aussi vite que +possible. Précisément, on pose +\[ +\left\{ +\begin{array}{ll} +\dur(x) := \sup\,\{\dur(y)+1 : y\in\outnb(x)\} +&\;\;\text{si $\gr(x) = 0$}\\ +\dur(x) := \min\,\{\dur(y)+1 : y\in\outnb(x)\text{~et~}\gr(y)=0\} +&\;\;\text{si $\gr(x) \neq 0$}\\ +\end{array} +\right. +\] +(où $\min S$ désigne le plus petit ordinal de $S$, si $S$ est un +ensemble non-vide d'ordinaux). + +(1) Expliquer pourquoi cette définition a bien un sens (on +prendra garde au fait que $\min\varnothing$ n'est pas défini). + +\begin{corrige} +Lorsque $\gr(x) \neq 0$, il existe au moins un voisin sortant $y \in +\outnb(x)$ tel que $\gr(y) = 0$ (car le $\mex$ est la plus petite +valeur exclue: si un tel $y$ n'existait pas, le $\mex$ serait $0$) : +ceci assure que le $\min$ dans la deuxième ligne de la définition +porte toujours sur un ensemble non-vide. + +En-dehors de ce fait, la définition ne pose pas de problème : le +$\sup$ d'un ensemble d'ordinaux existe toujours, et la récursivité de +la définition est légitime par induction bien-fondée, c'est-à-dire que +$\dur(x)$ peut faire appel aux valeurs de $\dur(y)$ pour des voisins +sortants $y$ de $x$. (Le fait de faire appel à $\gr(y)$ n'est pas un +problème car on sait que $\gr$ est bien défini, et la distinction en +cas est légitime de toute manière.) +\end{corrige} + +(2) Expliquer rapidement et informellement pourquoi $\dur(x)$ +correspond bien à l'explication intuitive qu'on a donnée. + +\begin{corrige} +Quand $x$ est une position avec $\gr(x) = 0$, c'est-à-dire une +position P, le joueur qui doit jouer est le joueur perdant (n'ayant +pas de stratégie gagnante) : il joue donc vers une position $y$ le +faisant perdre le plus lentement possible, c'est-à-dire avec $\dur(y)$ +aussi grand que possible, d'où la définition $\dur(x) = +\sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ dans ce cas (le $+1$ sert à +compter le coup joué par ce joueur). + +Au contraire, lorsque $\gr(x) \neq 0$, c'est-à-dire que $x$ est une +position N, le joueur qui doit jouer est le joueur gagnant : il joue +donc vers une position $y$ le faisant gagner le plus rapidement +possible, c'est-à-dire avec $\dur(y)$ aussi petit que possible parmi +les coups $x\to y$ gagnants, autrement dit ceux pour lesquels $\gr(y) += 0$, d'où la définition $\dur(x) = \min\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\}$ dans ce cas (le $+1$ sert à +compter le coup joué par ce joueur). +\end{corrige} + +(3) Sur le graphe $G$ représenté ci-dessous, calculer chacune des +fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à +étiqueter les sommets) : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,circle] {A}; +\node (nB) at (0bp,-40bp) [draw,circle] {B}; +\node (nC) at (40bp,0bp) [draw,circle] {C}; +\node (nD) at (40bp,-40bp) [draw,circle] {D}; +\node (nE) at (80bp,0bp) [draw,circle] {E}; +\node (nF) at (80bp,-40bp) [draw,circle] {F}; +\node (nG) at (120bp,-40bp) [draw,circle] {G}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip +Si on joue à partir du sommet A comme position initiale et que, comme +suggéré dans la définition de $\dur$, le joueur perdant cherche à +perdre aussi lentement que possible tandis que le joueur gagnant +cherche à gagner aussi vite que possible, quelle sera le déroulement +du jeu ? + +\begin{corrige} +Les sommets ont été fort sympathiquement étiquetés dans un ordre +compatible avec le rang (tri topologique), c'est-à-dire que chaque +arête pointe vers un sommet situé strictement après dans l'ordre +alphabétique. On effectue donc les calculs dans l'ordre alphabétique +inversé. On trouve, pour le rang : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,circle] {$4$}; +\node (nB) at (0bp,-40bp) [draw,circle] {$3$}; +\node (nC) at (40bp,0bp) [draw,circle] {$3$}; +\node (nD) at (40bp,-40bp) [draw,circle] {$2$}; +\node (nE) at (80bp,0bp) [draw,circle] {$2$}; +\node (nF) at (80bp,-40bp) [draw,circle] {$1$}; +\node (nG) at (120bp,-40bp) [draw,circle] {$0$}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip + +Pour la valeur de Grundy : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,circle] {$0$}; +\node (nB) at (0bp,-40bp) [draw,circle] {$1$}; +\node (nC) at (40bp,0bp) [draw,circle] {$1$}; +\node (nD) at (40bp,-40bp) [draw,circle] {$0$}; +\node (nE) at (80bp,0bp) [draw,circle] {$2$}; +\node (nF) at (80bp,-40bp) [draw,circle] {$1$}; +\node (nG) at (120bp,-40bp) [draw,circle] {$0$}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip + +Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à +suivre, on a entouré en double les sommets de valeur de Grundy $0$) : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,double,circle] {$4$}; +\node (nB) at (0bp,-40bp) [draw,circle] {$1$}; +\node (nC) at (40bp,0bp) [draw,circle] {$3$}; +\node (nD) at (40bp,-40bp) [draw,double,circle] {$2$}; +\node (nE) at (80bp,0bp) [draw,circle] {$1$}; +\node (nF) at (80bp,-40bp) [draw,circle] {$1$}; +\node (nG) at (120bp,-40bp) [draw,double,circle] {$0$}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip + +Si on joue à partir de la position A, le premier joueur, appelons-la +Alice, est en position perdante car la valeur de Grundy est nulle, et +va jouer vers C car c'est ce qui maximise la fonction $\dur$ ; son +adversaire, appelons-le Bob, joue alors vers D car c'est le seul coup +gagnant, après quoi Alice joue vers F (seul coup possible) et Bob joue +vers G. +\end{corrige} + +(4) Montrer que, dans n'importe quel graphe $G$ bien-fondé, et pour +n'importe quel sommet $x$ de $G$, on a $\dur(x) \leq \rk(x)$. + +\begin{corrige} +On montre par induction bien-fondée que $\dur(x) \leq \rk(x)$. On +peut donc faire l'hypothèse qu'on sait que $\dur(y) \leq \rk(y)$ pour +tout voisin sortant $y \in \outnb(x)$ (hypothèse d'induction). Dans +le cas où $\gr(x) = 0$, on a $\dur(x) = \sup\,\{\dur(y)+1 : +y\in\outnb(x)\}$, qui est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\}$ +par hypothèse d'induction (il est clair qu'augmenter au sens large +tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens +large), et ceci vaut $\rk(x)$ par définition. Dans le cas où $\gr(x) +\neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\}$ de façon évidente ($\min S \leq \sup S$ est clair), +et pour la même raison que précédemment, ceci est $\leq +\sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$. +\end{corrige} + + +% +% +% + +\exercice + +Soit $G$ un graphe orienté dont l'ensemble des sommets est (au plus) +dénombrable, et soit $x_0$ un sommet de $G$. (Il n'y a pas d'autre +hypothèse sur $G$, par exemple on ne suppose pas que $G$ est +bien-fondé.) + +On considère le jeu suivant. Deux joueurs s'affrontent, qu'on +appellera \emph{le Fugueur} et \emph{le Borneur}. Le Fugueur +commence, après quoi ils jouent tour à tour. En partant de $x_0$, +chaque joueur, quand vient son tour, choisit un voisin sortant de la +position actuelle $x$ \emph{ou bien} choisit de conserver $x$ ; +autrement dit, il choisit un élément de $\outnb(x) \cup \{x\}$. (Pour +être parfaitement clair : au premier tour, le Fugueur choisit $x_1 \in +\outnb(x_0) \cup \{x_0\}$, puis le Borneur choisit $x_2 \in +\outnb(x_1) \cup \{x_1\}$, et ainsi de suite.) Le jeu dure infiniment +longtemps (manifestement, les règles permettent toujours à chaque +joueur de faire un coup). Au bout d'un nombre infini de coups, on +considère la suite $(x_n)_{n\in\mathbb{N}}$ de toutes les positions +traversées : +\begin{itemize} +\item si cette suite est d'image finie (c'est-à-dire que l'ensemble + $\{x_n : n\in\mathbb{N}\}$ de toutes les positions traversées est + fini), alors le Borneur a gagné ; +\item sinon, le Fugueur a gagné. +\end{itemize} + +(1) Montrer, en appliquant un des résultats du cours, que l'un des +joueurs a nécessairement une stratégie gagnante (on ne demande pas de +préciser lequel). On pourra préalablement montrer que pour toute +partie $F \subseteq G$, la partie $F^{\mathbb{N}} \subseteq +G^{\mathbb{N}}$ est \emph{fermée} (pour la topologie sur +$G^{\mathbb{N}}$ produit de la topologie +discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}), et +en déduire une propriété de l'ensemble +$\bigcup_{F\text{~fini~}\subseteq G} F^{\mathbb{N}}$ réunion des +$F^{\mathbb{N}}$ où $F$ parcourt toutes les parties \emph{finies} +de $G$. + +\begin{corrige} +Pour commencer, montrons que si $F$ est une partie de $G$ alors +$F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée. Ceci revient à +montrer que son complémentaire est ouvert, autrement dit, que si +$\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, +alors il existe un voisinage fondamental de $\dblunderline{x}$ qui ne +rencontre pas $F^{\mathbb{N}}$. Or si $\dblunderline{x} \in +G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, c'est qu'elle a une +valeur $x_\ell$ qui n'est pas dans $F$, et toute suite commençant par +$x_0,\ldots,x_\ell$ n'est pas dans $F^{\mathbb{N}}$, c'est-à-dire que +le voisinage fondamental $V_{\ell+1}(\dblunderline{x})$ est inclus +dans le complémentaire de $F^{\mathbb{N}}$. Ceci achève de montrer +que $F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée. + +Maintenant, l'ensemble $\mathscr{F}$ des parties finies d'un ensemble +(au plus) dénombrable, en l'occurrence, $G$, est (au plus) +dénombrable. Ce fait peut être tenu pour acquis, mais rappelons +pourquoi il est vrai : en effet, si $G = \{g_i : i\in\mathbb{N}\}$, +alors on peut par exemple énumérer $\mathscr{F}$ à travers les +écritures binaires, ou plus précisément, $\mathscr{F} = \{F_n : +n\in\mathbb{N}\}$ où $F_n$ désigne la partie finie +$\{g_{i_0},\ldots,g_{i_r}\}$ lorsque $n = 2^{i_0} + \cdots + 2^{i_r}$ +avec $i_0,\ldots,i_r$ entiers naturels distincts (autrement dit, $F_0 += \varnothing$, $F_1 = \{g_0\}$, $F_2 = \{g_1\}$, $F_3 = \{g_0,g_1\}$, +etc.). Peu importe le fait qu'il y ait des répétitions dans +l'énumération $F_n$ (un ensemble surjecté par $\mathbb{N}$ est encore +dénombrable). + +Ceci nous permet de dire que $\bigcup_{F\text{~fini~}\subseteq G} +F^{\mathbb{N}}$, autrement dit $\bigcup_{F \in \mathscr{F}} +F^{\mathbb{N}}$, est une réunion dénombrable de fermés +dans $G^{\mathbb{N}}$. Comme un fermé est borélien, c'est une réunion +dénombrable de boréliens, donc c'est encore un borélien. + +Enfin, remarquons que dire que l'ensemble $\{x_n : n\in\mathbb{N}\}$ +est fini revient à dire qu'il est inclus un ensemble fini $F$, +autrement dit, que la suite $\dblunderline{x} = (x_n)$ appartient à +$F^{\mathbb{N}}$ pour un certain ensemble fini $F$, ou, ce qui revient +au même, qu'elle appartient à $\bigcup_{F \in \mathscr{F}} +F^{\mathbb{N}}$. + +On a donc affaire à un jeu de Gale-Stewart défini par l'ensemble de +suites $B := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien (ou +par son complémentaire $A := G^{\mathbb{N}} \setminus B$ si on prend +le point de vue du Fugueur). Le théorème de détermination borélienne +de Martin assure que l'un des joueurs a forcément une stratégie +gagnante. +\end{corrige} + +(2) Indépendamment de la question précédente, donner un exemple de +couple $(G,x_0)$ pour lequel le Borneur possède une stratégie gagnante +à ce jeu. Donner un exemple pour lequel le Fugueur en possède une. +(On cherchera à donner des exemples aussi simples que possibles.) + +\begin{corrige} +Si $G$ est le graphe formé du seul sommet $x_0$, alors le Borneur +gagne trivialement (la suite sera la suite constante). + +Si $G$ est le graphe formé des entiers naturels avec une arête $i \to +j$ lorsque $i<j$ (autrement dit des petits entiers naturels vers les +grands), ou même seulement $i \to i+1$, alors le Fugueur a une +stratégie gagnante consistant à jouer de $i$ vers $i+1$, ce qui assure +que la suite $(x_{2i+1})$ des positions choisies par le Fugueur est +strictement croissante quoi que fasse le Borneur (il ne peut pas +revenir en arrière), et notamment, elle n'est pas d'image finie. +\end{corrige} + + +% +% +% + +\exercice + +On considère une variante \emph{à somme (possiblement) non-nulle} de +Pierre-Papier-Ciseaux, à savoir le jeu en forme normale défini par la +matrice de gain suivante : +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&$U$&$V$&$W$\\\hline +$U$&$x,x$&$-1,+1$&$+1,-1$\\ +$V$&$+1,-1$&$x,x$&$-1,+1$\\ +$W$&$-1,+1$&$+1,-1$&$x,x$\\ +\end{tabular} +\end{center} +où $x$ est un réel et, pour plus de commodité, on a écrit $U$ pour +« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ». (La ligne +correspond à l'option choisie par Alice, la colonne à l'option de Bob, +et chaque case indique le gain d'Alice suivi du gain de Bob.) + +Le but de l'exercice est d'étudier les équilibres de Nash de ce jeu. + +(On prendra bien note, pour simplifier les raisonnements en cas, du +fait que les options ont une symétrie cyclique\footnote{C'est-à-dire + que remplacer $U$ par $V$ et $V$ par $W$ et $W$ par $U$ ne change + rien au jeu.}, et que les joueurs ont eux aussi des rôles +symétriques.) + +(1) Considérons le profil de stratégies mixtes dans lequel les deux +joueurs choisissent chacun chaque option avec probabilité +$\frac{1}{3}$ (c'est-à-dire la stratégie qui est optimale dans le cas +à somme nulle). Pour quelle(s) valeur(s) de $x$ ce profil est-il un +équilibre de Nash ? + +\begin{corrige} +Pour des raisons de symétrie, si l'un des joueurs joue cette stratégie +mixte $\frac{1}{3}U + \frac{1}{3}V + \frac{1}{3}W$, le gain espéré de +chacun des deux joueurs est le même quelle que soit la stratégie pure, +donc aussi mixte, de l'autre joueur. Cette valeur se calcule +d'ailleurs aisément (comme somme des trois colonnes, ou des trois +lignes, de la matrice de gains, affectées des +coefficients $\frac{1}{3}$) : c'est $\frac{1}{3}x$ ; mais la seule +chose qui importe est que l'adversaire ait le même gain espéré quelle +que soit la stratégie pure, donc aussi mixte, qu'il choisit : il n'a +donc pas intérêt à changer unilatéralement sa stratégie. Il s'agit +donc \emph{toujours} d'un équilibre de Nash, quelle que soit la valeur +de $x$. +\end{corrige} + +\emph{On suppose dorénavant que $x<-1$.} + +(2) Existe-t-il un équilibre de Nash dans lequel Alice joue purement +$U$ ? (On raisonnera les options pouvant être dans le support de la +stratégie de Bob en réponse.) En déduire tous les équilibres de Nash +dans lesquels au moins un joueur joue une stratégie pure. + +\begin{corrige} +Si Alice joue purement $U$, les gains de Bob pour les différentes +stratégies pures de sa réponse sont $x$ pour $U$, $+1$ pour $V$ et +$-1$ pour $W$ d'après la matrice de gains. Comme $+1 > -1 > x$, la +seule option qui peut faire partie du support d'une meilleure réponse +de Bob est $V$, autrement dit, si Alice joue purement $U$ dans un +équilibre de Nash, Bob répond forcément purement $V$. Mais par le +même raisonnement (compte tenu de la symétrie cyclique des options et +de la symétrie des joueurs), si Bob joue purement $V$, Alice joue $W$ +(et pas $U$ comme supposé). Il ne peut donc pas y avoir d'équilibre +de Nash dans lequel Alice joue purement $U$. Et de nouveau par +symétrie cyclique des options et symétrie des joueurs, il ne peut y +avoir aucun équilibre de Nash dans lequel un joueur jouerait une +stratégie pure. +\end{corrige} + +(3) Dans cette question et la suivante, envisageons un équilibre de +Nash dans lequel Alice joue la stratégie mixte $pU + (1-p)V$ avec +$0<p<1$. Supposons dans cette question que Bob réponde avec un une +stratégie mixte ayant elle aussi $\{U,V\}$ comme support. Montrer que +$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$. En +utilisant le fait que $\frac{x^2+1}{2x} < -\frac{1}{x}$ lorsque $x<-1$ +(qu'on admettra pour ne pas perdre son temps en calculs inutiles), en +déduire qu'un tel équilibre de Nash n'existe pas. + +\begin{corrige} +Si Alice joue $pU + (1-p)V$, les gains espérés de Bob pour les +différences stratégies pures de sa réponse sont $px-(1-p) = +-1+(x+1)p$ pour $U$, $p + (1-p)x = x-(x-1)p$ pour $V$ et $-p + (1-p) = +1-2p$ pour $W$. Si une meilleure réponse de Bob a $\{U,V\}$ comme +support, ces deux options doivent apporter le même gain espéré, +c'est-à-dire qu'on doit avoir $-1+(x+1)p = x-(x-1)p$, ce qui équivaut +à $p = \frac{x+1}{2x}$, et le gain en question est $\frac{x^2+1}{2x}$, +tandis que le gain espéré pour $W$ est alors $1-2p = -\frac{1}{x}$. +D'après l'inégalité $\frac{x^2+1}{2x} < -\frac{1}{x}$, l'option $W$ +fournit un meilleur gain espéré pour Bob, donc $\{U,V\}$ ne peut pas +être le support d'une meilleure réponse de Bob à $pU + (1-p)V$ +d'Alice. +\end{corrige} + +(4) On considère toujours un équilibre de Nash dans lequel Alice joue +la stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons maintenant +que Bob réponde avec une stratégie mixte ayant (au moins) $U$ et $W$ +dans son support support. Montrer que $p = \frac{2}{x+3}$ (et +que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ lorsque +$-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (de nouveau, on +admettra ces faits pour ne pas perdre de temps en calculs), en déduire +qu'un tel équilibre de Nash n'existe pas. + +\begin{corrige} +On a dit dans la question (3) que si Alice joue $pU + (1-p)V$, les +gains espérés de Bob pour les différences stratégies pures de sa +réponse sont $px-(1-p) = -1+(x+1)p$ pour $U$, $p + (1-p)x = +x-(x-1)p$ pour $V$ et $-p + (1-p) = 1-2p$ pour $W$. Si une meilleure +réponse de Bob a $U$ et $W$ dans son support, ces deux options doivent +apporter le même gain espéré, c'est-à-dire qu'on doit avoir $-1+(x+1)p += 1-2p$, ce qui équivaut à $(x+3)p = 3$, donc $x\neq 3$ et $p = +\frac{2}{x+3}$. D'après les inégalités admises, $p$, qui devrait être +entre $0$ et $1$, ne l'est jamais si $x<-1$, donc un tel équilibre de +Nash n'existe pas. +\end{corrige} + +(5) Expliquer soigneusement pourquoi les questions (2) à (4) montrent +que dans tout équilibre de Nash du jeu considéré, les deux joueurs +jouent une stratégie mixte ayant $\{U,V,W\}$ comme support (i.e., +aucun ensemble strictement plus petit n'est possible). + +\begin{corrige} +On a vu en (2) qu'il n'existe aucun équilibre de Nash dans lequel un +joueur joue une stratégie pure. Supposons maintenant un équilibre de +Nash dans lequel un joueur a deux options dans son support. Par +symétrie, sans perte de généralité, on peut supposer que c'est Alice +et que ces deux options sont $U$ et $V$. Comme les stratégies pures +sont exclues, les supports possibles de la réponse de Bob sont : +$\{U,V\}$, $\{U,W\}$, $\{V,W\}$ et $\{U,V,W\}$. Dans la question (3) +on a exclu $\{U,V\}$ ; dans la question (4), on a exclu $\{U,W\}$ et +$\{U,V,W\}$. Reste le cas où le support de la stratégie de Bob est +$\{V,W\}$ (tandis que celui d'Alice est, on le rappelle, $\{U,V\}$). +Mais quitte à effectuer une symétrie cyclique des options ($U\to W\to +V\to U$) et échanger les joueurs, cela revient au cas où le support de +la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : or +on a déjà exclu ce cas. Il ne reste donc aucune possibilité. +\end{corrige} + +(6) Envisageons maintenant un équilibre de Nash dans lequel Alice joue +une stratégie mixte $pU + p'V + (1-p-p')W$ avec $p>0$, $p'>0$ et +$1-p-p'>0$ et Bob répond par une stratégie ayant elle aussi +$\{U,V,W\}$ comme support. Écrire un système de deux équations +linéaires vérifié par $p,p'$, justifier que ce système est +non-dégénéré et conclure. Quels sont tous les équilibres de Nash du +jeu ? + +\begin{corrige} +Si Alice joue $pU + p'V + (1-p-p')W$, les gains espérés de Bob pour +les différences stratégies pures de sa réponse sont $px - p' + +(1-p-p') = 1 + (x-1)p - 2p'$ pour $U$, $p + p' x - (1-p-p') = -1 + 2p ++ (x+1)p'$ pour $V$ et $-p + p' + (1-p-p')x = x -(x+1)p - +(x-1)p'$ pour $W$. Si une meilleure réponse de Bob a $\{U,V,W\}$ +comme support, ces trois options doivent apporter le même gain espéré, +c'est-à-dire que $1 + (x-1)p - 2p' = -1 + 2p + (x+1)p' = x -(x+1)p - +(x-1)p'$, ou (en soustrayant, disons, le premier membre aux deux +autres) : +\[ +\begin{aligned} +-(x-3)p + (x+3)p' &= 2\\ +- 2xp - (x-3)p' &= -(x-1) +\end{aligned} +\] +Le déterminant de ce système est $(x-3)^2 + 2x(x+3) = 3(x^2+3)$ qui +est non nul quel que soit $x$, donc le système est non-dégénéré : la +solution $p=p'=\frac{1}{3}$ trouvée en (1) est donc la seule solution. + +Bref, on a montré que le seul équilibre de Nash dans lequel les +supports des stratégies d'Alice et Bob sont $\{U,V,W\}$ est celui +décrit en (1) ; comme on a vu en (5) que ceci est la seule possibilité +de support, il s'agit du seul équilibre de Nash du jeu. +\end{corrige} + + + + + +% +% +% +\end{document} |