From 9edf96a06b84c8c1d739c69c9bc276aff4347a16 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 25 Feb 2016 19:00:43 +0100
Subject: Determinacy of perfect information games from Gale-Stewart games.

---
 notes-mitro206.tex | 155 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 file changed, 152 insertions(+), 3 deletions(-)

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index fa39db5..110789e 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1337,7 +1337,7 @@ premier : formellement, le jeu $G_X^{\mathrm{b}}(A)$ est le même que
 $G_X^{\mathrm{a}}(X^{\mathbb{N}}\setminus A)$ si ce n'est que les noms
 des joueurs sont échangés.
 
-\begin{defn}
+\begin{defn}\label{definition-strategies-for-gale-stewart-games}
 Pour un jeu $G_X$ comme en \ref{definition-gale-stewart-game}, une
 \textbf{stratégie} pour le premier joueur (resp. le second joueur) est
 une fonction $\varsigma$ qui à une suite finie (=position) de longueur
@@ -1371,6 +1371,15 @@ joueur a une stratégie gagnante, le jeu $G_X^{\mathrm{a}}(A)$ est dit
 \textbf{déterminé}.
 \end{defn}
 
+\thingy Il est clair que les deux joueurs ne peuvent pas avoir
+simultanément une stratégie gagnante (il suffit de considérer la suite
+$\varsigma \ast \tau$ où $\varsigma$ et $\tau$ seraient des stratégies
+gagnantes pour les deux joueurs : elle devrait simultanément
+appartenir et ne pas appartenir à $A$).
+
+En revanche, il faut se garder de croire que les jeux $G_X(A)$ sont
+toujours déterminés.
+
 \thingy\label{unshifting-notation} Introduisons la notation suivante :
 si $\underline{x} := (x_0,\ldots,x_{\ell-1})$ est une suite finie
 d'éléments de $X$ et si $A$ est un sous-ensemble de $X^{\mathbb{N}}$,
@@ -1626,7 +1635,7 @@ Alice.  C'est tout simplement qu'on a fait l'hypothèse que
 \emph{toute} suite commençant par $x_0,\ldots,x_{\ell-1}$ appartient
 à $A$.
 
-\begin{thm}[D. Gale \& F. M. Stewart, 1953]
+\begin{thm}[D. Gale \& F. M. Stewart, 1953]\label{gale-stewart-theorem}
 Si $A \subseteq X^{\mathbb{N}}$ est ouvert, ou bien fermé, alors le
 jeu $G_X(A)$ est déterminé.
 \end{thm}
@@ -1752,6 +1761,146 @@ confrontation est gagnée par Bob.
 \end{proof}
 
 
+\subsection{Détermination des jeux combinatoires}
+
+On va définir ici rapidement les notions relatives aux jeux impartiaux
+à information parfaite pour expliquer comment ces jeux peuvent se
+ramener à des jeux de Gale-Stewart et comment la détermination des
+jeux ouverts peut s'appliquer dans ce contexte :
+
+\begin{defn}\label{first-definition-impartial-combinatorial-game}
+Soit $G$ un graphe orienté (c'est-à-dire un ensemble $G$ muni d'une
+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).
+
+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
+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 un $i$ pair, on dit que le premier
+joueur \textbf{perd} et que les second \textbf{gagne}, tandis que
+lorsque le dernier $x_i$ défini l'est pour un $i$ impair, on dit que
+le premier joueur gagne et que le second perd ; enfin, lorsque $x_i$
+est défini pour tout entier naturel $i$, on dit que la confrontation
+est nulle ou que les deux joueurs \textbf{survivent} sans gagner.
+\end{defn}
+
+\thingy\label{combinatorial-to-gale-stewart} Pour un jeu comme
+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.
+
+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).
+\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
+Gale-Stewart !  Si on préfère, on peut les faire commencer à $0$, et
+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.
+
+\begin{lem}\label{openness-of-combinatorial-to-gale-stewart}
+Avec les notations de \ref{combinatorial-to-gale-stewart}, les parties
+$A$ et $B$ sont ouvertes (pour la topologie produit,
+cf. \ref{definition-product-topology}).
+\end{lem}
+\begin{proof}
+Soit $(x_1,x_2,x_3,\ldots)$ est une suite d'éléments de $X = G$.  Si
+la suite appartient à $A$ alors, par définition de $A$, il existe un
+$i$ impair tel que $x_{i+1}$ ne soit pas un voisin sortant de $x_i$ et
+tel que $x_{j+1}$ soit un voisin sortant de $x_j$ pour tout $j<i$.  On
+en déduit que le voisinage fondamental formé de toutes les suites qui
+coïncident avec $(x_1,x_2,x_3,\ldots)$ jusqu'à $x_{i+1}$ inclus est
+contenu dans $A$.  La même démonstration fonctionne pour $B$ avec $i$
+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
+exactement l'une des trois affirmations suivantes est vraie :
+\begin{itemize}
+\item le premier joueur (Alice) possède une stratégie gagnante,
+\item le second joueur (Bob) possède une stratégie gagnante,
+\item chacun des deux joueurs possède une stratégie survivante.
+\end{itemize}
+(La notion de « stratégie » ici doit se comprendre comme pouvant
+dépendre de l'histoire des coups joués précédemment : voir
+\ref{remark-historical-versus-positional-strategies} ci-dessous.)
+\end{thm}
+\begin{proof}
+Il est évident que les affirmations sont exclusives (si un joueur
+possède une stratégie gagnante, l'autre ne peut pas posséder de
+stratégie survivante, sinon on aurait une contradiction en les faisant
+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.
+
+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
+stratégie gagnante de Bob dans ce jeu est une stratégie gagnante dans
+le jeu d'origine ; ainsi, dans le jeu d'origine, soit Alice a une
+stratégie survivante soit Bob a une stratégie gagnante.
+
+En mettant ensemble ces deux disjonctions, on voit que l'un des trois
+faits énoncés est vrai.
+\end{proof}
+
+\thingy\label{remark-historical-versus-positional-strategies} La
+notion de « stratégie » implicite dans le
+théorème \ref{determinacy-of-perfect-information-games} est une notion
+\emph{historique} : puisque c'est ainsi qu'elles ont été définies
+en \ref{definition-strategies-for-gale-stewart-games}, les stratégies
+ont le droit de choisir le coup à jouer en fonction de tous les coups
+joués antérieurement.  Il se trouve en fait qu'on a les mêmes
+résultats avec des stratégies \emph{positionnelles}, c'est-à-dire, qui
+ne choisissent un coup qu'en fonction du sommet $x \in G$.
+
+\textcolor{red}{À compléter.}
+
+
 
 %
 %
@@ -2521,7 +2670,7 @@ comprendre que le joueur abandonne la partie).  Une \textbf{stratégie
   historique} est une fonction partielle $\varsigma
 \big(\bigcup_{\ell=1}^{+\infty} G^\ell\big) \dasharrow G$, où
 $\big(\bigcup_{\ell=1}^{+\infty} G^\ell\big)$ désigne l'ensemble des
-suites finies de longueur $G$ (i.e., des suites
+suites finies de $G$ de longueur non nulle (i.e., des suites
 $z_0,\ldots,z_{\ell-1}$ d'éléments de $G$ avec $\ell>0$ entier) telle
 que $\varsigma(z_0,\ldots,z_{\ell-1})$ soit un voisin sortant
 de $z_{\ell-1}$.
-- 
cgit v1.2.3