Second exercise, on parity games.

1 files changed, 236 insertions, 0 deletions

diff --git a/controle-20260622.tex b/controle-20260622.tex
index cbd6973..e1f5345 100644
--- a/controle-20260622.tex
+++ b/controle-20260622.tex
@@ -315,6 +315,242 @@ $n_B > 0$.
 \end{corrige}
 
 
+%
+%
+%
+
+\exercise
+
+Le but de cet exercice est de montrer la détermination d'une certaine
+généralisation des jeux combinatoires étudiés en cours : les « jeux de
+parité ».
+
+Pour simplifier la terminologie, faisons d'abord la définition
+suivante : si $(u_0,u_1,u_2,\ldots) \in X^{\mathbb{N}}$ est une suite
+(infinie) à valeurs dans un ensemble $X$, on dira qu'une valeur $v \in
+X$ est \textbf{infiniment récurrente} pour la suite lorsque la suite
+prend cette valeur un nombre infini de fois, c'est-à-dire : $\forall
+n\in\mathbb{N}.\; \exists i\geq n.\; (u_i = v)$ ; ou, ce qui revient
+au même, $\{i\in\mathbb{N} : u_i=v\}$ est infini.  Il est clair que
+toute suite (infinie) à valeurs dans un ensemble fini possède au moins
+une valeur infiniment récurrente (on ne demande pas de justifier ce
+fait, qu'on pourra utiliser).
+
+Un \textbf{jeu de parité} est défini par la donnée : d'un graphe
+orienté $G$ (qui n'est pas supposé fini, ni bien-fondé) ; d'un sommet
+$x_0$ de $G$ appelé « position initiale » ; et d'une fonction $\pi
+\colon G \to \mathbb{N}$ \emph{bornée}\footnote{C'est-à-dire qu'il
+existe $N\in\mathbb{N}$ tel que $\pi$ ne prenne que des valeurs $\leq
+N$.}, appelée « priorité ».  La règle du jeu est la suivante : les
+joueurs Impair et Pair alternent, chacun choisissant un voisin sortant
+de la position actuelle (c'est-à-dire que Impair commence en
+choisissant $x_1$ voisin sortant de $x_0$, puis Pair choisit $x_2$
+voisin sortant de $x_1$, puis Impair choisit $x_3$ voisin sortant
+de $x_2$, et ainsi de suite).  Le gagnant est défini par les règles
+suivantes :
+\begin{itemize}
+\item si un joueur ne peut pas jouer, ce joueur perd (i.e., son
+  adversaire gagne) ;
+\item si la confrontation $\dblunderline{x} :=
+  (x_0,x_1,x_2,x_3,\ldots)$ dure un temps infini, alors (puisque $\pi$
+  était supposée bornée) il existe au moins une valeur qui soit
+  infiniment récurrente pour la suite $(\pi(x_0), \pi(x_1), \ldots)$
+  des priorités des sommets parcourus : le gagnant est alors donné par
+  la parité du maximum de ces valeurs (autrement dit, on pose $u_i =
+  \pi(x_i)$, on appelle $p := \max\{v : v\text{~infiniment récurrente
+    dans~}(u_i)\}$ et Impair gagne si $p$ est impair tandis que Pair
+  gagne si $p$ est pair).
+\end{itemize}
+Pour le dire de façon plus courte, le jeu se joue comme un jeu
+combinatoire normal, mais si la confrontation est infinie, au lieu de
+considérer que cela conduit à une issue nulle, le gagnant est donné
+par la parité de la plus grande priorité infiniment récurrente.  Il a
+donc toujours un gagnant et un perdant.
+
+{\footnotesize (Intuitivement, on peut imaginer le jeu ainsi : les
+  sommets $x$ avec $\pi(x)$ pair donnent un petit avantage au joueur
+  Pair, les sommets avec $\pi(x)$ impair donnent un petit avantage au
+  joueur Impair ; et cet avantage est d'autant plus important que
+  $\pi(x)$ est grand.  Si l'issue de la confrontation n'est pas
+  déterminée par le fait qu'un joueur soit dans l'impossibilité de
+  jouer, elle l'est par le fait qu'un de ces petits avantages se soit
+  infiniment accumulé.)\par}
+
+\medskip
+
+\textbf{(1)} À titre d'exemple, considérons le graphe $G =
+\{g_0,g_1,g_2\}$ avec une arête de chaque $g_i$ vers chaque autre
+$g_j$ (où $j\neq i$), la position initiale $g_0$, et les priorités
+$\pi(g_i) = i$.  Décrire une stratégie gagnante explicite pour Pair
+dans ce jeu.
+
+\begin{corrige}
+Pair peut jouer de la manière suivante : si la position actuelle est
+$g_0$ ou $g_1$, il joue vers $g_2$, sinon, il joue vers $g_0$.
+(Notons qu'il joue toujours vers un sommet dans $\{g_0,g_2\}$.)  Si la
+position $g_1$ est infiniment récurrente dans une confrontation, alors
+c'est forcément Impair qui a joué infiniment souvent vers cette
+position (puisque Pair joue toujours dans $\{g_0,g_2\}$), donc au coup
+suivant Pair joue vers $g_2$, et alors $g_2$ est infiniment récurrente
+aussi.  Donc la plus grande priorité infiniment récurrente ne peut pas
+être $1$, seule priorité impaire, donc elle est paire et Pair gagne.
+\end{corrige}
+
+\medskip
+
+On va maintenant montrer que les jeux de parité sont toujours
+déterminés, c'est-à-dire qu'un des joueurs a une stratégie
+gagnante\footnote{On autorise ici les stratégies \emph{historiques},
+c'est-à-dire que le coup choisi a le droit de dépendre de tous les
+coups antérieurs et pas seulement de la position actuelle.  (Il
+s'avère que les jeux de parité sont aussi déterminés pour les
+stratégies positionnelles, mais on ne s'intéressera pas à cette
+subtilité ici.)}.
+
+\medskip
+
+\textbf{(2)} Montrer que, pour $i,v\in\mathbb{N}$, l'ensemble
+\[
+S_{i,v} := \{\dblunderline{x}\in G^{\mathbb{N}} : \pi(x_i) = v\}
+\]
+est \emph{ouvert} (sous-entendu : pour la topologie produit de la
+topologie discrète) dans $G^{\mathbb{N}}$.
+
+\begin{corrige}
+Si $\dblunderline{x} \in S_{i,v}$ alors toute suite commençant par les
+mêmes valeurs $x_0,\ldots,x_i$ que $\dblunderline{x}$ est encore
+dans $S_{i,v}$, c'est-à-dire que $S_{i,v}$ contient le $(i+1)$-ième
+voisinage fondamental de $\dblunderline{x}$, donc en est un voisinage,
+et ceci montre que $S_{i,v}$ est ouvert.
+\end{corrige}
+
+\medskip
+
+\textbf{(3)} Pour $v\in\mathbb{N}$, montrer que l'ensemble $P_v$ des
+suites $\dblunderline{x}\in G^{\mathbb{N}}$ pour lesquelles la
+priorité $v$ est infiniment récurrente est :
+\[
+\bigcap_{n=0}^{+\infty} \bigcup_{i=n}^{+\infty} S_{i,v}
+\]
+— et que l'ensemble $M_v$ de celles pour lesquelles pour lesquelles
+$v$ est précisément la plus grande priorité infiniment récurrente
+est :
+\[
+P_v \setminus \bigcup_{w=v+1}^{+\infty} P_w
+\]
+
+\begin{corrige}
+Dire que $v$ est infiniment récurrente signifie :
+\[
+\forall n\in\mathbb{N}.\; \exists i\geq n.\; (\pi(x_i) = v)
+\]
+C'est exactement dire que $\dblunderline{x} \in
+\bigcap_{n=0}^{+\infty} \bigcup_{i=n}^{+\infty} S_{i,v}$ d'après la
+définition de $S_{i,v}$, et de l'intersection et de la réunion.
+
+Dire que $v$ est la plus grande priorité infiniment récurrente
+signifie exactement qu'elle l'est et qu'aucune priorité $w\geq v+1$ ne
+l'est, c'est-à-dire que $\dblunderline{x} \in P_v \setminus
+\bigcup_{w=v+1}^{+\infty} P_w$.
+\end{corrige}
+
+\medskip
+
+\textbf{(4)} Pour avoir toujours affaire à des confrontations
+infinies, lorsqu'un joueur ne peut plus jouer selon les règles, on
+conviendra qu'il joue n'importe quoi et a automatiquement perdu (i.e.,
+la suite des coups après est arbitraire et sans importance).  En
+reprenant un raisonnement du cours, rappeler pourquoi $G^{\mathbb{N}}$
+est la réunion disjointe $A \cup B \cup D$ où $A$, resp. $B$ sont des
+ouverts décrivant des confrontations gagnées par Impair, resp. Pair
+parce que l'autre joueur a violé en premier la règle de choisir un
+voisin sortant, et $D$ est un fermé décrivant les confrontations où
+chaque $x_{i+1}$ est un voisin sortant de $x_i$.
+
+\begin{corrige}
+Appelons $D$ l'ensemble des suites $\dblunderline{x} \in
+G^{\mathbb{N}}$ telles que chaque $x_{i+1}$ est un voisin sortant
+de $x_i$, et $A$ l'ensemble des suites telles qu'il existe $i$ tel que
+$x_{i+1}$ n'est pas un voisin sortant de $x_i$ et que le plus petit
+tel $i$ est impair (i.e., Pair a violé la règle en premier, donc
+Impair gagne), et $B$ l'ensemble des suites telles qu'il existe $i$
+tel que $x_{i+1}$ n'est pas un voisin sortant de $x_i$ et que le plus
+petit tel $i$ est pair (i.e., Impair a violé la règle en premier, donc
+Pair gagne).  Il est clair que $G^{\mathbb{N}} = A \cup B \cup D$,
+réunion disjointe.  Les ensembles $A,B$ sont ouverts comme on l'a vu
+en cours (rappel : si $i$ est le plus petit tel que $x_{i+1}$ n'est
+pas un voisin sortant de $x_i$, alors toute suite commençant par
+$x_0,\ldots,x_{i+1}$ a la même propriété) ; l'ensemble $D$ est donc
+fermé comme complémentaire de l'ouvert $A\cup B$.
+\end{corrige}
+
+\medskip
+
+\textbf{(5)} Dans les notations des questions (2)–(4), quelle est la
+partie de $G^{\mathbb{N}}$ décrivant exactement les confrontations
+gagnées par Impair ?
+
+\begin{corrige}
+Il s'agit de l'ensemble
+\[
+A \cup \left(D \cap \bigcup_{k=0}^{+\infty} M_{2k+1}\right)
+\]
+correspondant aux deux façons de gagner : soit Pair ne peut plus jouer
+et viole la règle (la confrontation est dans $A$), soit la règle est
+suivie jusqu'au bout et la plus grande priorité infiniment récurrente
+est impaire.
+
+(Pour les pinailleurs : il y a un problème de numérotation des suites,
+puisque Impair joue en premier avec le choix de $x_1$.  On peut
+résoudre cette petite difficulté en numérotant les suites à partir
+de $1$, ou en convenant que Pair joue en premier et perd immédiatement
+s'il ne choisit pas la position initiale $x_0$ imposée.  Ça ne change
+rien et ce n'est pas important ici.)
+\end{corrige}
+
+\medskip
+
+\textbf{(6)} En appliquant un théorème vu en cours, conclure que le
+jeu est déterminé.
+
+\begin{corrige}
+On rappelle que les boréliens sont la plus petite partie de
+$\mathscr{P}(G^{\mathbb{N}})$ contenant les ouverts et stable par
+complémentaire et réunions dénombrables (donc aussi intersections
+dénombrables).
+
+L'ensemble $S_{i,v}$ est borélien car ouvert.  L'ensemble
+$\bigcup_{i=n}^{+\infty} S_{i,v}$ est donc aussi borélien (en fait,
+ouvert).  L'ensemble $P_v := \bigcap_{n=0}^{+\infty}
+\bigcup_{i=n}^{+\infty} S_{i,v}$ est donc aussi borélien (intersection
+dénombrable de boréliens).  L'ensemble $\bigcup_{w=v+1}^{+\infty} P_w$
+est donc aussi borélien (réunion dénombrable de boréliens).
+L'ensemble $M_v := P_v \setminus \bigcup_{w=v+1}^{+\infty} P_w$,
+c'est-à-dire $P_v \cap (G^{\mathbb{N}} \setminus
+\bigcup_{w=v+1}^{+\infty} P_w)$ est donc aussi borélien (intersection
+d'un borélien et du complémentaire d'un borélien).  L'ensemble
+$\bigcup_{k=0}^{+\infty} M_{2k+1}$ est donc encore borélien.
+L'ensemble $D$ est fermé, donc borélien (complémentaire d'un ouvert),
+et l'ensemble $A$ est ouvert, donc borélien.  Donc finalement,
+l'ensemble $A \cup \left(D \cap \bigcup_{k=0}^{+\infty}
+M_{2k+1}\right)$ trouvé en (5) est borélien.
+
+Le théorème de détermination borélienne pour les jeux de Gale-Stewart,
+vu en cours, s'applique donc et permet de conclure que le jeu de
+parité considéré est déterminé.
+\end{corrige}
+
+\medskip
+
+{\footnotesize\textbf{À lire après l'épreuve, pour votre culture :}
+  Les jeux de parité, dans le cas où $G$ est fini, ont une grande
+  importance en informatique théorique, notamment en théorie de la
+  complexité parce que la question de décider quel joueur a une
+  stratégie gagnante est un problème qui est connu pour être à la fois
+  dans $\mathbf{NP}$ et $\mathbf{coNP}$ (et même « quasipolynomial »),
+  mais dont on ignore s'il est dans $\mathbf{P}$.\par}
+
+
 
 %
 %