Transitive collapse, combinatorial games.

1 files changed, 182 insertions, 35 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 25279c8..72876d7 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -95,20 +95,20 @@ quelques unes de ces théories des jeux.
 
 \thingy Une tentative pour approcher la notion de jeu mathématique :
 le jeu possède un \textbf{état}, qui évolue dans un ensemble (fini ou
-infini) d'états possibles ; un certain nombre de \textbf{joueurs}
-choisissent, simultanément ou consécutivement, un \textbf{coup} à
-jouer parmi différentes \textbf{options}, en fonction de l'état
-courant, ou peut-être seulement d'une fonction de l'état courant ; ce
-coup peut éventuellement faire intervenir un aléa (hasard voulu par le
-joueur) ; l'état du jeu évolue en fonction des coups des joueurs et
-éventuellement d'un autre aléa (hasard intrinsèque au jeu) ; au bout
-d'un certain nombre de coups (fini ou infini), la règle du jeu
-attribue, en fonction de l'état final, ou de son évolution complète,
-un \textbf{gain} à chaque joueur, ce gain pouvant être un réel (gain
-numérique), l'étiquette « gagné » / « perdu », ou encore autre chose,
-et chaque joueur cherche en priorité à maximiser son gain (i.e., à
-gagner le plus possible, ou à gagner tout court), ou dans le cas
-probabiliste, son espérance de gain.
+infini) d'états ou \textbf{positions} possibles ; un certain nombre de
+\textbf{joueurs} choisissent, simultanément ou consécutivement, un
+\textbf{coup} à jouer parmi différentes \textbf{options}, en fonction
+de l'état courant, ou peut-être seulement d'une fonction de l'état
+courant ; ce coup peut éventuellement faire intervenir un aléa (hasard
+voulu par le joueur) ; l'état du jeu évolue en fonction des coups des
+joueurs et éventuellement d'un autre aléa (hasard intrinsèque au
+jeu) ; au bout d'un certain nombre de coups (fini ou infini), la règle
+du jeu attribue, en fonction de l'état final, ou de son évolution
+complète, un \textbf{gain} à chaque joueur, ce gain pouvant être un
+réel (gain numérique), l'étiquette « gagné » / « perdu », ou encore
+autre chose, et chaque joueur cherche en priorité à maximiser son gain
+(i.e., à gagner le plus possible, ou à gagner tout court), ou dans le
+cas probabiliste, son espérance de gain.
 
 Mais même cette définition très vague est incomplète !, par exemple
 dans le cas des jeux différentiels, les coups n'ont pas lieu tour à
@@ -138,7 +138,7 @@ ne connaissent pas toute la règle du jeu (voir « information
 \thingy Le \textbf{nombre de joueurs} est généralement $2$.  On peut
 néanmoins étudier des jeux multi-joueurs, ce qui pose des questions
 d'alliances et compliquer la question des buts (un joueur peut être
-incapable de gagner lui-même mais être en position de décider quel
+incapable de gagner lui-même mais être en situation de décider quel
 autre joueur gagnera : on parle de « kingmaker »).  On peut aussi
 étudier des jeux à un seul joueur (jouant contre le hasard), voire à
 zéro joueurs (systèmes dynamiques), mais ceux-ci relèvent plutôt
@@ -197,15 +197,16 @@ on ne considérera que des jeux à information complète [et toute
   occurrence des mots « information complète » sera probablement un
   lapsus pour « information parfaite »].)
 
-\thingy Le nombre de positions, comme le nombre d'options dans une
-position donnée, ou comme le nombre de coups, peut être \textbf{fini
-  ou infini}.  Même si l'étude des jeux finis (de différentes
-manières) est la plus intéressante pour des raisons pratiques, toutes
-sortes de jeux infinis peuvent être considérés, par exemple en logique
-(voir plus loin sur l'axiome de détermination).  Pour un jeu à durée
-infinie, le gagnant pourra être déterminé, par exemple, par toute la
-suite des coups effectués par les deux joueurs ; on peut même
-introduire des coups après un nombre infini de coups, etc.
+\thingy Le nombre de positions (= états possibles), comme le nombre
+d'options dans une position donnée, ou comme le nombre de coups, peut
+être \textbf{fini ou infini}.  Même si l'étude des jeux finis (de
+différentes manières) est la plus intéressante pour des raisons
+pratiques, toutes sortes de jeux infinis peuvent être considérés, par
+exemple en logique (voir plus loin sur l'axiome de détermination).
+Pour un jeu à durée infinie, le gagnant pourra être déterminé, par
+exemple, par toute la suite des coups effectués par les deux joueurs ;
+on peut même introduire des coups après un nombre infini de coups,
+etc.
 
 De même, l'ensemble des positions, des options ou des temps peut être
 \textbf{discret ou continu}.  Dans ce cours, on s'intéressera presque
@@ -273,7 +274,7 @@ nul ; sinon, papier gagne sur pierre, ciseaux gagne sur papier et
 pierre gagne sur ciseaux (l'intérêt étant qu'il s'agit d'un « ordre »
 cyclique, totalement symétrique entre les options).  Il s'agit
 toujours d'un jeu à somme nulle (disons que gagner vaut $+1$ et perdre
-vaut $-1$), et cette fois les deux joueurs sont en position
+vaut $-1$), et cette fois les deux joueurs sont en situation
 complètement symétrique.  On verra que la meilleure stratégie possible
 consiste à choisir chacune des options avec probabilité $\frac{1}{3}$
 (ceci assure une espérance de gain nul quoi que fasse l'autre joueur).
@@ -366,14 +367,34 @@ peut se convaincre que si $X = \mathbb{Q}$, alors Uriel possède une
 stratégie gagnante, tandis que si $X = \mathbb{R}$ c'est Vivien 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
+choisissent tour à tour une arête à emprunter pour arriver dans un
+nouveau sommet (c'est-à-dire : Alice choisit un voisin sortant $x_1$
+de $x_0$, puis Bob un voisins ortant $x_2$ de $x_1$, puis Alice $x_3$
+de $x_2$ et ainsi de suite).  \emph{Le perdant est celui qui ne peut
+  plus jouer}, et si ceci ne se produit jamais (si on définit un
+chemin infini $x_0, x_1, x_2, x_3,\ldots$) alors la partie est
+déclarée nulle (ceci ne peut pas se produire lorsque le graphe $G$ est
+« bien-fondé »).  On verra qu'il s'agit là du cadre général dans
+lequel on étudie la théorie combinatoire des jeux impartiaux à
+information parfaite
+(cf. \ref{definition-impartial-combinatorial-game}).
+
+Dans une variante du jeu, celui qui ne peut plus jouer gagne au lieu
+de perdre : on parle alors de la variante « misère » du jeu.
+
 \thingy Le \textbf{jeu de Nim} : un certain nombre d'allumettes sont
 arrangées en plusieurs lignes ; chacun leur tour, Alice et Bob
 retirent des alumettes, au moins une à chaque fois, et autant qu'ils
 veulent, mais \emph{d'une ligne seulement} ; le gagnant est celui qui
 retire la dernière allumette (de façon équivalente, le perdant est
 celui qui ne peut pas jouer).  Il s'agit ici d'un jeu à deux joueurs
-impartial à connaissance parfaite : on verra que la théorie de Grundy
-permet de décrire exactement la stratégie gagnante (et pour qui).
+impartial à connaissance parfaite (un cas particulier du jeu général
+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).
 
 
 \subsection{Remarques}
@@ -765,7 +786,7 @@ compact $C_0 \neq \varnothing$ inclus dans $C$.
 
 \subsection{Graphes orientés bien-fondés}
 
-\begin{defn}
+\begin{defn}\label{definitions-graphs}
 Un \textbf{graphe orienté [simple]} est la donnée d'un ensemble $G$ et
 d'une partie $E$ de $G^2$ ne rencontrant pas la diagonale (i.e., un
 ensemble de couples $(x,y)$ avec $x\neq y$) : si on préfère, il s'agit
@@ -1060,16 +1081,24 @@ On verra que la notion de fonction de Grundy, et particulièrement le
 fait que la valeur soit nulle ou pas, a énormément d'importance dans
 l'étude de la théorie des jeux impartiaux.
 
+
+\subsection{Écrasement transitif}
+
 \begin{defn}\label{definition-transitive-collapse}
 Soit $G$ un graphe orienté bien-fondé.  En utilisant le
 théorème \ref{well-founded-definition} (modulo la remarque qui suit),
 on définit alors une fonction $f$ sur $G$ par $f(x) = \{f(y) :
-y\in\outnb(x)\}$.  L'image de $G$ par la fonction $f$ (c'est-à-dire
+y\in\outnb(x)\}$.  L'image $f(G)$ de $G$ par la fonction $f$ (c'est-à-dire
 l'ensemble des $f(x)$ pour $x\in G$) s'appelle l'\textbf{écrasement
   transitif} ou \textbf{écrasement de Mostowski} de $G$, tandis que
 $f$ s'appelle la fonction d'écrasement, et la valeur $f(x)$ (qui n'est
 autre que l'écrasement transitif de l'aval de $x$ vu comme un graphe
 orienté) s'appelle l'écasement transitif du sommet $x$.
+
+On considérera l'écrasement $f(G)$ de $G$ comme un graphe orienté, en
+plaçant une arête de $u$ vers $v$ lorsque $v \in u$ ; autrement dit,
+lorsque $v = f(y)$ et $u = f(x)$ pour certains $x,y$ de $G$ tels qu'il
+existe une arête de $x$ vers $y$.
 \end{defn}
 
 \thingy En particulier, un puits a pour écrasement $\varnothing$, un
@@ -1079,6 +1108,11 @@ que de tels sommets a pour écrasement $\{\{\varnothing\}\}$ tandis que
 s'il a aussi des sommets terminaux pour voisins sortants ce sera
 $\{\varnothing,\penalty0 \{\varnothing\}\}$, et ainsi de suite.
 
+La terminologie « transitif » fait référence au fait qu'un ensemble
+$E$ est dit transitif lorsque $v \in u\in E$ implique $v \in E$ (de
+façon équivalente, $E \subseteq \mathscr{P}(E)$ où $\mathscr{P}(E)$
+est l'ensemble des parties de $E$) : c'est le cas de $f(G)$ ici.
+
 Il y a une subtilité ensembliste dans la définition ci-dessus, c'est
 qu'on ne peut pas donner \textit{a priori} un ensemble $Z$ dans lequel
 $f$ prend sa valeur : il faut en fait appliquer une généralisation
@@ -1093,7 +1127,12 @@ sommets $x$ et $x'$ ayant le même ensemble de voisins sortants ($\outnb(x)
 = \outnb(x')$) sont égaux.
 \end{defn}
 
-\begin{prop}
+Pour bien comprendre et utiliser la définition ci-dessus, il est
+pertinent de rappeler que \emph{deux ensembles sont égaux si et
+  seulement si il sont les mêmes éléments} (\textbf{axiome
+  d'extensionalité}).
+
+\begin{prop}\label{extensional-iff-collapse-injective}
 Un graphe orienté bien-fondé est extensionnel si et seulement si sa
 fonction d'écrasement $f$ définie
 en \ref{definition-transitive-collapse} est injective.
@@ -1104,13 +1143,121 @@ particulier $f(x) = f(x')$ (puisque $f(x)$ est définie comme l'image
 par $f$ de $\outnb(x)$), donc $x = x'$.  Ceci montre que $G$ est
 extensionnel.
 
-Réciproquement, $G$ extensionnel et montrons par induction bien-fondée que $f$
-est injective sur l'aval de tout sommet $x$.  Soit $P$ l'ensemble des
-$x$ tels que $f$ restreinte à l'aval de $x$ soit injective.  Soit $x$
-un sommet dont tous les voisins sortants appartiennent à $P$ :
-\textcolor{red}{à finir.}
+Réciproquement, $G$ extensionnel et montrons que $f$ est injective,
+c'est-à-dire que $f(x) = f(x')$ implique $x = x'$.  On va procéder par
+induction bien-fondée sur le graphe $G^2$ dont les sommets sont les
+couples $(x,x')$ de sommets de $G$, avec une arête de $(x,x')$ vers
+$(y,y')$ lorsqu'il y en a de $x$ vers $y$ \emph{et} de $x'$
+vers $y'$ : il est clair que $G^2$ est bien-fondé ; soit $P$
+l'ensemble des sommets $(x,x')$ de $G^2$ tels que $f(x) = f(x')$
+implique $x=x'$ (autrement dit, l'ensemble des sommets tels que
+$(x,x')$ tels que $x=x'$ \emph{ou bien} $f(x) \neq f(x')$).  Soit
+$(x,x')$ un sommet de $G^2$ dont tous les voisins sortants vérifient
+l'hypothèse d'induction (i.e., appartiennent à $P$) : on suppose $f(x)
+= f(x')$ et on veut montrer $x = x'$ pour pouvoir conclure $P = G^2$.
+Or $f(x) \subseteq f(x')$ signifie que tout $f(y) \in f(x)$ appartient
+à $f(x')$, c'est-à-dire que pour tout voisin sortant $y$ de $x$ il
+existe un voisin sortant $y'$ de $x'$ pour lequel $f(y) = f(y')$, et
+l'hypothèse d'induction montre alors $y = y'$ : ainsi, $\outnb(x)
+\subseteq \outnb(x')$, et par symétrie, $f(x) = f(x')$ montre
+$\outnb(x) = \outnb(x')$ donc, par extensionalité de $G$, on a $x =
+x'$ comme on le voulait.
 \end{proof}
 
+\thingy Si $G$ est un graphe orienté (non nécessairement bien-fondé),
+et si $\sim$ est une relation d'équivalence sur l'ensemble des sommets
+de $G$, on peut définir un \emph{graphe quotient} $G/\sim$ dont les
+sommets sont les classes d'équivalences pour $\sim$ de sommets de $G$
+et dont les arêtes sont les couples $(\bar x,\bar y)$ de classes
+telles qu'il existe une arête $(x,y)$ (i.e., de $x$ vers $y$) dans $G$
+avec $\bar x$ classe de $x$ et $\bar y$ celle de $y$ ; si ce graphe
+est extensionnel, on peut dire abusivement que $\sim$ l'est :
+concrètement, cela signifie que pour tous $x,x' \in G$, si pour chaque
+voisin sortant $y$ de $x$ il existe un voisin sortant $y'$ de $x'$
+avec $y \sim y'$ et que la même chose vaut en échangeant $x$ et $x'$,
+alors $x \sim x'$.  Une intersection quelconque de relations
+d'équivalence extensionnelles sur $G$ est encore une relation
+d'équivalence extensionnelle, donc il existe une plus petite relation
+d'équivalence extensionnelle $\equiv$ sur $G$, c'est-à-dire un plus
+grand quotient $G/\equiv$ de $G$ qui soit extensionnel (« plus grand »
+au sens où tout quotient de $G$ par une relation d'équivalence se
+factorise à travers ce quotient $G/\equiv$).
+
+Le contenu essentiel de la
+proposition \ref{extensional-iff-collapse-injective} est que
+l'écrasement transitif $f(G)$ d'un graphe $G$ bien-fondé réalise ce
+plus grand quotient extensionnel $G/\equiv$ : la relation $f(x) =
+f(x')$ sur $G$ est précisément la plus petite relation d'équivalence
+extensionnelle $\equiv$ sur $G$ (en effet, la relation $f(x) = f(x')$
+est évidemment extensionnelle, donc contient $\equiv$ par définition
+de celle-ci, mais l'écrasement de $G/\equiv$ est le même que celui
+de $G$, et comme la fonction d'écrasement est injective sur
+$G/\equiv$, on a bien $f(x) = f(x')$ ssi $x\equiv x'$).
+
+
+\subsection{Jeux impartiaux à information parfaite}
+
+\begin{defn}\label{definition-impartial-combinatorial-game}
+Un jeu \textbf{impartial à information parfaite} est un graphe
+orienté $G$ muni d'un sommet $x_0$ appelé \textbf{position initiale}
+et vérifiant de plus :
+\begin{itemize}
+\item pour un jeu « court » : $G$ est fini acyclique (ou de façon
+  équivalente, fini et bien-fondé) ;
+\item pour un jeu « terminant » : $G$ est bien-fondé ;
+\item pour un jeu « fini à boucles » : $G$ est fini.
+\item pour un jeu « non nécessairement terminant » : (aucune
+  hypothèse).
+\end{itemize}
+On supposera de plus que tout sommet de $G$ est accessible à partir
+de $x_0$ (si ce n'est pas le cas, il reviendra au même de supprimer
+tous les sommets inaccessibles, assurant du coup cette hypothèse).
+\end{defn}
+
+La terminologie est malheureusement peu standardisée : la plupart des
+auteurs font implicitement une des deux hypothèses
+(« bien-fondé »=« terminant », et/ou « fini ») sur le jeu $G$, le cas
+« court » étant la conjonction des deux.  Ici, on fera le plus souvent
+l'hypothèse que $G$ est terminant.
+
+\begin{defn}
+Pour un jeu $G$ comme
+en \ref{definition-impartial-combinatorial-game}, une
+\textbf{stratégie} est une fonction $\varsigma$ de $G$ vers $G \cup
+\{\bot\}$ (où $\bot$ signifiant « forfait » ou « non-défini », est un
+symbole n'appartenant pas à $G$) telle que $\varsigma(x)$ soit, pour
+chaque $x$, un voisin sortant de $x$ ou bien $\bot$.
+
+Une \textbf{partie} 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
+un $i$ pair, on dit qu'Alice perd et que Bob gagne, tandis que lorsque
+le dernier $x_i$ défini l'est pour un $i$ impair, on dit qu'Alice
+gagne et que Bob perd ; enfin, lorsque $x_i$ est défini pour tout
+entier naturel $i$ (ce qui ne peut pas se produire si $G$ est
+bien-fondé), on dit que la partie est nulle ou que les deux joueurs
+survivent sans gagner.  Lorsque de plus $\varsigma(x_i) = x_{i+1}$
+pour chaque $i$ pair pour lequel $x_i$ est défini (et en interprétant
+$\bot$ comme « non-défini »), on dit qu'Alice a joué la partie selon
+la stratégie $\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour
+chaque $i$ impair pour lequel $x_i$ est défini, on dit que Bob a joué
+la partie selon la stratégie $\tau$.
+
+Si $\varsigma$ et $\tau$ sont deux stratégies, on définit $\varsigma
+\ast \tau$ comme la partie jouée lorsque Alice joue $\varsigma$ et Bob
+joue $\tau$ : autrement dit, $x_0$ est la position initiale du jeu,
+et, si $x_i$ est défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ si
+$i$ est pair et $\tau(x_i)$ si $i$ est impair (en convenant que $\bot$
+signifie que le terme de la suite n'est pas défini et que la suite
+s'arrête).
+
+La stratégie $\varsigma$ est dite \textbf{gagnante pour Alice} lorsque
+Alice gagne toute partie où elle joue selon $\varsigma$.  La stratégie
+$\tau$ est dite \textbf{gagnante pour Bob} lorsque Bob gagne toute
+partie où il joue selon $\tau$.
+\end{defn}
+
 %
 %
 %