diff options
| -rw-r--r-- | notes-mitro206.tex | 75 |
1 files changed, 70 insertions, 5 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index ded15ef..15ac029 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -850,7 +850,8 @@ 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 Les \textbf{jeux de Gale-Stewart} : soit $A$ un sous-ensemble de +\thingy\label{introduction-gale-stewart-games} Les \textbf{jeux de + Gale-Stewart} (cf. section \ref{gale-stewart-games}) : soit $A$ un sous-ensemble de $\mathbb{N}^{\mathbb{N}}$ ou de $\{0,1\}^{\mathbb{N}}$ ou de $[0,1]$. Alice et Bob choisissent tour à tour un élément de $\mathbb{N}$ (dans le premier cas) ou de $\{0,1\}$ (dans les deux suivants). Ils jouent @@ -903,6 +904,10 @@ sexes (\ref{battle-of-sexes}). On évoque plus particulièrement les jeux à somme nulle en \ref{zero-sum-games} : on pensera alors à des jeux comme pierre-papier-ciseaux (cf. \ref{rock-paper-scissors}). +La section \ref{gale-stewart-games} introduit la notion de jeux de +Gale-Stewart et prouve un théorème fondamental de détermination (la +détermination des jeux \emph{ouverts}). + La section \ref{section-well-founded-induction} introduit la notion de graphe bien-fondée et d'induction bien-fondée qui est essentielle pour la suite. @@ -1281,6 +1286,69 @@ compact $C_0 \neq \varnothing$ inclus dans $C$. % % +\section{Jeux de Gale-Stewart et détermination}\label{gale-stewart-games} + +\subsection{Définitions} + +\begin{defn}\label{definition-gale-stewart-game} +Soit $X$ un ensemble quelconque (à titre indicatif, les cas $X = +\{0,1\}$ et $X = \mathbb{N}$ seront particulièrement intéressants). +Soit $A$ un sous-ensemble de $X^{\mathbb{N}}$. Le \textbf{jeu de + Gale-Stewart} $G_X(A)$ est défini de la manière suivante : Alice et +Bob choisissent tour à tour un élément de $X$ (autrement dit, Alice +choisit $x_0 \in X$ puis Bob choisit $x_1 \in X$ puis Alice choisit +$x_2 \in X$ et ainsi de suite). Ils jouent un nombre infini de tours, +« à la fin » desquels la suite $(x_0,x_1,x_2,\ldots)$ de leurs coups +définit un élément de $X^{\mathbb{N}}$ : si cet élément appartient à +$A$, Alice \textbf{gagne}, sinon c'est Bob (la partie n'est jamais +nulle). + +Dans ce contexte, les suites finies d'éléments de $X$ s'appellent les +\textbf{positions} (y compris la suite vide, qui peut s'appeler +position initiale) de $G_X(A)$, ou de $G_X$ vu que $A$ n'intervient +pas ici ; leur ensemble $\bigcup_{\ell=0}^{+\infty} X^\ell$ s'appelle +parfois l'\textbf{arbre} du jeu $G_X$. Une \textbf{partie} ou +\textbf{confrontation}\footnote{Le mot « partie » peut malheureusement + désigner soit un sous-ensemble soit une partie d'un jeu au sens + défini ici : le mot « confrontation » permet d'éviter l'ambiguïté.} +de $G_X$ est une suite $(x_0,x_1,x_2,\ldots) \in X^{\mathbb{N}}$. +\end{defn} + +\begin{defn} +Pour un jeu $G_X$ comme en \ref{definition-gale-stewart-game}, une +\textbf{stratégie} pour Alice (resp. Bob) est une fonction $\varsigma$ +qui à une suite finie de longueur paire (resp. impaire) d'éléments +de $X$ associe un élément de $X$, autrement dit une fonction +$\big(\bigcup_{\ell=0}^{+\infty} X^{2\ell}\big) \to X$ +(resp. $\big(\bigcup_{\ell=0}^{+\infty} X^{2\ell+1}\big) \to X$). + +Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G_X$ +on a $\varsigma((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ pair (y +compris $\varsigma(()) = x_0$), on dit qu'Alice a joué la partie selon +la stratégie $\varsigma$ ; de même, lorsque +$\tau((x_0,\ldots,x_{i-1})) = x_i$ pour chaque $i$ impair, on dit que +Bob a joué la partie selon la stratégie $\tau$. + +Si $\varsigma$ et $\tau$ sont deux stratégies pour Alice et Bob +respectivement, on définit $\varsigma \ast \tau$ comme la partie jouée +lorsque Alice joue selon $\varsigma$ et Bob selon $\tau$ : autrement +dit, $x_i$ est défini par $\varsigma((x_0,\ldots,x_{i-1}))$ si $i$ est +pair ou $\tau((x_0,\ldots,x_{i-1}))$ si $i$ est impair. + +Donnée une partie $A$ de $X^{\mathbb{N}}$, la stratégie $\varsigma$ +pour Alice est dite \textbf{gagnante} (dans $G_X(A)$) lorsque Alice +gagne toute partie où elle joue selon $\varsigma$. La stratégie +$\tau$ pour Bob est dite \textbf{gagnante} lorsque Bob gagne toute +partie où il joue selon $\tau$. Lorsque l'un ou l'autre joueur a une +stratégig gagnante, le jeu est dit \textbf{déterminé}. +\end{defn} + + + +% +% +% + \section{Théorie de l'induction bien-fondée}\label{section-well-founded-induction} Le but de cette section est de présenter les outils fondamentaux sur @@ -1989,10 +2057,7 @@ quelle position de n'importe quel jeu. \begin{defn} Soit $G$ un jeu comme en \ref{definition-impartial-combinatorial-game}. Une \textbf{partie} -ou \textbf{confrontation}\footnote{Le mot « partie » peut - malheureusement désigner soit un sous-ensemble soit une partie d'un - jeu au sens défini ici : le mot « confrontation » permet d'éviter - l'ambiguïté.} de $G$ est une suite finie ou infinie $(x_i)$ de +ou \textbf{confrontation} de $G$ est une suite finie ou infinie $(x_i)$ de sommets de $G$ telle que $x_0$ soit la position initiale et que pour chaque $i$ pour lequel $x_{i+1}$ soit défini, ce dernier soit un voisin sortant de $x_i$. Lorsque le dernier $x_i$ défini l'est pour |