From 3b6d9b51918800ab219b39fd83423091b6b22d8b Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Tue, 8 Mar 2016 14:20:38 +0100
Subject: Various clarifications in wording in the
 combinatorial-to-Gale-Stewart argument.

---
 notes-mitro206.tex | 84 +++++++++++++++++++++++++++++++-----------------------
 1 file changed, 48 insertions(+), 36 deletions(-)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 8bd781f..d30e163 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1982,14 +1982,15 @@ relation $E$ irreflexive dont les éléments sont appelés arêtes du
 graphe, cf. \ref{definitions-graphs} ci-dessous pour les définitions
 générales) dont les sommets seront appelés \textbf{positions} de $G$,
 et soit $x_0$ un sommet de $G$ qu'on appellera \textbf{position
-  initiale}.  Le \textbf{jeu impartial à information parfaite} associé
-à ces données est défini de la manière suivante : partant de $x =
-x_0$, Alice et Bob choisissent tour à tour un voisin sortant de $x$,
-autrement dit, Alice choisit une arête $(x_0,x_1)$ de $G$, puis Bob
-choisit une arête $(x_1,x_2)$ de $G$, puis Alice choisit une arête
-$(x_2,x_3)$, et ainsi de suite.  Si un joueur ne peut plus jouer, il a
-perdu ; si la confrontation dure un temps infini, elle est considérée
-comme nulle (ni gagnée ni perdue par les joueurs).
+  initiale}.  Le \textbf{jeu combinatoire impartial à information
+  parfaite} associé à ces données est défini de la manière suivante :
+partant de $x = x_0$, Alice et Bob choisissent tour à tour un voisin
+sortant de $x$, autrement dit, Alice choisit une arête $(x_0,x_1)$
+de $G$, puis Bob choisit une arête $(x_1,x_2)$ de $G$, puis Alice
+choisit une arête $(x_2,x_3)$, et ainsi de suite.  Si un joueur ne
+peut plus jouer, il a perdu ; si la confrontation dure un temps
+infini, elle est considérée comme nulle (ni gagnée ni perdue par les
+joueurs).
 
 Une \textbf{partie} ou \textbf{confrontation} de ce jeu est une suite
 finie ou infinie $(x_i)$ de sommets de $G$ telle que $x_0$ soit la
@@ -2007,27 +2008,36 @@ est nulle ou que les deux joueurs \textbf{survivent} sans gagner.
 en \ref{first-definition-impartial-combinatorial-game}, va définir un,
 ou plutôt deux, jeux de Gale-Stewart : l'intuition est que si un
 joueur enfreint la « règle » du jeu (i.e., choisit un sommet qui n'est
-pas un voisin sortant du sommet actuel), il a immédiatement perdu.
+pas un voisin sortant du sommet actuel), il a immédiatement perdu — il
+n'y a manifestement pas grande différence entre avoir un jeu où un
+joueur \emph{ne peut pas} faire un certain coup et un jeu où si ce
+joueur fait ce coup il a immédiatement perdu (quoi qu'il se passe par
+la suite).  On va définir deux jeux de Gale-Stewart plutôt qu'un parce
+qu'un jeu de Gale-Stewart a forcément un gagnant (il n'y a pas de
+partie nulle), donc on va définir un jeu où les parties nulles sont
+comptées au bénéfice de Bob et un autre où elles sont comptées au
+bénéfice d'Alice.
 
 Autrement dit, soit $G$ un graphe orienté et $x_0 \in G$.  On pose $X
 = G$ et on partitionne l'ensemble des suites à valeurs dans $X$ en
 trois :
 \begin{itemize}
-\item l'ensemble $D$ des (confrontations nulles, c'est-à-dire des)
-  suites $(x_1,x_2,x_3,\ldots)$ telles que pour chaque $i \in
-  \mathbb{N}$ (y compris $0$) le sommet $x_{i+1}$ soit un voisin
-  sortant de $x_i$ (c'est-à-dire : $(x_i,x_{i+1})$ est une arête
-  de $G$) (bref, personne n'a enfreint la règle),
-\item l'ensemble $A$ des (confrontations gagnées par Alice,
-  c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles qu'il existe
-  $i \in \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un voisin sortant
-  de $x_i$ et que le plus petit tel $i$ soit \emph{impair} (i.e., Bob a
-  enfreint la règle en premier),
-\item l'ensemble $B$ des (confrontations gagnées par Bob, c'est-à-dire
-  des) suites $(x_1,x_2,x_3,\ldots)$ telles qu'il existe $i \in
-  \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un voisin sortant
-  de $x_i$ et que le plus petit tel $i$ soit \emph{pair} (i.e., Alice
-  a enfreint la règle en premier).
+\item l'ensemble $D$ des (confrontations nulles dans le jeu
+  combinatoire, c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles
+  que pour chaque $i \in \mathbb{N}$ (y compris $0$) le sommet
+  $x_{i+1}$ soit un voisin sortant de $x_i$ (c'est-à-dire :
+  $(x_i,x_{i+1})$ est une arête de $G$) (bref, personne n'a enfreint
+  la règle),
+\item l'ensemble $A$ des (confrontations gagnées par Alice dans le jeu
+  combinatoire, c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles
+  qu'il existe $i \in \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un
+  voisin sortant de $x_i$ et que le plus petit tel $i$ soit
+  \emph{impair} (i.e., Bob a enfreint la règle en premier),
+\item l'ensemble $B$ des (confrontations gagnées par Bob dans le jeu
+  combinatoire, c'est-à-dire des) suites $(x_1,x_2,x_3,\ldots)$ telles
+  qu'il existe $i \in \mathbb{N}$ pour lequel $x_{i+1}$ n'est pas un
+  voisin sortant de $x_i$ et que le plus petit tel $i$ soit
+  \emph{pair} (i.e., Alice a enfreint la règle en premier).
 \end{itemize}
 (On a choisi ici d'indicer les suites par les entiers naturels non
 nuls : il va de soi que ça ne change rien à la théorie des jeux de
@@ -2036,9 +2046,9 @@ mettre dans $A$ toutes les suites qui ne commencent pas par $x_0$.)
 
 Le jeu de Gale-Stewart $G_X(A)$ est essentiellement identique au jeu
 considéré en \ref{first-definition-impartial-combinatorial-game}, à
-ceci près que les nuls sont comptés comme des gains de Bob ; le jeu
-$G_X(A \cup D)$, pour sa part, est lui aussi identique à ceci près que
-les nuls sont comptés comme des gains d'Alice.
+ceci près que les confrontations nulles sont comptées comme des gains
+de Bob ; le jeu $G_X(A \cup D)$, pour sa part, est lui aussi identique
+à ceci près que les nuls sont comptés comme des gains d'Alice.
 
 \begin{lem}\label{openness-of-combinatorial-to-gale-stewart}
 Avec les notations de \ref{combinatorial-to-gale-stewart}, les parties
@@ -2057,8 +2067,8 @@ pair.
 \end{proof}
 
 \begin{thm}\label{determinacy-of-perfect-information-games}
-Soit $(G,x_0)$ un jeu impartial à information parfaite comme
-en \ref{first-definition-impartial-combinatorial-game}.  Alors
+Soit $(G,x_0)$ un jeu combinatoire impartial à information parfaite
+comme en \ref{first-definition-impartial-combinatorial-game}.  Alors
 exactement l'une des trois affirmations suivantes est vraie :
 \begin{itemize}
 \item le premier joueur (Alice) possède une stratégie gagnante,
@@ -2078,13 +2088,15 @@ jouer l'une contre l'autre).
 Avec les notations de \ref{combinatorial-to-gale-stewart},
 d'après \ref{openness-of-combinatorial-to-gale-stewart}, les parties
 $A$ et $B$ sont ouvertes, donc \ref{gale-stewart-theorem} montre que
-les jeux définis par $A$ et $A \cup D = X\setminus B$ sont déterminés.
-
-Mais une stratégie gagnante d'Alice dans le jeu défini par $A$ est une
-stratégie gagnante dans le jeu d'origine, tandis qu'une stratégie
-gagnante de Bob dans ce jeu est une stratégie survivante dans le jeu
-d'origine ; ainsi, dans le jeu d'origine, soit Alice a une stratégie
-gagnante soit Bob a une stratégie survivante.
+les jeux définis par l'ouvert $A$ et le fermé $A \cup D = X\setminus
+B$ sont déterminés.
+
+Mais une stratégie gagnante d'Alice dans le jeu de Gale-Stewart défini
+par $A$ est une stratégie gagnante dans le jeu combinatoire d'origine,
+tandis qu'une stratégie gagnante de Bob dans ce jeu de Gale-Stewart
+est une stratégie survivante dans le jeu d'origine ; ainsi, dans le
+jeu d'origine, soit Alice a une stratégie gagnante soit Bob a une
+stratégie survivante.
 
 De même, une stratégie gagnante d'Alice dans le jeu défini par $A \cup
 D$ est une stratégie survivante dans le jeu d'origine, tandis qu'une
-- 
cgit v1.2.3

