summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--notes-mitro206.tex89
1 files changed, 69 insertions, 20 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 72876d7..8cea295 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -822,7 +822,7 @@ notions sont distinctes, l'exemple le plus évident étant sans doute
celui de $\mathbb{N}$ dans lequel on fait pointer une arête de $i$
à $i+1$ pour chaque $i$.
-\begin{defn}
+\begin{defn}\label{definition-accessibility-downstream-wfpart}
Si $G$ est un graphe orienté on appelle \textbf{relation
d'accessibilité} la clôture réflexive-transitive de la relation
donnée par les arêtes de $G$ : autrement dit, on dit que $y$ est
@@ -878,6 +878,13 @@ intersection quelconque d'ensembles aval-inductifs est aval-inductive.
Leur nature, au moins dans un graphe bien-fondé, va être précisée dans
ce qui suit, et ceci justifiera le terme d'« aval-inductif ».
+Il sera utile pour la suite de remarquer que la partie bien-fondée
+de $G$ est à la fois aval-close et aval-inductive (car on peut
+construire une suite infinie $x_0, x_1, x_2\ldots$, avec $x_{i+1}$
+voisin sortant de $x_i$, commençant par un $x_0$ donné si et seulement
+si on peut le faire en commençant pour un certain voisin sortant $x_1$
+de ce $x_0$).
+
\begin{prop}[induction bien-fondée]\label{well-founded-induction}
Pour un graphe orienté $G$, les affirmations suivantes sont
équivalentes :
@@ -931,7 +938,7 @@ de montrer que $x$ a la propriété $P$, que cette propriété est déjà
connue de tous les voisins sortants de $x$.
\end{scho}
-\begin{prop}
+\begin{prop}\label{wfpart-is-smallest-inductive}
Si $G$ est un graphe orienté non supposé bien-fondé, la partie
bien-fondée de $G$ est la plus petite (pour l'inclusion) partie $P$
aval-inductive de $P$ (i.e., vérifiant la propriété « lorsque $x \in
@@ -956,9 +963,10 @@ aval-inductive de $G$.
Mais réciproquement, la partie bien-fondée de $G$ est elle-même
aval-inductive (car si $\downstr(y)$ est bien-fondé pour tout voisin
-sortant de $x$, il est clair que $\downstr(x)$ est aussi bien-fondé),
-donc un sommet qui appartient à toute partie aval-inductive de $G$
-est, en particulier, dans la partie bien-fondée de $G$.
+sortant de $x$, il est clair que $\downstr(x)$ est aussi bien-fondé,
+cf. \ref{trivial-remark-downstream}), donc un sommet qui appartient à
+toute partie aval-inductive de $G$ est, en particulier, dans la partie
+bien-fondée de $G$.
\end{proof}
\begin{thm}[définition par induction bien-fondée]\label{well-founded-definition}
@@ -1055,7 +1063,7 @@ on vient de le dire sur sa partie bien-fondée, et poser $\rho(x) =
Voici un autre exemple de définition par induction bien-fondée :
-\begin{defn}
+\begin{defn}\label{definition-grundy-function}
Soit $G$ un graphe orienté bien-fondé dans lequel chaque sommet n'a
qu'un nombre fini de voisins sortants. En utilisant le
théorème \ref{well-founded-definition}, on définit alors une fonction
@@ -1079,7 +1087,30 @@ de valeur de Grundy $0$ comme voisin sortant.
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.
+l'étude de la théorie des jeux impartiaux. On verra aussi comment la
+définir sans l'hypothèse que chaque sommet n'a qu'un nombre fini de
+voisins sortants (mais ce ne sera pas forcément un entier naturel).
+En attendant, peut se passer de cette hypothèse pour définir isolément
+l'ensemble des sommets de valeur de Grundy $0$ :
+
+\begin{defn}\label{definition-grundy-kernel}
+Soit $G$ un graphe orienté bien-fondé. En utilisant le
+théorème \ref{well-founded-definition}, on définit alors une partie $P
+\subseteq G$ telle que $x \in P$ ssi $\outnb(x) \cap P =
+\varnothing$ ; formellement, c'est-à-dire que pour $f\colon \outnb(x)
+\to \{0,1\}$ on définit $\Phi(x, f)$ comme valant $1$ si $f$ prend la
+valeur $0$ et $0$ si $f$ vaut constamment $1$, et qu'on appelle $f$ la
+fonction telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ dont l'existence
+et l'unicité sont garanties par le théorème, et enfin on pose $P = \{x
+\in G : f(x) = 0\}$.
+
+Les éléments de $P$ seront appelés les \textbf{P-sommets} (ou
+P-positions) de $G$, tandis que les éléments du complémentaire
+$G\setminus P$ seront appelés \textbf{N-sommets} (ou N-positions)
+de $G$ : ainsi, \emph{un P-sommet est un sommet dont tous les voisins
+ sortants sont des N-sommets, et un N-sommet est un sommet qui a au
+ moins un P-sommet pour voisin sortant}.
+\end{defn}
\subsection{Écrasement transitif}
@@ -1218,7 +1249,9 @@ 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.
+l'hypothèse que $G$ est terminant ; on attire l'attention sur le fait
+que cela signifie que $x_0$ appartient à la partie bien-fondée
+(cf. \ref{definition-accessibility-downstream-wfpart}) du graphe $G$.
\begin{defn}
Pour un jeu $G$ comme
@@ -1232,17 +1265,17 @@ 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$.
+un $i$ pair, on dit qu'Alice \textbf{perd} et que Bob \textbf{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 \textbf{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
@@ -1255,9 +1288,25 @@ 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$.
+partie où il joue selon $\tau$. On définit de même une stratégie
+survivante (c'est-à-dire, permettant d'assurer au moins le nul) pour
+Alice, resp. Bob.
\end{defn}
+\begin{thm}
+Soit $G$ un jeu impartial à information parfaite : exactement l'une
+des trois affirmations suivantes est vraie :
+\begin{itemize}
+\item Alice possède une stratégie gagnante,
+\item Bob possède une stratégie gagnante,
+\item Alice et Bob possèdent une stratégie survivante — ce cas ne
+ pouvant pas se produire si $G$ est terminant.
+\end{itemize}
+\end{thm}
+\begin{proof}
+\textcolor{red}{...}
+\end{proof}
+
%
%
%