diff options
| -rw-r--r-- | controle-20220413.tex | 441 | ||||
| -rw-r--r-- | controle-20230417.tex | 793 | ||||
| -rw-r--r-- | notes-mitro206.tex | 2 |
3 files changed, 1235 insertions, 1 deletions
diff --git a/controle-20220413.tex b/controle-20220413.tex new file mode 100644 index 0000000..5c2448d --- /dev/null +++ b/controle-20220413.tex @@ -0,0 +1,441 @@ +%% 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} 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} diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 7d20177..d5fb37f 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1947,7 +1947,7 @@ devient de maximiser $v_+ - v_-$ sous les contraintes \[-\sum_{a\in A_1} x_a \leq -1\] \[(\forall b\in A_2)\;v_+ - v_- - \sum_{a \in A_1} u(a,b)\, x_a \leq 0\] Le problème dual (minimiser ${^{\mathrm{t}}\textbf{q}} y$ sous les -contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{q}}$ +contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{p}}$ et $y\geq 0$) est alors de minimiser $w_+ - w_-$ sous les contraintes \[w_+\geq 0,\; w_- \geq 0,\;\; (\forall b\in A_2)\;y_b \geq 0\] \[\sum_{b\in A_2} y_b \geq 1\] |