diff options
-rw-r--r-- | controle-20220413.tex | 441 | ||||
-rw-r--r-- | controle-20230417.tex | 793 | ||||
-rw-r--r-- | controle-20240422.tex | 577 | ||||
-rw-r--r-- | controle-20250626.tex | 1083 | ||||
-rw-r--r-- | notes-mitro206.tex | 2 |
5 files changed, 2895 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/controle-20240422.tex b/controle-20240422.tex new file mode 100644 index 0000000..9350f2a --- /dev/null +++ b/controle-20240422.tex @@ -0,0 +1,577 @@ +%% 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{22 avril 2024} +\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. + +\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 + +\ifcorrige +Ce corrigé comporte 6 pages (page de garde incluse). +\else +Cet énoncé comporte 3 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 + +\textbf{(1)} On considère le jeu en forme normale défini par la +matrice de gain suivante : +\begin{center} +\begin{tabular}{r|cc} +$\downarrow$Alice, Bob$\rightarrow$&$X$&$Y$\\\hline +$X$&$1$&$0$\\ +$Y$&$0$&$2$\\ +\end{tabular} +\end{center} +Un seul nombre a été inscrit dans chaque case car les gains des deux +joueurs sont \emph{égaux}, et c'est ce nombre-là qui est écrit +(attention, il ne s'agit pas d'un jeu à somme nulle, au contraire : au +lieu d'être opposés, les intérêts des deux joueurs sont parfaitement +identiques). + +Étudier et déterminer tous les équilibres de Nash de ce jeu : on +commencera par considérer ceux en stratégies pures, puis par +considérer les cas où un joueur, ou l'autre, ou les deux, joue une +stratégie strictement mixte (i.e., ayant pour support $\{X,Y\}$). + +\begin{corrige} +Si Alice joue (purement) $X$, les options de Bob apportent les gains +$1$ pour $X$ et $0$ pour $Y$, dont la seule meilleure réponse de Bob +est de jouer purement $X$. De même, si Alice joue (purement) $Y$, les +options de Bob apportent les gains $0$ pour $X$ et $2$ pour $Y$, dont +la seule meilleure réponse de Bob est de jouer purement $Y$. Le rôle +des deux joueurs étant symétrique, ceci prouve que, dans un équilibre +de Nash, si l'un joue purement une des deux options, l'autre doit +jouer la même, et ceci donne bien deux équilibres de Nash, $(X,X)$ +(avec gain $1$) et $(Y,Y)$ (avec gain $2$). + +Si Alice joue une stratégie strictement mixte dans un équilibre de +Nash, on vient de voir que Bob joue $pX + (1-p)Y$, l'espérance de gain +d'Alice doit être la même pour les deux options du support de sa +stratégie, c'est-à-dire que $p = 2(1-p)$, donc $p = \frac{2}{3}$. Par +symétrie, Bob joue aussi cette stratégie, et on vérifie que ceci donne +bien un équilibre de Nash, $(\frac{2}{3}X + \frac{1}{3}Y, \; +\frac{2}{3}X + \frac{1}{3}Y)$. +\end{corrige} + +\textbf{(2)} Plus généralement, on considère un jeu de la forme +suivante : les deux joueurs ont le même ensemble d'options, notons-le +$\{X_1,\ldots,X_N\}$, et ils ont le même gain $u_A(a,b) = u_B(a,b)$ +pour $a,b\in \{X_1,\ldots,X_N\}$, et de plus ce gain vaut $0$ lorsque +$b\neq a$ et il vaut $g_i$ lorsque $a = b = X_i$, où tous les $g_i$ +sont des réels strictement positifs ($g_i > 0$). Pour résumer : +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&$X_1$&$\cdots$&$X_N$\\\hline +$X_1$&$g_1$&$\cdots$&$0$\\ +$\vdots$&$\vdots$&$\ddots$&$\vdots$\\ +$X_N$&$0$&$\cdots$&$g_N$\\ +\end{tabular} +\end{center} + +\textbf{(a)} Montrer que, dans un équilibre de Nash d'un jeu comme on +vient de le dire, si $I \subseteq \{X_1,\ldots,X_N\}$ est le +support\footnote{On rappelle que le support d'une stratégie mixte est +l'ensemble des options qu'elle choisit avec une probabilité $>0$.} de +la stratégie d'Alice, le support $J$ de la stratégie de Bob est inclus +dans $I$. (\emph{Indication :} toute option hors de $I$ apporte un +gain espéré nul, donc strictement moins bon que n'importe quelle +combinaison convexe d'options dans $I$.) En déduire par symétrie +que $I=J$. + +\begin{corrige} +Si $X_j \not\in I$, alors l'option $X_j$ apporte un gain nul à Bob, +tandis que toute option $X_i \in I$ apporte un gain strictement +positif (puisque $g_i$ est pondéré avec un coefficient strictement +positif, tout le reste étant nul). Il s'ensuit qu'une meilleure +réponse possible de Bob ne peut pas inclure $X_j$ : elle ne peut donc +inclure que des options dans $I$. Donc $J \subseteq I$. Et par +symétrie des deux joueurs, $I \subseteq J$. Donc finalement $I = J$. +\end{corrige} + +\textbf{(b)} Toujours en considérant un équilibre de Nash d'un tel +jeu, en notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie (mixte) +d'Alice, montrer que les $g_i p_i$ tels que $p_i > 0$ (c'est-à-dire +$X_i \in I$) sont tous égaux entre eux. En déduire par symétrie le +résultat analogue pour la stratégie de Bob, donc qu'elles sont égales. +En déduire qu'il existe au plus $2^N - 1$ équilibres de Nash, un pour +chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$. + +\begin{corrige} +En notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie d'Alice, pour +toute option $X_i \in J = I$ de Bob, le gain espéré de $X_i$ doit être +toujours le même. Or ce gain est $g_i p_i$. Donc tous les $g_i p_i$ +pour $X_i \in I$ sont égaux. C'est-à-dire que les $p_i$ sont +proportionnels aux $\frac{1}{g_i}$ pour $X_i \in I$ (les autres étant +nuls). Ceci détermine la stratégie d'Alice, et par symétrie c'est +aussi celle de Bob. On a donc trouvé $2^N - 1$ équilibres de Nash +potentiels : pour toute partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on +pose calcule $p_i$ comme le quotient de $\frac{1}{g_i}$ par la somme +des $\frac{1}{g_j}$ pour $X_j \in I$ si $X_i \in I$ (et $0$ sinon), et +Alice et Bob jouent chacun $p_1 X_1 + \cdots + p_N X_N$. +\end{corrige} + +\textbf{(c)} Vérifier que les stratégies mixtes trouvées en (b) sont +bien des équilibres de Nash du jeu, et conclure qu'il a exactement +$2^N - 1$ équilibres de Nash, qu'on décrira explicitement. + +\begin{corrige} +Pour chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on a bien +décrit une stratégie mixte pour chacun des deux joueurs (c'est la +même) : on a bien affaire à des réels $p_i$ positifs de somme $1$. Le +gain espéré de $X_j$ contre $p_1 X_1 + \cdots + p_N X_N$ est $0$ si +$X_j \not\in I$ et $g_j p_j$ (qui ne dépend pas de $j$) si $X_j \in +I$ : on ne peut pas faire mieux (avec une stratégie pure, donc a +fortiori avec une stratégie mixte), donc cette stratégie est bien une +meilleure réponse possible contre elle-même, et on a bien affaire à un +équilibre de Nash. + +Pour résumer : tous les équilibres de Nash sont décrits de la façon +suivante : pour une certaine partie non vide $I$ de +$\{X_1,\ldots,X_N\}$, on pose +\[ +\left\{ +\begin{array}{ll} +p_i = \frac{\textstyle 1/g_i}{\textstyle \sum_{X_j\in I}(1/g_j)}&\text{si $p_i\in I$}\\ +p_i = 0&\text{sinon} +\end{array} +\right. +\] +et les deux joueurs jouent $p_1 X_1 + \cdots + p_N X_N$ : ceci est +bien un équilibre de Nash et tous sont de cette forme (et $I$ est bien +déterminé par l'équilibre puisque c'est le support commun des +stratégies des deux joueurs, donc tous les équilibres qu'on vient de +décrire sont distincts). Il y en a donc exactement $2^N - 1$. +\end{corrige} + + +% +% +% + +\exercice + +On considère un jeu de la forme suivante. Soit $A \subseteq +\mathbb{R}$ un ensemble de réels, soit $X \subseteq \mathbb{R}$ un +ensemble \emph{fini} de réels, et soit enfin $b>1$ un réel. (Toutes +ces données sont fixées à l'avance et sont des paramètres définissant +le jeu. Ils sont supposés connus des deux joueurs.) + +Chaque joueur quand vient son tour choisit un élément $x_i \in X$ : +plus exactement, Alice choisit $x_0$, puis Bob choisit $x_1$, puis +Alice choisit $x_2$, et ainsi de suite. Il n'y a aucune contrainte +sur le choix du $x_i$ et chacun a connaissance de tous les coups +antérieurs. + +Au bout d'un nombre infini de tours, on considère le réel +\[ +u = x_0 + \frac{x_1}{b} + \frac{x_2}{b^2} + \frac{x_3}{b^3} + \cdots +\] +c'est-à-dire la somme de la série +$\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. Cette série converge car elle +converge absolument\footnote{\label{footnote-series-converges}Preuve : +$\sum_{i=0}^{+\infty}\left|\frac{x_i}{b^i}\right| \leq +\sum_{i=0}^{+\infty}\frac{M}{b^i} = \frac{M}{1-b}$ où $M$ est un +majorant des $|x|$ pour $x\in X$, qui existe car $X$ est fini.}. Si +$u\in A$ alors Alice a gagné ; sinon, Bob a gagné. + +(Un cas particulier qu'on peut garder à l'esprit est celui où $X = +\{0,1\}$ et $b = 2$, auquel cas Alice et Bob construisent un nombre +binaire entre $0$ et $2$ en choisissant alternativement ses chiffres : +$u = x_0.x_1 x_2 x_3\cdots$ en binaire.) + +On cherche à montrer que sous certaines conditions sur $A$, l'un des +joueurs a une stratégie gagnante. + +\textbf{(1)} On considère l'application $\psi\colon X^{\mathbb{N}} \to +\mathbb{R}$ qui à une suite $\dblunderline{x} = (x_i)_{i\in\mathbb{N}} +\in X^{\mathbb{N}}$ associe $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. +Montrer que si $\psi(\dblunderline{x}) = u$ et $\varepsilon > 0$, +alors il existe $\ell \in \mathbb{N}$ tel que toute suite +$\dblunderline{y}$ commençant par $x_0,\ldots,x_{\ell-1}$ vérifie +$|\psi(\dblunderline{y})-u| < \varepsilon$. Autrement dit, il existe +$\ell$ tel que l'image du $\ell$-ième voisinage +fondamental\footnote{Rappel : $V_\ell(\dblunderline{x})$ est +l'ensemble des suites commençant par les $\ell$ termes +$x_0,\ldots,x_{\ell-1}$.} $V_\ell(\dblunderline{x})$ de +$\dblunderline{x}$ par $\psi$ soit incluse dans la boule ouverte +$B_\varepsilon(u) := +\mathopen]u-\varepsilon,u+\varepsilon\mathclose[$. + (\emph{Indication :} s'inspirer de la + note \ref{footnote-series-converges}.) + +\begin{corrige} +Si $\dblunderline{x}$ et $\dblunderline{y}$ coïncident sur les +termes $i<\ell$, alors $|\psi(\dblunderline{y})-u| = +|\psi(\dblunderline{y})-\psi(\dblunderline{x})| = +\left|\sum_{i=\ell}^{+\infty} \frac{y_i - x_i}{b^i}\right| \leq +\sum_{i=\ell}^{+\infty} (\left|\frac{x_i}{b^i}\right| + +\left|\frac{y_i}{b^i}\right|) \leq \sum_{i=\ell}^{+\infty} +\frac{2M}{b^i} = \frac{2Mb^\ell}{1-b}$. Cette quantité tend vers $0$ +quand $\ell\to+\infty$, donc il existe $\ell$ tel qu'elle +soit $<\varepsilon$. Ceci montre bien que si $\dblunderline{y} \in +V_\ell(\dblunderline{x})$ on a $|\psi(\dblunderline{y})-u| < +\varepsilon$. +\end{corrige} + +\textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au +sens de la topologie usuelle des réels\footnote{Rappel : $U \subseteq +\mathbb{R}$ est ouvert lorsque pour tout $u\in U$ il existe +$\varepsilon>0$ tel que $B_\varepsilon(u) \subseteq U$.}), alors +l'image réciproque $\psi^{-1}(U) \subseteq X^{\mathbb{N}}$ est ouverte +(au sens de la topologie produit de la topologie discrète sur +$X^{\mathbb{N}}$, qu'on a considérée en cours). + +\begin{corrige} +Supposons que $U$ soit ouvert. Si $\dblunderline{x} \in +\psi^{-1}(U)$, c'est-à-dire $\psi(\dblunderline{x}) =: u \in U$, comme +$U$ est ouvert, il existe $\varepsilon>0$ tel que $B_\varepsilon(u) +\subseteq U$, et d'après la question (1), il existe $\ell$ tel que +$\psi(V_\ell(\dblunderline{x})) \subseteq B_\varepsilon(u) \subseteq +U$, ce qui signifie $V_\ell(\dblunderline{x}) \subseteq \psi^{-1}(U)$. +On vient de montrer que tout $\dblunderline{x} \in \psi^{-1}(U)$ a un +voisinage fondamental $V_\ell(\dblunderline{x})$ inclus dans +$\psi^{-1}(U)$, c'est-à-dire que $\psi^{-1}(U)$ est ouvert. + +(Note : on a évité dans ce corrigé d'utiliser le mot « continu » car +il n'a pas été défini en cours dans le contexte d'une application de +$X^{\mathbb{N}}$ vers $\mathbb{R}$. Mais bien sûr, il est correct de +dire que $\psi$ est continue en tant qu'application entre espaces +topologiques.) +\end{corrige} + +\textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé, +dans $\mathbb{R}$, alors l'un des deux joueurs possède une stratégie +gagnante au jeu qu'on a décrit. + +\begin{corrige} +Le jeu qu'on a décrit est exactement le jeu de Gale-Stewart défini par +la partie $\psi^{-1}(A)$. Si $A$ est ouvert, alors la question (2) +montre que $\psi^{-1}(A)$ est ouvert, donc le jeu est déterminé +d'après le théorème de détermination des jeux ouverts. Si $A$ est +fermé, alors son complémentaire $\mathbb{R}\setminus A$ est ouvert, +donc la question (2) montre que $\psi^{-1}(\mathbb{R}\setminus A) = +X^{\mathbb{N}} \setminus \psi^{-1}(A)$ est ouvert, c'est-à-dire que +$\psi^{-1}(A)$ est fermé, donc le jeu est déterminé d'après le +théorème de détermination des jeux fermés. +\end{corrige} + +\textbf{(4)} Montrer aussi ce résultat lorsque $A = \mathbb{Q}$ +(autrement dit, Alice gagne si la somme $u$ de la série est +rationnelle\footnote{Merci d'avance de ne pas prétendre que +$\mathbb{Q}$ est ouvert, ni qu'il est fermé.}). Plus généralement, +montrer ce résultat lorsque $A$ est borélien. + +\begin{corrige} +L'ensemble $\mathbb{Q}$ est la réunion dénombrable des fermés $\{r\}$ +pour $r\in\mathbb{Q}$ : il est donc borélien (dans $\mathbb{R}$) ; +l'image réciproque $\psi^{-1}(\mathbb{Q})$ est donc la réunion +dénombrable des fermés $\psi^{-1}(\{r\})$ : il est donc borélien (dans +$X^{\mathbb{N}}$). D'après le théorème de détermination des jeux +boréliens, le jeu est déterminé. + +Plus généralement, l'ensemble des $B$ tels que $\psi^{-1}(B)$ soit +borélien dans $X^{\mathbb{N}}$ est une tribu (puisque $\psi^{-1}$ +préserve les réunions et intersections quelconques, ainsi que le +complémentaire) et elle contient les ouverts (puisqu'on a vu que +$\psi^{-1}(U)$ est ouvert pour $U$ ouvert). Elle contient donc les +boréliens de $\mathbb{R}$. C'est-à-dire que si $B$ est borélien +dans $\mathbb{R}$ alors $\psi^{-1}(B)$ est borélien dans +$X^{\mathbb{N}}$. D'après le théorème de détermination des jeux +boréliens, le jeu est déterminé dès que $A$ est borélien. +\end{corrige} + + +% +% +% + +\exercice + +On va développer dans cet exercice un algorithme pour calculer la +somme et le produit d'ordinaux écrits en forme normale de Cantor +(itérée). + +\textbf{(1)} On rappelle que $1 + \omega = \omega$. En déduire que si +un ordinal $\alpha$ vérifie $\alpha \geq \omega$, alors on a $1 + +\alpha = \alpha$ (\emph{indication :} justifier qu'on peut écrire +$\alpha = \omega + \beta$). En déduire que $1 + \omega^\gamma = +\omega^\gamma$ lorsque $\gamma > 0$, puis que $\omega^{\gamma_1} + +\omega^{\gamma_2} = \omega^{\gamma_2}$ lorsque $\gamma_1 < \gamma_2$, +et enfin que $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 = +\omega^{\gamma_2} n_2$ si $n_1,n_2$ sont deux entiers naturels non +nuls (et toujours avec $\gamma_1 < \gamma_2$). + +\begin{corrige} +On a vu que lorsque $\alpha_0 \leq \alpha$, il existe un unique +$\beta$ tel que $\alpha = \alpha_0 + \beta$ : en particulier, si +$\alpha \geq \omega$, on peut écrire $\alpha = \omega + \beta$, et on +en déduit que $1 + \alpha = 1 + \omega + \beta = \omega + \beta = +\alpha$. + +Or si $\gamma > 0$, c'est-à-dire $\gamma \geq 1$, on a $\omega^\gamma +\geq \omega$, et on vient de voir que ceci implique $1 + \omega^\gamma += \omega^\gamma$. + +Si $\gamma_1 < \gamma_2$, on peut écrire $\gamma_2 = \gamma_1 + +\gamma$ (cf. deux paragraphes plus haut), donc $\omega^{\gamma_1} + +\omega^{\gamma_2} = \omega^{\gamma_1} + \omega^{\gamma_1 + \gamma} = +\omega^{\gamma_1} + \omega^{\gamma_1} \, \omega^{\gamma} = +\omega^{\gamma_1} (1 + \omega^\gamma) = \omega^{\gamma_1} \, +\omega^\gamma = \omega^{\gamma_1+\gamma} = \omega^{\gamma_2}$. + +Une fois acquis que $\omega^{\gamma_1} + \omega^{\gamma_2} = +\omega^{\gamma_2}$, on a $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} +n_2 = \omega^{\gamma_1} + \cdots + \omega^{\gamma_1} + +\omega^{\gamma_2} + \cdots + \omega^{\gamma_2}$ (avec $n_1$ termes +$\omega^{\gamma_1}$ et $n_2$ termes $\omega^{\gamma_2}$), et en +utilisant de façon répétée l'égalité qu'on vient de dire, ceci vaut +$\omega^{\gamma_2} + \cdots + \omega^{\gamma_2} = \omega^{\gamma_2} +n_2$, comme annoncé. +\end{corrige} + +\textbf{(2)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1$ (avec $\gamma_s > \cdots > \gamma_1$ et +$n_1,\ldots,n_s$ des entiers naturels non nuls) et $\alpha' = +\omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$ +(idem) sont deux ordinaux écrits en forme normale de Cantor, en +utilisant les résultats de la question précédente, expliquer comment +calculer $\alpha + \alpha'$, en supposant qu'on sache +algorithmiquement comparer les $\gamma_i$ et les $\gamma'_j$. + +\begin{corrige} +On écrit $\alpha + \alpha' = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1 + \omega^{\gamma'_{s'}} n'_{s'} + \cdots + +\omega^{\gamma'_1} n'_1$ et, d'après ce qu'on vient de voir, dès que +deux termes ne sont pas dans le bon ordre (i.e., si un +$\omega^{\gamma_i} n_i$ précède $\omega^{\gamma_j} n_j$ avec $\gamma_i +< \gamma_j$), alors le premier disparaît purement et simplement ; et +bien sûr, si $\gamma_i = \gamma_j$, les termes fusionnent en +$\omega^{\gamma_i} (n_i+n_j)$ par distributivité à droite. On se +retrouve donc avec l'écriture en forme normale de Cantor de $\alpha + +\alpha'$. +\end{corrige} + +\textbf{(3)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot +3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha + +\alpha'$ et $\alpha' + \alpha$. + +\begin{corrige} +Dans le sens $\alpha + \alpha'$, on a $(\omega^3\cdot 2 + \omega\cdot +3 + 5) + (\omega^2 + \omega\cdot 4) = \omega^3\cdot 2 + \omega^2 + +\omega\cdot 4$. + +Dans le sens $\alpha' + \alpha$, on a $(\omega^2 + \omega\cdot 4) + +(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^3\cdot 2 + \omega\cdot +3 + 5$. +\end{corrige} + +\textbf{(4)} Déduire de la question (2) que si $\alpha = +\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ en forme +normale de Cantor et $k \geq 1$ est un entier naturel, alors +$\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} +n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ (c'est-à-dire que seul le +coefficient $n_s$ de la plus haute puissance de $\omega$ est multiplié +par $k$ ; \emph{indication} : on a $\alpha\cdot k = \alpha + \cdots + +\alpha$ avec $k$ termes identiques). + +\begin{corrige} +En écrivant $\alpha\cdot k = \alpha + \cdots + \alpha$ (qui résulte de +la distributivité à droite) et en appliquant les règles expliquées +en (2), on voit que tous les termes autres que le plus haut de tous +les termes autres que le dernier de la terme disparaissent purement et +simplement (ils sont absorbés par le terme le plus haut du $\alpha$ +suivant), donc seul subsistent $k-1$ copies de $\omega^{\gamma_s} n_s$ +plus le dernier $\alpha$, ce qui donne bien $\alpha\cdot k = +\omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + +\omega^{\gamma_1} n_1$ comme annoncé. +\end{corrige} + +\textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s} +n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\cdot\omega = +\omega^{\gamma_s+1}$ (\emph{indication} : on pourra calculer +$\lim_{k\to\omega} \alpha \cdot k$), et plus généralement $\alpha\cdot +\omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq 1$ +(\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$). + +\begin{corrige} +On cherche à calculer $\alpha\cdot\omega = \lim_{k\to\omega} \alpha \cdot +k$ (rappelons que cette limite est juste une borne supérieure). Par +comparaison des formes normales de Cantor, $\omega^{\gamma_s+1}$ est +plus grand que tous les $\alpha\cdot k = \omega^{\gamma_s} n_sk + +\omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$, donc +$\omega^{\gamma_s+1} \geq \lim_{k\to\omega} \alpha \cdot k$. Mais +inversement, la forme normale de Cantor de tout ordinal +$<\omega^{\gamma_s+1}$ commence par un terme $\leq\omega^{\gamma_s} +N$, donc majoré par $\alpha\cdot k$ pour $k$ assez grand (certainement +pour $k\geq N$) : donc $\lim_{k\to\omega} \alpha \cdot k$ ne peut pas +être $<\omega^{\gamma_s+1}$. Donc c'est exactement +$\omega^{\gamma_s+1}$, et on a prouvé $\alpha\cdot\omega = +\omega^{\gamma_s+1}$. + +Plus généralement, si $\gamma'\geq 1$, on peut écrire $\gamma' = +1+\gamma''$ comme on l'a déjà rappelé plus haut, et +$\alpha\cdot\omega^{\gamma'} = \alpha\cdot\omega^{1+\gamma''} = +\alpha\cdot\omega\omega^{\gamma''} = +\omega^{\gamma_s+1}\omega^{\gamma''} = \omega^{\gamma_s+1+\gamma''} = +\omega^{\gamma_s+\gamma'}$. +\end{corrige} + +\textbf{(6)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1$ et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} + +\cdots + \omega^{\gamma'_1} n'_1$ sont deux ordinaux écrits en forme +normale de Cantor, en utilisant les résultats de la question +précédente, expliquer comment calculer $\alpha \cdot \alpha'$, en +supposant qu'on sache algorithmiquement comparer et ajouter les +$\gamma_i$ et les $\gamma'_j$. + +\begin{corrige} +Par distributivité à droite et comme on sait déjà calculer des sommes, +on peut se ramener au cas où $\alpha'$ est un seul terme +$\omega^{\gamma'} n'$. Par associativité, il suffit de savoir +calculer le produit par $\omega^{\gamma'}$ à droite, et par $n'$. Le +produit par $\omega^{\gamma'}$ est trivial si $\gamma'=0$ et est réglé +par la question (5) si $\gamma'>0$. Et le produit par $n'$ est réglé +par la question (4). + +Un peu plus concrètement, pour chaque terme de $\alpha'$ pour lequel +$\gamma'_j > 0$, on a $\alpha\cdot \omega^{\gamma'_j} n'_j = +\omega^{\gamma_s + \gamma'_j} n_s n_j$, et le terme fini, s'il existe +(c'est-à-dire si $\gamma'_1 = 0$) vaut $\alpha\cdot n'_1 = +\omega^{\gamma_s} n_s n'_1 + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + +\omega^{\gamma_1} n_1$. Il n'y a plus qu'à ajouter tous ces termes +dans l'ordre (qui est déjà le bon, et qui donne déjà une forme normale +de Cantor, puisque $\gamma_s + \gamma'_s > \cdots + \gamma_s + +\gamma'_2 > \gamma_s > \cdots > \gamma_1$). +\end{corrige} + +\textbf{(7)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot +3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha \cdot +\alpha'$ et $\alpha' \cdot \alpha$. + +\begin{corrige} +Dans le sens $\alpha\alpha'$ on trouve $(\omega^3\cdot 2 + \omega\cdot +3 + 5) (\omega^2 + \omega\cdot 4) = \omega^5 + \omega^4\cdot 4$ (il +n'y a pas de terme fini à la fin de $\alpha'$ donc seul le premier +terme de $\alpha$ survit). + +Dans le sens $\alpha'\alpha$ on trouve $(\omega^2 + \omega\cdot 4) +(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^5\cdot 2 + +\omega^3\cdot 3 + \omega^2\cdot 5 + \omega\cdot 4$. +\end{corrige} + + + +% +% +% +\end{document} diff --git a/controle-20250626.tex b/controle-20250626.tex new file mode 100644 index 0000000..36f8319 --- /dev/null +++ b/controle-20250626.tex @@ -0,0 +1,1083 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\usepackage[french]{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}{Whatever} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercise{% +\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}}} +% +\renewcommand{\thefootnote}{\fnsymbol{footnote}} +% +\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{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} +\else +\title{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} +\fi +\author{} +\date{2025-06-26} +\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. + +Une traduction anglaise indicative suit l'énoncé en français. + +\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 + +\ifcorrige +Ce corrigé comporte 11 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 + + +% +% +% + +\exercise\label{normal-form-games-exercise} + +\textbf{(1)} On considère le jeu en forme normale symétrique à somme +nulle défini par la matrice de gains suivante : +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline +Pierre&$0$&$-1$&$+1$\\ +Papier&$+1$&$0$&$-1$\\ +Ciseaux&$-1$&$+1$&$0$\\ +\end{tabular} +\end{center} +(Seul le gain d'Alice a été inscrit dans chaque case car les gains des +deux joueurs sont opposés.) + +Quels sont tous les équilibres de Nash de ce jeu ? + +\begin{corrige} +On a vu en cours qu'une stratégie optimale pour l'un ou l'autre joueur +est $\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + +\frac{1}{3}\text{Ciseaux}$ : de fait, la valeur du jeu est nulle car +il est à somme nulle et \emph{symétrique}, et cette stratégie mixte +$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + +\frac{1}{3}\text{Ciseaux}$ réalise au moins la valeur du jeu contre +n'importe quelle option de l'adversaire. + +Réciproquement, si $p\,\text{Pierre} + q\,\text{Papier} + +r\,\text{Ciseaux}$ est une stratégie optimale d'un joueur (avec +$p,q,r$ positifs de somme $1$), son gain contre les trois stratégies +pures de l'adversaire (à savoir $q-r$ contre Pierre, $r-p$ contre +Papier et $p-q$ contre Ciseaux) doit être au moins égal à la valeur du +jeu (soit $0$). On a donc $q \geq r$ et $r \geq p$ et $p \geq q$, ce +qui impose $p=q=r$ donc ils valent $\frac{1}{3}$. Ceci montre que +$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + +\frac{1}{3}\text{Ciseaux}$ est la seule stratégie optimale à ce jeu +(quel que soit le joueur). + +Enfin, les équilibres de Nash d'un jeu à somme nuls sont ceux où les +deux joueurs jouent une stratégie optimale, donc il n'y a qu'un seul +ici, c'est celui où Alice et Bob jouent chacun +$\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + +\frac{1}{3}\text{Ciseaux}$. +\end{corrige} + +\medskip + +\textbf{(2)} On souhaite maintenant ajouter une nouvelle option +« Foobar » au jeu ci-dessus, c'est-à-dire qu'on considère le jeu en +forme normale (toujours symétrique et à somme nulle) défini par la +matrice de gains : +\begin{center} +\begin{tabular}{r|cccc} +$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar\\\hline +Pierre&$0$&$-1$&$+1$&$-x$\\ +Papier&$+1$&$0$&$-1$&$-y$\\ +Ciseaux&$-1$&$+1$&$0$&$-z$\\ +Foobar&$x$&$y$&$z$&$0$\\ +\end{tabular} +\end{center} +(Les trois sous-questions qui suivent sont indépendantes.) + +\textbf{\hphantom{(2)} (a)} À quelle condition (nécessaire et +suffisante) sur $x,y,z$ les équilibres de Nash trouvés en (1) sont-ils +encore des équilibres de Nash pour ce nouveau jeu ?\quad\textbf{(b)} À +quelle condition (nécessaire et suffisante) sur $x,y,z$ y a-t-il un +équilibre de Nash où les deux joueurs jouent l'option Foobar (de façon +certaine) ?\quad\textbf{(c)} À quelle condition (nécessaire et +suffisante) sur $x,y,z$ y a-t-il un équilibre de Nash où les deux +joueurs jouent $\frac{1}{2}\text{Pierre} + \frac{1}{2}\text{Foobar}$ +(i.e., Pierre ou Foobar chacun avec probabilité $\frac{1}{2}$) ? + +\begin{corrige} +\textbf{(a)} En ajoutant une ligne et une colonne pour la stratégie +mixte $M := \frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + +\frac{1}{3}\text{Ciseaux}$, le tableau devient : +\begin{center} +\begin{tabular}{r|cccc|c} +$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar&$M$\\\hline +Pierre&$0$&$-1$&$+1$&$-x$&$0$\\ +Papier&$+1$&$0$&$-1$&$-y$&$0$\\ +Ciseaux&$-1$&$+1$&$0$&$-z$&$0$\\ +Foobar&$x$&$y$&$z$&$0$&$\frac{1}{3}(x+y+z)$\\\hline +$M$&$0$&$0$&$0$&$-\frac{1}{3}(x+y+z)$&$0$\\ +\end{tabular} +\end{center} +Le profil $(M,M)$ est un équilibre de Nash lorsque $0$ est le plus +grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire +exactement lorsque $x+y+z \leq 0$. + +\textbf{(b)} Le profil $(\text{Foobar}, \text{Foobar})$ est un +équilibre de Nash lorsque $0$ est le plus grand nombre de sa colonne +et le plus petit de sa ligne, c'est-à-dire lorsque $x,y,z$ sont tous +positifs. + +\textbf{(c)} En ajoutant une ligne et une colonne pour la stratégie +mixte $N := \frac{1}{2}\text{Pierre} + +\frac{1}{2}\text{Foobar}$, le tableau devient : +\begin{center} +\begin{tabular}{r|cccc|c} +$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar&$N$\\\hline +Pierre&$0$&$-1$&$+1$&$-x$&$-\frac{x}{2}$\\[0.7ex] +Papier&$+1$&$0$&$-1$&$-y$&$-\frac{y-1}{2}$\\[0.7ex] +Ciseaux&$-1$&$+1$&$0$&$-z$&$-\frac{z+1}{2}$\\[0.7ex] +Foobar&$x$&$y$&$z$&$0$&$\frac{x}{2}$\\[0.7ex]\hline +$N$&$\frac{x}{2}$&$\frac{y-1}{2}$&$\frac{z+1}{2}$&$-\frac{x}{2}$&$0$\\ +\end{tabular} +\end{center} +Le profil $(N,N)$ est un équilibre de Nash lorsque $0$ est le plus +grand nombre de sa colonne et le plus petit de sa ligne, c'est-à-dire +exactement lorsque $x=0$ et $y\geq 1$ et $z\geq -1$. +\end{corrige} + +\medskip + +\textbf{(3)} On change de jeu : on reprend maintenant la matrice de +gains écrite en (1), mais cette fois les gains des deux joueurs seront +\emph{égaux} au lieu d'être opposés (ce n'est donc plus un jeu à somme +nulle ! les joueurs sont alliés et non plus adversaires). Le tableau +donne la valeur du gain commun aux deux joueurs. + +\textbf{\hphantom{(3)} (a)} Montrer que les équilibres de Nash trouvés +en (1) sont encore des équilibres de Nash de ce nouveau +jeu.\quad\textbf{(b)} Donner au moins un équilibre de Nash différent +de ceux-ci. Commenter brièvement quant à la différence de gain +éventuelle entre les équilibres de Nash trouvés en (a) et (b). + +\begin{corrige} +\textbf{(a)} En ajoutant une ligne et une colonne pour la stratégie +mixte $M := \frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + +\frac{1}{3}\text{Ciseaux}$, le tableau devient : +\begin{center} +\begin{tabular}{r|ccc|c} +$\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&$M$\\\hline +Pierre&$0$&$-1$&$+1$&$0$\\ +Papier&$+1$&$0$&$-1$&$0$\\ +Ciseaux&$-1$&$+1$&$0$&$0$\\\hline +$M$&$0$&$0$&$0$&$0$\\ +\end{tabular} +\end{center} +Le profil $(M,M)$ est bien un équilibre de Nash car $0$ est le plus +grand nombre de sa colonne et le plus grand de sa ligne, ce qui est +bien le cas ici. + +\textbf{(b)} Il y a des équilibres de Nash évidents en stratégies +pures, à savoir tous les $+1$ du tableau : par exemple, si Alice joue +Papier et Bob joue Pierre, ceci constitue bien un équilibre de Nash +(car $+1$ est le plus grand nombre de sa colonne et le plus grand de +sa ligne). + +L'équilibre de Nash trouvé en (a) correspond intuitivement à une +situation où les joueurs ne sont pas synchronisés : ils jouent une +stratégie équilibrée entre les trois options. Dans ce jeu coopératif, +ce n'est pas du tout optimal, le gain espéré étant $0$, mais aucun n'a +d'intérêt à privilégier unilatéralement une des options tant que +l'autre continue à jouer cette stratégie. Dans le cas trouvé en (b), +en revanche, les joueurs se sont synchronisés sur une stratégie qui +les arrange tous les deux, réalisant le gain qui est visiblement le +meilleur possible ici. +\end{corrige} + + +% +% +% + +\exercise\label{modified-nim-exercise} + +On considère dans cet exercice le jeu suivant : + +Alice et Bob ont devant eux des piles de jetons, qui représentent +l'état du jeu (= la position). Chaque pile contient un certain nombre +fini (entier naturel) de jetons. Les piles sont numérotées par des +entiers naturels, mais il n'y en a qu'un nombre fini qui soient +non-vides (i.e., qui aient $>0$ jetons). Pour représenter la position +mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, n_k)$ +où $n_i$ est le nombre de jetons de la pile numérotée $i$, et où ceci +signifie implicitement que toutes les piles $\geq k$ sont vides. + +Un coup d'un joueur consiste à retirer \emph{exactement un} jeton +d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il +le souhaite} (y compris $0$) jetons à chacune des piles $j<i$, y +compris ajouter des nombres différents à des piles différentes. Par +exemple, à partir de la position $(0,3,2)$ on peut notamment jouer +vers $(42,1000,1)$ ou bien vers $(0,2,2)$ ou encore vers +$(696\,729\,600,2,2)$. + +Comme d'habitude, le joueur qui ne peut pas jouer a perdu, +c'est-à-dire que celui qui prend le dernier jeton a gagné. + +\medskip + +\textbf{(1)} Montrer que le jeu qu'on vient de définir termine +forcément en temps fini, quelle que soit la position initiale et quels +que soient les coups effectués par les joueurs. (On justifiera +soigneusement.) + +\begin{corrige} +On associe à la position $(n_0,\ldots,n_k)$ l'ordinal $\omega^k\cdot +n_k + \cdots + \omega\cdot n_1 + n_0$ (remarquons qu'il s'agit d'une +écriture en forme normale de Cantor). Un coup du jeu consiste à +remplacer un certain $n_i$ par $n_i-1$ et tous les $n_j$ avec $j<i$ +par des $n'_j$ où $n'_j \geq n_j$. Le tuple +$(n'_0,\ldots,n'_{i-1},n_i-1,n_{i+1},\ldots,n_k)$ qui résulte du coup +est lexicographiquement inférieur à $(n_0,\ldots,n_k)$ pour l'ordre +lexicographique donnant le poids le plus fort aux $n_j$ avec $j$ +grand, ce qui signifie justement que l'ordinal qu'on vient de lui +associer a diminué strictement. Comme toute suite strictement +décroissante d'ordinaux est finie, le jeu termine en temps fini, +\end{corrige} + +\textbf{Définition :} Appelons « position totalement paire » une +position dans laquelle le nombre $n_i$ de jetons de chaque pile est +pair, et « position non totalement paire » une position dans laquelle +au moins un des $n_i$ est impair. + +\textbf{(2)} Montrer que tout coup joué depuis une position totalement +paire conduit nécessairement à une position non totalement paire. + +\begin{corrige} +On a retiré un jeton d'une certaine pile $i$, donc si le nombre de +jetons était pair avant le coup, il est devenu impair, et la position +n'est plus totalement paire. +\end{corrige} + +\textbf{(3)} Montrer que depuis toute position non totalement paire il +existe au moins un coup conduisant à une position totalement paire. + +\begin{corrige} +Si $(n_0,\ldots,n_k)$ est une position non totalement paire, il existe +un $n_i$ impair : soit $i$ le plus grand possible tel que $n_i$ soit +impair (tous les $n_j$ avec $j>i$ sont donc pairs). Le coup +consistant à retirer un jeton de la pile $i$ (qui passe donc à $n_i-1$ +jetons, lequel nombre est pair) et à en ajouter un à toutes les piles +$j<i$ telles que $n_j$ soit impair (qui passent donc à $n_j+1$ jetons, +lequel nombre est pair) est légal selon les règles du jeu, et conduit +à une position totalement paire. +\end{corrige} + +\textbf{(4)} En déduire quelles sont les positions du jeu dans +lesquelles le premier joueur a une stratégie gagnante, et quelles sont +celles dans lesquelles le second joueur en a une. (On justifiera très +soigneusement.) + +\begin{corrige} +Considérons la stratégie $\sigma$ consistant à jouer vers une position +totalement paire si on est dans une position qui ne l'est pas (c'est +possible par la question (3)) et à retirer un jeton quelconque sinon +(et bien sûr, à capituler s'il n'y a plus de jeton). Le joueur qui +applique cette stratégie $\sigma$ depuis une position non totalement +paire va gagner : chacun de ces coups mènera à une position totalement +paire et son adversaire va forcément en sortir au coup suivant, donc +(par une récurrence immédiate) le joueur dont on parle sera toujours +face à une position non totalement paire, et gagnera car le jeu ne +peut pas durer indéfiniment longtemps (question (1)). Ceci montre que +les positions qui ne sont pas totalement paires sont gagnantes pour le +premier joueur (ce sont des positions N) et que celles qui sont +totalement paires sont gagnantes pour le second joueur (ce sont des +positions P). + +Si on préfère, on peut aussi rédiger ainsi : on a vu au (1) que le +graphe des positions du jeu est bien-fondé. On peut donc montrer par +induction bien-fondée sur la position $x$ que $x$ est une position P +si et seulement si elle est totalement paire. Si $x$ est totalement +paire, aucun de ses voisins sortants n'est totalement pair +d'après (2), donc ils sont tous N par l'hypothèse d'induction, donc +$x$ est P ; et réciproquement, si $x$ est P, tous ses voisins sont N, +donc par hypothèse d'induction aucun n'est totalement pair, donc $x$ +n'est pas totalement pair par (la contraposée de) la question (3). +Ceci conclut l'induction. +\end{corrige} + +\textbf{(5)} Calculer, en fonction de $n$, la valeur de Grundy de la +position $(n)$ (c'est-à-dire s'il n'y a que la pile numérotée $0$, et +que celle-ci comporte $n$ jetons). + +\begin{corrige} +On a $\gr((0)) = 0$ car c'est un puits, et $\gr((1)) = \mex\{0\} = 1$ +puis $\gr((2)) = \mex\{1\} = 0$, et ainsi de suite. + +Pour simplifier la notation dans les réponses ultérieures, notons +$(n\%2)$ l'entier valant $0$ si $n$ est pair et $1$ si $n$ est impair. + +Une récurrence sur $n$ permet de prouver que $\gr((n)) = (n\%2)$ : en +effet, si $n$ est pair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{1\} = +0$, et si $n$ est impair, $\gr((n)) = \mex(\{\gr((n-1))\}) = \mex\{0\} += 1$. +\end{corrige} + +\textbf{(6)} En déduire la valeur de Grundy des posititions $(0,1)$ et +$(1,1)$, puis plus généralement de $(n,1)$ en fonction de $n$. + +\begin{corrige} +On a $\gr((0,1)) = \mex\{\gr((n)) : n\in\mathbb{N}\} = \mex\{0,1\} = +2$. On en déduit que $\gr((1,1)) = \mex(\{\gr((n+1)) : +n\in\mathbb{N}\} \cup \{\gr((0,1))\}) = \mex\{0,1,2\} = 3$. On +vérifie alors par récurrence sur $n$ que $\gr((n,1)) = 2$ si $n$ est +pair et $\gr((n,1)) = 3$ si $n$ est impair (i.e., $2+(n\%2)$, si on +veut) : en effet, si $n$ est pair, $\gr((n,1)) = \mex(\{\gr((m)) : +m\geq n\} \cup \{\gr((n-1,1))\}) = \mex(\{0,1,3\}) = 2$, et si $n$ est +impair, $\gr((n,1)) = \mex(\{\gr((m)) : m\geq n\} \cup +\{\gr((n-1,1))\}) = \mex(\{0,1,2\}) = 3$. +\end{corrige} + +\textbf{(7)} En déduire la valeur de Grundy des positions $(0,2)$ et +$(1,2)$, plus plus généralement de $(n_0,n_1)$ en fonction +de $n_0,n_1$. + +\begin{corrige} +On a $\gr((0,2)) = \mex\{\gr((n,1)) : n\in\mathbb{N}\} = \mex\{2,3\} = +0$ (ce qu'on peut aussi conclure du fait que $(0,2)$ est totalement +paire). On en déduit que $\gr((1,2)) = \mex(\{\gr((n+1,1)) : +n\in\mathbb{N}\} \cup \{\gr((0,2))\}) = \mex\{2,3,0\} = 1$. + +On peut alors mener une récurrence sur $n_1$ et, pour chaque $n_1$, +sur $n_0$ (ou, si on préfère, une induction transfinie sur l'ordinal +$\omega\cdot n_1 + n_0$) pour montrer : $\gr((n_0,n_1)) = 2(n_1\%2) + +(n_0\%2)$. En effet, +\begin{itemize} +\item si $n_0$ et $n_1$ sont pairs, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{2,3,1\} = 0$ (ce qu'on peut aussi conclure du fait que + $(n_0,n_1)$ est totalement paire), +\item si $n_0$ est impair et $n_1$ pair, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{2,3,0\} = 1$, +\item si $n_0$ est pair et $n_1$ impair, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{0,1,3\} = 2$, +\item si $n_0$ et $n_1$ sont impairs, on a $\gr((n_0,n_1)) = + \mex(\{\gr((m,n_1-1)) : m\geq n_0\} \cup \{\gr((n_0-1,n_1))\}) = + \mex\{0,1,2\} = 3$. +\end{itemize} +Ceci couvre tous les cas et conclut la récurrence. +\end{corrige} + +\textbf{(8)} En déduire la valeur de Grundy de la position $(0,0,1)$. + +\begin{corrige} +On a $\gr((0,0,1)) = \mex\{\gr((n_0,n_1)) : n_0,n_1\in\mathbb{N}\} = +\mex\{0,1,2,3\} = 4$. +\end{corrige} + +\textbf{(9)} Conjecturer une formule générale pour la valeur de Grundy +d'une position $(n_0,n_1,\ldots,n_k)$ quelconque. + +\begin{corrige} +Les résultats précédents suggèrent que $\gr((n_0,n_1,\ldots,n_k))$ ne +dépend que de la parité de $n_0,\ldots,n_k$, c'est-à-dire de ce qu'on +a noté $(n_i\%2)$. Les valeurs calculées jusqu'à présent inspirent à +penser que +\[ +\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2) +\] +(C'est-à-dire qu'on lit les $(n_i\%2)$ comme un nombre en binaire et +qu'il donne la valeur de Grundy.) +\end{corrige} + +\textbf{(10)} Démontrer cette formule. (Cette question est plus +difficile, et il peut être opportun de la garder pour la fin. On +pourra s'inspirer de la démonstration faite en cours du calcul de la +valeur de Grundy pour le jeu de nim.) + +\begin{corrige} +On va montrer par induction transfinie sur l'ordinal $\omega^k\cdot +n_k + \cdots + \omega\cdot n_1 + n_0$ associé à la position +$(n_0,n_1,\ldots,n_k)$ (ou, ce qui revient essentiellement au même, +par induction bien-fondée sur la position elle-même) que la formule +ci-dessus est valable. + +Comme $\gr((n_0,n_1,\ldots,n_k))$ est le $\mex$ de l'ensemble $S$ des +$\gr((n'_0,n'_1,\ldots,n'_k))$ où $(n'_0,n'_1,\ldots,n'_k)$ parcourt +tous les voisins sortants de $(n_0,n_1,\ldots,n_k)$, pour montrer que +$\gr((n_0,n_1,\ldots,n_k)) = 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + +(n_0\%2)$, il s'agit de vérifier (A) que $2^k\,(n_k\%2) + \cdots + +2\,(n_1\%2) + (n_0\%2)$ n'est pas dans $S$ et (B) que tout nombre $r < +2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est dans $S$. Or par +hypothèse d'induction, les éléments de $S$ sont les $2^k\,(n'_k\%2) + +\cdots + 2\,(n'_1\%2) + (n'_0\%2)$ avec $(n'_0,n'_1,\ldots,n'_k)$ +voisin sortant de $(n_0,n_1,\ldots,n_k)$. + +Montrons (A) : on sait qu'un des $n'_i$ vaut $n_i-1$. Ceci assure que +$(n'_i\%2) \neq (n_i\%2)$, donc par unicité des écritures binaires, +que $2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + (n_0\%2)$ est différent de +$2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$ (au moins un bit +diffère). Ceci conclut le (A). + +Montrons (B) : si $r < 2^k\,(n_k\%2) + \cdots + 2\,(n_1\%2) + +(n_0\%2)$, appelons $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$ son +écriture binaire, où $b_j \in \{0,1\}$. Soit $i$ le plus grand +possible tel que $b_i \neq (n_i\%2)$ : alors $b_i = ((n_i-1)\%2)$. +(On prendra aussi note du fait que $b_j = (n_j\%2)$ si $j>i$ par +maximalité de $i$.) Définissons les $n'_j$ comme suit : on pose $n'_j += n_j$ si $j>i$, et $n'_i = n_i-1$, et enfin, pour $j<i$, on pose +$n'_j = n_j + ((n_j+b_j)\%2)$. Par construction (comme $n'_j = n_j$ +si $j>i$ et $n'_i = n_i$ et $n'_j \geq n_j$ si $j\leq i$), le +$(n'_0,n'_1,\ldots,n'_k)$ qu'on vient de définir est bien un voisin +sortant de $(n_0,n_1,\ldots,n_k)$. Par ailleurs, $(n'_j\%2) = b_j$ : +en effet, pour $j>i$ cela résulte de $b_j = (n_j\%2)$ et $n'_j = +n_j$ ; pour $j=i$ cela résulte de $b_i = ((n_i-1)\%2)$ et $n'_i = +n_i-1$ ; et pour $j<i$ cela résulte du fait que $n'_j = n_j + +((n_j+b_j)\%2)$ est congru à $n_j + n_j + b_j$ donc à $b_j$ +modulo $2$. En insérant la formule $b_j = (n'_j\%2)$ qu'on vient de +montrer dans $r = 2^k\,b_k + \cdots + 2\,b_1 + b_0$, on voit que $r = +2^k\,(n'_k\%2) + \cdots + 2\,(n'_1\%2) + (n'_0\%2)$. qui est donc +dans $S$. Ceci conclut le (B), l'induction, et l'ensemble de la +démonstration. +\end{corrige} + + + +% +% +% + +\exercise\label{indeterminacy-exercise} + +On se propose dans cet exercice de montrer qu'il existe une partie $A +\subseteq \{0,1\}^{\mathbb{N}}$ tel que le jeu de Gale-Stewart $G(A) +:= G_{\{0,1\}}(A)$ ne soit pas déterminé (i.e., tel qu'aucun des deux +joueurs n'ait de stratégie gagnante). + +(La démonstration a été découpées en questions admettant des réponses +courtes, parfois d'une seule ligne.) + +\medskip + +\textbf{(1)} Montrer qu'il existe une bijection $h_{\mathrm{A}}$ +(resp. $h_{\mathrm{B}}$) entre $\{0,1\}^{\mathbb{N}}$ et l'ensemble +des stratégies d'Alice (resp. de Bob) au jeu $G(A)$. +(\emph{Indication :} on pourra expliquer rapidement pourquoi il existe +une bijection entre $\mathbb{N}$ et l'ensemble des positions où c'est +à Alice, resp. à Bob, de jouer.) + +\begin{corrige} +L'ensemble $P_{\mathrm{A}}$ des positions où c'est à Alice de jouer +sont les suites binaires finies de longueur paires : on peut les +énumérer dans l'ordre de longueur et, pour chaque longueur, dans +l'ordre lexicographique ($()$, $00$, $01$, $10$, $11$, $0000$, $0001$, +$0010$, etc.). Ceci fournit une bijection $g_{\mathrm{A}}\colon +\mathbb{N} \to P_{\mathrm{A}}$ : on en déduit une bijection +$h_{\mathrm{A}}\colon \{0,1\}^{P_{\mathrm{A}}} \to +\{0,1\}^{\mathbb{N}}$ par $h_{\mathrm{A}}(u) = (n \mapsto +u(g_{\mathrm{A}}(n)))$. Or $\{0,1\}^{P_{\mathrm{A}}}$ est exactement +l'ensemble des stratégies d'Alice (ce sont les fonctions qui à une +position où c'est à Alice de jouer associent un coup d'Alice). + +Exactement le même raisonnement fournit le résultat pour +$h_{\mathrm{B}}$ : il faut simplement considérer cette fois l'ensemble +$P_{\mathrm{B}}$ des positions où c'est à Bob de jouer, qui sont les +suites binaires finies de longueur paires ($0$, $1$, $000$, $001$, +etc.). +\end{corrige} + +\textbf{(2)} On \emph{admet}\footnote{Plus généralement, on peut +montrer qu'il existe une relation de bon ordre sur n'importe quel +ensemble (théorème du bon ordre).} qu'il existe une relation de bon +ordre $\preceq$ sur $\{0,1\}^{\mathbb{N}}$. En déduire qu'il existe +un ordinal $\gamma$ et une bijection $\xi \mapsto u_\xi$ entre +l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$ et +l'ensemble $\{0,1\}^{\mathbb{N}}$ (autrement dit, les $u_\xi$ sont +deux à deux distincts et $\{u_\xi : \xi < \gamma\} = +\{0,1\}^{\mathbb{N}}$). + +\begin{corrige} +Soit $W$ l'ensemble $\{0,1\}^{\mathbb{N}}$ muni du bon ordre $\preceq$ +qu'on a supposé exister, et soit $\gamma = \#W$ son ordinal. À tout +élément $w$ de $W$ on associe un ordinal $\#w$ qui est l'ordinal de +l'ensemble $\{x \in W : x \prec w\}$ des prédécesseurs stricts +de $w$ : ceci constitue une bijection strictement croissante entre $W$ +et l'ensemble $\{\xi < \gamma\}$ des ordinaux $<\gamma$ ; on appelle +alors $\xi \mapsto u_\xi$ la bijection réciproque. + +(Si on préfère : l'ordinal de $W$ est le même que l'ordinal de $\{\xi +< \gamma\}$, à savoir $\gamma$, donc il y a une — unique — bijection +croissante entre les deux, et on appelle $\xi \mapsto u_\xi$ sa +réciproque.) +\end{corrige} + +\textbf{(3)} Expliquer en une ligne, pourquoi il existe un plus petit +ordinal $\gamma$ tel qu'il existe une surjection $\xi \mapsto u_\xi$ +de l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$ +sur l'ensemble $\{0,1\}^{\mathbb{N}}$. + +\begin{corrige} +En une ligne : on vient de montrer qu'un tel $\gamma$ existe, donc il +y en a un plus petit. + +(En un tout petit peu plus détaillé : comme les ordinaux sont +bien-ordonnés, dès qu'il existe un ordinal tel que (quelque chose), +alos il y en a un plus petit ; or il existe un ordinal tel que $\{\xi +< \gamma\}$ se surjecte sur $\{0,1\}^{\mathbb{N}}$ — on vient de voir +l'existence d'une telle bijection —, donc il en existe un plus petit.) +\end{corrige} + +\textbf{Définition :} On notera\footnote{Il s'agit ici d'un ‘c’ +gothique (cet ordinal s'appelle le « cardinal du continu ») ; si on ne +veut pas écrire de ‘c’ gothique on pourra, par exemple, faire un ‘c’ +souligné.} $\mathfrak{c}$ l'ordinal dont on vient de justifier +l'existence, i.e., le plus petit $\gamma$ tel qu'on puisse écrire +$\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ pour une certaine +fonction $\xi \mapsto u_\xi$, qu'on fixe dans la suite. + +\textbf{(4)} \textbf{(a)} Si $(v_\xi)_{\xi<\alpha}$ sont des éléments +quelconques de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, +expliquer en une ligne pourquoi il existe un élément $x$ de +$\{0,1\}^{\mathbb{N}}$ différent de tous +les $v_\xi$.\quad\textbf{(b)} Si $w$ est encore un élément de +$\{0,1\}^{\mathbb{N}}$, expliquer pourquoi on peut trouver $x$ qui +soit différent de $w$ (et toujours différent des $v_\xi$). + +\begin{corrige} +\textbf{(a)} En une ligne : $\xi \mapsto v_\xi$ n'est pas surjective +par minimalité de $\mathfrak{c}$. + +\textbf{(b)} Si $\alpha$ est fini, il est évident qu'on peut trouver +$x$ différent de tous les $v_\xi$ et de $w$ (qui sont en nombre fini), +parce que $\{0,1\}^{\mathbb{N}}$ est infini. Si $\alpha$ est infini, +alors $\alpha = 1 + \alpha$ donc on n'a qu'à poser $v'_0 = w$ et +$v'_{1+\xi} = v_\xi$ pour tout $\xi < \alpha$, et appliquer (a), vu +que $\{v'_\xi : \xi<\alpha\} = \{v_\xi : \xi<\alpha\} \cup \{w\}$. +\end{corrige} + +\textbf{Définition :} Si $\sigma$ est une stratégie d'Alice au jeu +$G(A)$ et $y \in \{0,1\}^{\mathbb{N}}$, on note $\sigma \ast y$ la +confrontation dans laquelle Alice joue selon $\sigma$ et Bob joue +simplement les termes successifs de $y$ (indépendamment de ce que fait +Alice ; i.e.,\footnote{Pour enlever le moindre doute : $\sigma \ast y$ +est la suite $(t_n)_{n\in\mathbb{N}}$ définie par récurrence par : +$t_{2m} = \sigma((t_0,\ldots,t_{2m-1}))$ et $t_{2m+1} = y_m$.} $\sigma +\ast y$ est une suite binaire dont la suite des termes impairs, ceux +joués par Bob, est donnée par $y$, tandis qu'Alice joue les termes +pairs selon la stratégie $\sigma$). Symétriquement, si $\tau$ est une +stratégie de Bob et $z \in \{0,1\}^{\mathbb{N}}$, on définit $z \ast +\tau$ comme la confrontation dans laquelle Alice joue les termes de la +suite $z$ et Bob joue selon $\tau$. + +\textbf{(5)} Si $\sigma$ est une stratégie d'Alice, expliquer en une +ligne pourquoi la fonction $y \mapsto \sigma \ast y$ (de +$\{0,1\}^{\mathbb{N}}$ vers $\{0,1\}^{\mathbb{N}}$) est injective. + +\begin{corrige} +En une ligne : si $\sigma \ast y = \sigma \ast y'$, ils ont les mêmes +termes impairs, donc $y = y'$. + +(Si on préfère : $y$ se retrouve à partir de $\sigma \ast y$ comme la +suite de ses termes impairs.) +\end{corrige} + +\textbf{(6)} Si $(a_\xi)_{\xi<\alpha}$ sont des éléments quelconques +de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire de +(4)(a) et (5) qu'il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que +$\sigma \ast y$ soit différent de tous les $a_\xi$ pour $\xi<\alpha$. + +\begin{corrige} +Pour chaque $\xi < \alpha$, si $a_\xi$ est de la forme $\sigma \ast +v$, appelons $v_\xi$ le $v$ en question (qui est unique d'après (5)), +et sinon, soit $v_\xi$ quelconque (par exemple la suite nulle). (Ou, +si on préfère, on peut appeler $v_\xi$ la suite des termes impairs +de $a_\xi$ dans tous les cas.) + +D'après (4)(a), il existe $y \in \{0,1\}^{\mathbb{N}}$ qui est +différent de tous les $v_\xi$ pour $\xi < \alpha$. Alors $\sigma \ast +y$ ne peut pas être égal à $a_\xi$, car si c'était le cas, +c'est-à-dire $a_\xi = \sigma \ast y$, on aurait $\sigma \ast v_\xi = +\sigma \ast y$, donc $v_\xi = y$ par (5), contredisant la définition +de $y$. +\end{corrige} + +\textbf{Supposition :} Dans les questions (7) à (9), on suppose que +$(\sigma_\xi)_{\xi<\mathfrak{c}}$ sont des stratégies d'Alice et +$(\tau_\xi)_{\xi<\mathfrak{c}}$ des stratégies de Bob. On les +définira après la question (9), mais on n'a pas besoin d'en savoir +plus pour l'instant. + +\textbf{(7)} En supposant donnés des éléments $(a_\xi)_{\xi<\alpha}$ +et $(b_\xi)_{\xi<\alpha}$ de $\{0,1\}^{\mathbb{N}}$, où $\alpha < +\mathfrak{c}$, déduire en une ligne des questions précédentes qu'il +existe $b'$ qui soit de la forme $\sigma_\alpha \ast y$ (pour un +certain $y \in \{0,1\}^{\mathbb{N}}$), mais différent de tous les +$a_\xi$ pour $\xi<\alpha$. Expliquer aussi pourquoi il existe $a'$ +qui soit de la forme $z \ast \tau_\alpha$ (pour un certain $z \in +\{0,1\}^{\mathbb{N}}$), mais différent de tous les $b_\xi$ +pour $\xi<\alpha$ et également différent du $b'$ qu'on vient de +trouver. + +\begin{corrige} +On pose $b' = \sigma_\alpha \ast y$, où l'existence de $y$ a été +prouvée en (6) (pour $\sigma = \sigma_\alpha$). + +La construction de $a'$ est symétrique, il n'y a qu'à remarquer que $z +\mapsto z \ast \tau$ est injective, car si $z \ast \tau = z' \ast +\tau$, ils ont les mêmes termes pairs, donc $z = z'$, tout le reste +est presque pareil. La seule chose qui diffère est qu'on a un élément +de plus à éviter ($b_\alpha$), mais la question (4)(b) donne justement +ce point +\end{corrige} + +On \emph{admettra} qu'il ne pose pas de problème pour +\emph{choisir}\footnote{Ceci constitue une utilisation de l'axiome du +choix (qui a d'ailleurs déjà été utilisé dans ce qu'on a admis à la +question (2)).} de tels $a'$ et $b'$ en fonction de tous les autres +paramètres. + +\textbf{(8)} Déduire de tout ce qui précède qu'il existe $(a_\xi)_{\xi + < \mathfrak{c}}$ et $(b_\xi)_{\xi < \mathfrak{c}}$ tels que : +\begin{itemize} +\item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$ (i.e., pour + tous $\xi<\mathfrak{c}$ et tout $\zeta<\mathfrak{c}$, on a $a_\xi + \neq b_\zeta$), +\item pour tout $\xi < \mathfrak{c}$, il existe $y \in + \{0,1\}^{\mathbb{N}}$ tel que $b_\xi = \sigma_\xi \ast y$, +\item pour tout $\xi < \mathfrak{c}$, il existe $z \in + \{0,1\}^{\mathbb{N}}$ tel que $a_\xi = z \ast \tau_\xi$. +\end{itemize} +(C'est tout ce qu'on aura besoin de savoir pour les questions +suivantes.) + +\begin{corrige} +On définit $(a_\xi)_{\xi < \mathfrak{c}}$ et $(b_\xi)_{\xi < + \mathfrak{c}}$ par induction transfinie sur $\xi$ : si $(a_\xi)_{\xi + < \alpha}$ et $(b_\xi)_{\xi < \alpha}$ ont déjà été définis, pour +$\alpha < \mathfrak{c}$, alors on choisit $a_\alpha$ et $b_\alpha$ +comme l'existence a été montrée en (7). + +Pour vérifier le premier point, on distingue les cas $\xi < \zeta$ et +$\zeta \leq \xi$. Dans le premier cas, la définition même de +$b_\zeta$ était d'être différent de tous les $a_\xi$ pour $\xi < +\zeta$ ; dans le second cas, la définition même de $a_\xi$ était +d'être différent de tous les $b_\zeta$ pour $\zeta < \xi$ et aussi de +$b_\xi$. + +Les deux points suivants font partie de la définition des $b_\xi$ et +des $a_\xi$, il n'y a rien de plus à dire. +\end{corrige} + +\textbf{Définition :} Appelons maintenant $A = \{a_\xi : \xi < +\mathfrak{c}\}$ l'ensemble des $a_\xi$ qu'on vient de construire +en (8). + +\textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie $\tau_\xi$ +n'est pas gagnante pour Bob au jeu $G(A)$. Montrer que la stratégie +$\sigma_\xi$ n'est pas gagnante pour Alice à ce même jeu (attention, +ce n'est pas complètement symétrique vu que $A$ est l'ensemble +des $a_\alpha$). + +\begin{corrige} +Supposons par l'absurde que la stratégie $\tau_\xi$ soit gagnante pour +Bob : mais on a vu que $a_\xi = z \ast \tau_\xi$ pour un certain $z$, +donc $z \ast \tau_\xi$ est dans $A$, c'est-à-dire qu'Alice gagne la +confrontation, ce qui contredit le fait que $\tau_\xi$ soit gagnante +pour Bob. + +Supposons par l'absurde que la stratégie $\sigma_\xi$ soit gagnante +pour Alice : mais on a vu que $b_\xi = \sigma_\xi \ast y$ pour un +certain $y$ ; or $b_\xi$ ne peut pas être dans $A$ car il serait alors +égal à l'un des $a_\zeta$ et on a vu que ce n'était pas le cas. +C'est-à-die que Bob gagne la confrontation, ce qui contredit le fait +que $\sigma_\xi$ soit gagnante pour Bob. +\end{corrige} + +\textbf{Définition :} Posons maintenant $\sigma_\xi := +h_{\mathrm{A}}(u_\xi)$ où $h_{\mathrm{A}}$ a été définie en (1) et +$u_\xi$ en (3), et de même $\tau_\xi := h_{\mathrm{B}}(u_\xi)$. + +\textbf{(10)} Montrer que ni Alice ni Bob n'ont de stratégie gagnante +au jeu $G(A)$. + +\begin{corrige} +La fonction $h_{\mathrm{A}}$ est surjective par définition, +c'est-à-dire que n'importe quel stratégie d'Alice est de la forme +$h_{\mathrm{A}}(u)$ pour un certain $u \in \{0,1\}^{\mathbb{N}}$ ; +mais $\xi \mapsto u_\xi$ est surjective, c'est-à-dire que tout $u \in +\{0,1\}^{\mathbb{N}}$ est de la forme $u_\xi$ pour un certain $\xi$. +Autrement dit, n'importe quelle stratégie d'Alice est une des +$\sigma_\xi$. Symétriquement, n'importe quelle stratégie de Bob est +une des $\tau_\xi$. + +On vient de voir que ni $\sigma_\xi$ ni $\tau_\xi$ ne peut être une +stratégie gagnante pour le joueur concerné : donc il n'y a aucune +stratégie gagnante à ce jeu. +\end{corrige} + +\textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en +cours ? Que dire de la partie $A$ ? + +\begin{corrige} +Les résultats du cours concernent les parties ouvertes, fermées, ou +plus généralemnt boréliennes de $\{0,1\}^{\mathbb{N}}$. Ici on doit +conclure que la partie $A$ n'est pas borélienne. +\end{corrige} + +% +% +% + +\begin{otherlanguage}{english} + +\vskip1in\penalty-1000 + +\centerline{\hbox to2truein{\hrulefill}} +\centerline{\textbf{English translation}} + +\footnotesize + +(This translation is provided to help understand the French version, +but the French remains the only official text and should be referred +to in case of ambiguity or doubt, as this translation has not been +checked carefully.) + +\medbreak + +\textbf{Exercise \ref{normal-form-games-exercise}.} + +\textbf{(1)} Consider the zero-sum symmetric normal form game defined +by the following payoff matrix: +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors\\\hline +Rock&$0$&$-1$&$+1$\\ +Paper&$+1$&$0$&$-1$\\ +Scissors&$-1$&$+1$&$0$\\ +\end{tabular} +\end{center} +(Only Alice's payoff has been entered in each cell because the two +players' payoffs are opposite.) + +What are all the Nash equilibria of this game? + +\textbf{(2)} We now want to add a new option “Foobar” to the above +game, that is, we consider the game in normal form (still symmetric +and zero-sum) defined by the payoff matrix: +\begin{center} +\begin{tabular}{r|cccc} +$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors&Foobar\\\hline +Rock&$0$&$-1$&$+1$&$-x$\\ +Paper&$+1$&$0$&$-1$&$-y$\\ +Scissors&$-1$&$+1$&$0$&$-z$\\ +Foobar&$x$&$y$&$z$&$0$\\ +\end{tabular} +\end{center} +(The following three sub-questions are independent.) + +\textbf{\hphantom{(2)} (a)} Under what (necessary and sufficient) +condition on $x,y,z$ are the Nash equilibria found in (1) still Nash +equilibria for this new game?\quad\textbf{(b)} Under what (necessary +and sufficient) condition on $x,y,z$ is there a Nash equilibrium where +both players play the Foobar option (with +certainty)?\quad\textbf{(c)} Under what (necessary and sufficient) +condition on $x,y,z$ is there a Nash equilibrium where both players +play $\frac{1}{2}\text{Rock} + \frac{1}{2}\text{Foobar}$ (i.e., Rock +or Foobar each with probability $\frac{1}{2}$)? + +\textbf{(3)} We change the game: we now use the payoff matrix written +in (1), but this time the payoffs of the two players will be equal +instead of opposite (so it is no longer a zero-sum game! the players +are allies and no longer adversaries). The table gives the value of +the common payoff for both players. + +\textbf{\hphantom{(3)} (a)} Show that the Nash equilibria found in (1) +are still Nash equilibria of this new game. \quad\textbf{(b)} Give at +least one Nash equilibrium different from these. Comment briefly on +the possible difference in payoff between the Nash equilibria found in +(a) and (b). + +\medbreak + +\textbf{Exercise \ref{modified-nim-exercise}.} + +In this exercise, we consider the following game: + +Alice and Bob have piles of tokens in front of them, which represent +the state of the game (= the position). Each pile contains a finite +number (natural numbers) of tokens. The piles are numbered by natural +numbers, but only a finite number are non-empty (i.e., have $>0$ +tokens). To represent the position mathematically, we will use the +list $(n_0, n_1, n_2, \ldots, n_k)$ where $n_i$ is the number of +tokens in pile numbered i, and this implicitly means that all piles +$\geq k$ are empty. A player's move consists of removing exactly one +token from a given pile $i$ of their choice, and adding as many tokens +as they wish (including zero) to each of the piles $j<i$, including +adding different numbers to different piles. For example, from +position $(0,3,2)$ one can play to $(42,1000,1)$ or to $(0,2,2)$ or to +$(696\,729\,600,2,2)$. + +As usual, the player who cannot play has lost, meaning the one who +takes the last token has won. + +\medskip + +\textbf{(1)} Show that the game just defined necessarily ends in a +finite number of moves, regardless of the initial position and +regardless of the moves made by the players. (Careful justification +is required here.) + +\textbf{Definition:} Let us call a position “totally even” when the +number $n_i$ of tokens in each pile is even, and “not totally even” +when least one of the $n_i$ is odd. + +\textbf{(2)} Show that any move played from a totally even position +necessarily leads to a not totally even position. + +\textbf{(3)} Show that from any not totally even position there is at +least one move leading to a totally even position. + +\textbf{(4)} Deduce which positions in the game the first player has a +winning strategy, and which ones the second player has one. (Very +careful justification is required.) + +\textbf{(5)} Calculate, as a function of $n$, the Grundy value of +position $(n)$ (i.e., if there is only the pile numbered $0$, and +if it contains $n$ tokens). + +\textbf{(6)} Deduce the Grundy value of the positions $(0,1)$ and +$(1,1)$, then more generally of $(n,1)$ as a function of $n$. + +\textbf{(7)} Deduce the Grundy value of the positions $(0,2)$ and +$(1,2)$, and more generally of $(n_0,n_1)$ as a function of $n_0,n_1$. + +\textbf{(8)} Deduce the Grundy value of the position $(0,0,1)$. + +\textbf{(9)} Conjecture a general formula for the Grundy value +of any position $(n_0,n_1,\ldots,n_k)$. + +\textbf{(10)} Prove this formula. (This question is more difficult, +and it may be appropriate to save it for the end. One can draw +inspiration from the proof given in class of the calculation of the +Grundy value for the game of nim.) + +\medbreak + +\textbf{Exercise \ref{indeterminacy-exercise}.} + +In this exercise, we aim to show that there exists a game $A \subseteq +\{0,1\}^{\mathbb{N}}$ such that the Gale-Stewart game $G(A) := +G_{\{0,1\}}(A)$ is not determined (i.e., such that neither player has +a winning strategy). + +(The proof has been divided into questions allowing short answers, +sometimes as short as a single line.) + +\medskip + +\textbf{(1)} Show that there exists a bijection $h_{\mathrm{A}}$ +(resp. $h_{\mathrm{B}}$) between $\{0,1\}^{\mathbb{N}}$ and the set of +Alice's (resp. Bob's) strategies in the game $G(A)$. (\emph{Hint:} one +can quickly explain why there exists a bijection between $\mathbb{N}$ +and the set of positions where it is Alice's, or Bob's, turn to play.) + +\textbf{(2)} We \emph{admit} that there exists a well-ordering +relation $\preceq$ on $\{0,1\}^{\mathbb{N}}$. Deduce that there +exists an ordinal $\gamma$ and a bijection $\xi \mapsto u_\xi$ between +the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$ and the +set $\{0,1\}^{\mathbb{N}}$ (in other words, the $u_\xi$ are pairwise +distinct and $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$). + +\textbf{(3)} Explain in one line why there exists a smallest +ordinal $\gamma$ such that there exists a surjection $\xi \mapsto u_\xi$ +from the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$ +to the set $\{0,1\}^{\mathbb{N}}$. + +\textbf{Definition:} We will denote $\mathfrak{c}$ the ordinal whose +existence we just justified, i.e., the smallest $\gamma$ such that we +can write $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ for a +certain function $\xi \mapsto u_\xi$, which we fix in the +following. + +\textbf{(4)} \textbf{(a)} If $(v_\xi)_{\xi<\alpha}$ are any elements +of $\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, explain in +one line why there exists an element $x$ of $\{0,1\}^{\mathbb{N}}$ +different from all the $v_\xi$.\quad\textbf{(b)} If $w$ is also an +element of $\{0,1\}^{\mathbb{N}}$, explain why we can find $x$ that is +different from $w$ (and still different from the $v_\xi$). + +\textbf{Definition:} If $\sigma$ is a strategy for Alice in the game +$G(A)$ and $y \in \{0,1\}^{\mathbb{N}}$, we denote by $\sigma \ast y$ +the confrontation in which Alice plays according to $\sigma$ and Bob +plays simply the successive terms of $y$ (independently of what Alice +does; i.e.,\footnote{To remove any doubt: $\sigma \ast y$ is the +sequence $(t_n)_{n\in\mathbb{N}}$ defined by induction by: $t_{2m} = +\sigma((t_0,\ldots,t_{2m-1}))$ and $t_{2m+1} = y_m$.} $\sigma \ast y$ +is a binary sequence whose sequence of odd terms, those played by Bob, +is given by $y$, while Alice plays the even terms according to the +strategy $\sigma$). Symmetrically, if $\tau$ is a strategy for Bob +and $z \in \{0,1\}^{\mathbb{N}}$, we define $z \ast \tau$ as the +confrontation in which Alice plays the terms of the sequence $z$ and +Bob plays according to $\tau$. + +\textbf{(5)} If $\sigma$ is a strategy for Alice, explain in one line +why the function $y \mapsto \sigma \ast y$ (from +$\{0,1\}^{\mathbb{N}}$ to $\{0,1\}^{\mathbb{N}}$) is injective. + +\textbf{(6)} If $(a_\xi)_{\xi<\alpha}$ are any elements of +$\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, deduce from +(4)(a) and (5) that there exists $y \in \{0,1\}^{\mathbb{N}}$ such +that $\sigma \ast y$ is different from all $a_\xi$ for $\xi<\alpha$. + +\textbf{Assumption:} In questions (7) to (9), we assume that +$(\sigma_\xi)_{\xi<\mathfrak{c}}$ are strategies for Alice and +$(\tau_\xi)_{\xi<\mathfrak{c}}$ are strategies for Bob. We will +define them after question (9), but we don't need to know more about +them for now. + +\textbf{(7)} Assuming we are given elements $(a_\xi)_{\xi<\alpha}$ and +$(b_\xi)_{\xi<\alpha}$ of $\{0,1\}^{\mathbb{N}}$, where $\alpha < +\mathfrak{c}$, deduce in one line from the previous questions that +there exists $b'$ which is of the form $\sigma_\alpha \ast y$ (for +some $y \in \{0,1\}^{\mathbb{N}}$), but different from all $a_\xi$ for +$\xi<\alpha$. Also explain why there exists $a'$ that is of the form +$z \ast \tau_\alpha$ (for some $z \in \{0,1\}^{\mathbb{N}}$), but +different from all $b_\xi$ for $\xi<\alpha$ and also different from +the $b'$ that we have just found. + +We will admit that it poses no problem to \emph{choose} such $a'$ and +$b'$ as a function of all the other parameters. + +\textbf{(8)} Deduce from all of the above that there exist $(a_\xi)_{\xi +< \mathfrak{c}}$ and $(b_\xi)_{\xi < \mathfrak{c}}$ such that: +\begin{itemize} +\item none of the $a_\xi$ is equal to any of the $b_\zeta$ (i.e., for +all $\xi<\mathfrak{c}$ and all $\zeta<\mathfrak{c}$, we have $a_\xi +\neq b_\zeta$), +\item for all $\xi < \mathfrak{c}$, there exists $y \in +\{0,1\}^{\mathbb{N}}$ such that $b_\xi = \sigma_\xi \ast y$, +\item for all $\xi < \mathfrak{c}$, there exists $z \in +\{0,1\}^{\mathbb{N}}$ such that $a_\xi = z \ast \tau_\xi$. +\end{itemize} +(This is all we will need to know for the following questions.) + +\textbf{Definition:} Let us now call $A = \{a_\xi : \xi < +\mathfrak{c}\}$ the set of the $a_\xi$ that we just constructed +in (8). + +\textbf{(9)} Show that, for all $\xi$, the strategy $\tau_\xi$ is not +a winning one for Bob in the game $G(A)$. Show that the strategy +$\sigma_\xi$ is not a winning one for Alice in this same game (note: +this is not completely symmetric since $A$ is the set of $a_\alpha$). + +\textbf{Definition:} Now let $\sigma_\xi := h_{\mathrm{A}}(u_\xi)$ +where $h_{\mathrm{A}}$ was defined in (1) and $u_\xi$ in (3), and +similarly $\tau_\xi := h_{\mathrm{B}}(u_\xi)$. + +\textbf{(10)} Show that neither Alice nor Bob have a winning strategy +in the game $G(A)$. + +\textbf{(11)} Why doesn't this contradict the results seen in class? +What can be said about the subset $A$? + +\end{otherlanguage} + + + + +% +% +% +\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\] |