diff options
| -rw-r--r-- | notes-mitro206.tex | 49 |
1 files changed, 35 insertions, 14 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index d37e8a3..fce6917 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -449,20 +449,6 @@ Cet exemple sert à illustrer le fait que dans l'étude des jeux sous forme normale, l'hypothèse de finitude des choix sera généralement essentielle. -\thingy Le \textbf{jeu topologique de Choquet} : soit $X$ un espace -métrique (ou topologique) fixé à l'avance. Uriel et Vania choisissent -tour à tour un ouvert non vide de ($X$ contenu dans) l'ouvert -précédemment choisi : i.e., Uriel choisit $\varnothing \neq U_0 -\subseteq X$, puis Vania choisit $\varnothing \neq V_0 \subseteq U_0$, -puis Uriel choisit $\varnothing \neq U_1 \subseteq V_0$ et ainsi de -suite. Le jeu continue pendant un nombre infini de tours indicés par -les entiers naturels. À la fin, on a bien sûr $\bigcap_{n=0}^{\infty} -U_n = \bigcap_{n=0}^{\infty} V_n$ : on dit qu'Uriel gagne le jeu si -cette intersection est vide, Vania le gagne si elle est non-vide. On -peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une -stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en -a une. - \thingy\label{introduction-graph-game} Le jeu d'un graphe : soit $G$ un graphe orienté (cf. \ref{definitions-graphs} ci-dessous pour la définition) et $x_0$ un sommet de $G$. Partant de $x_0$, Alice et Bob @@ -492,6 +478,41 @@ défini en \ref{introduction-graph-game}) : on verra que la théorie de Grundy permet de décrire exactement la stratégie gagnante (et pour qui). +\thingy Le \textbf{jeu de l'hydre} : Hercule essaie de terrasser +l'hydre. Le joueur qui joue l'hydre commence par dessiner (i.e., +choisir) un arbre (fini, enraciné), la forme initiale de l'hydre. +Puis Hercule choisit une \emph{tête} de l'hydre, c'est-à-dire une +feuille $x$ de l'arbre, et la décapite en la supprimant de l'arbre. +L'hydre se reproduit alors de la façon suivante : soit $y$ le nœud +parent de $x$ dans l'arbre, et $z$ le nœud parent de $y$ (grand-parent +de $x$, donc) : si l'un ou l'autre n'exite pas, rien ne se passe +(l'hydre passe son tour) ; sinon, l'hydre choisit un entier naturel +$n$ (aussi grand qu'elle veut) et attache à $z$ autant de nouvelles +copies de $y$ (mais sans la tête $x$ qui a été décapitée) qu'elle le +souhaite. Hercule gagne s'il réussit à décapiter le dernier nœud de +l'hydre ; l'hydre gagnerait si elle réussissait à survivre +indéfiniment. + +Ce jeu est particulier en ce que, mathématiquement, non seulement +Hercule possède une stratégie gagnante, mais en fait Hercule gagne +\emph{toujours}, quoi qu'il fasse et quoi que fasse l'hydre. +Pourtant, en pratique, l'hydre peut facilement s'arranger pour +survivre un temps inimaginablement long. + +\thingy Le \textbf{jeu topologique de Choquet} : soit $X$ un espace +métrique (ou topologique) fixé à l'avance. Uriel et Vania choisissent +tour à tour un ouvert non vide de ($X$ contenu dans) l'ouvert +précédemment choisi : i.e., Uriel choisit $\varnothing \neq U_0 +\subseteq X$, puis Vania choisit $\varnothing \neq V_0 \subseteq U_0$, +puis Uriel choisit $\varnothing \neq U_1 \subseteq V_0$ et ainsi de +suite. Le jeu continue pendant un nombre infini de tours indicés par +les entiers naturels. À la fin, on a bien sûr $\bigcap_{n=0}^{\infty} +U_n = \bigcap_{n=0}^{\infty} V_n$ : on dit qu'Uriel gagne le jeu si +cette intersection est vide, Vania le gagne si elle est non-vide. On +peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une +stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vania qui en +a une. + \subsection{Remarques} |