diff options
| -rw-r--r-- | notes-mitro206.tex | 89 |
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} + % % % |