diff options
| -rw-r--r-- | notes-mitro206.tex | 76 |
1 files changed, 38 insertions, 38 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index aea1dd5..78064ae 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -2218,8 +2218,8 @@ joueurs). Une \textbf{partie} ou \defin{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 +position initiale et que pour chaque $i\geq 1$ pour lequel $x_i$ soit +défini, ce dernier soit un voisin sortant de $x_{i-1}$. Lorsque le dernier $x_i$ défini l'est pour un $i$ pair, on dit que le premier joueur \textbf{perd} et que le second \defin[gain]{gagne}, tandis que lorsque le dernier $x_i$ défini l'est pour un $i$ impair, on dit que @@ -2248,20 +2248,19 @@ trois : \begin{itemize} \item l'ensemble $D$ des (confrontations nulles dans le jeu combinatoire, 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), + que pour chaque $i \geq 1$ le sommet $x_i$ soit un voisin sortant + de $x_{i-1}$ (c'est-à-dire : $(x_{i-1},x_i)$ est une arête de $G$) + (bref, personne n'a enfreint la règle), \item l'ensemble $A$ des (confrontations gagnées par Alice dans le jeu combinatoire, 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), + qu'il existe $i \geq 1$ pour lequel $x_i$ n'est pas un voisin + sortant de $x_{i-1}$ et que le plus petit tel $i$ soit \emph{pair} + (i.e., Bob a enfreint la règle en premier), \item l'ensemble $B$ des (confrontations gagnées par Bob dans le jeu combinatoire, 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). + qu'il existe $i \geq 1$ pour lequel $x_i$ n'est pas un voisin + sortant de $x_{i-1}$ et que le plus petit tel $i$ soit \emph{impair} + (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 @@ -2282,12 +2281,12 @@ cf. \ref{definition-product-topology}). \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. +$i\geq 1$ pair tel que $x_i$ ne soit pas un voisin sortant +de $x_{i-1}$ et tel que $x_j$ soit un voisin sortant de $x_{j-1}$ pour +tout $1\leq 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$ inclus est contenu dans $A$. La même démonstration fonctionne +pour $B$ avec $i$ impair. \end{proof} \begin{thm}\label{determinacy-of-perfect-information-games} @@ -2374,25 +2373,25 @@ $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}$. -Lorsque dans une partie (confrontation) $x_0,x_1,x_2,\ldots$ de $G$ (à -partir d'une position initiale $x_0$) on a $\varsigma(x_i) = x_{i+1}$ -pour chaque $i$ pair pour lequel $x_i$ est défini, on dit que le +Lorsque dans une confrontation $x_0,x_1,x_2,\ldots$ de $G$ (à partir +d'une position initiale $x_0$) on a $x_i = \varsigma(x_{i-1})$ pour +chaque $i\geq 1$ impair pour lequel $x_i$ est défini, on dit que le premier joueur a joué la partie selon la stratégie positionnelle -$\varsigma$ ; tandis que si $\tau(x_i) = x_{i+1}$ pour chaque $i$ -impair pour lequel $x_i$ est défini, on dit que le second joueur a +$\varsigma$ ; tandis que si $x_i = \tau(x_{i-1})$ pour chaque $i\geq +1$ pair pour lequel $x_i$ est défini, on dit que le second joueur a joué la partie selon la stratégie $\tau$. Pour une stratégie -historique, il faut remplacer $\varsigma(x_i) = x_{i+1}$ et $\tau(x_i) -= x_{i+1}$ par $\varsigma(x_0,\ldots,x_i) = x_{i+1}$ et -$\tau(x_0,\ldots,x_i) = x_{i+1}$ respectivement. +historique, il faut remplacer $x_i = \varsigma(x_{i-1})$ et $x_i = +\tau(x_{i-1})$ par $x_i = \varsigma(x_0,\ldots,x_{i-1})$ et $x_i = +\tau(x_0,\ldots,x_{i-1})$ respectivement. La position initiale $x_0 \in G$ ayant été fixée, si $\varsigma$ et $\tau$ sont deux stratégies (positionnelles ou historiques), on définit $\varsigma \ast \tau$ comme la confrontation jouée lorsque le premier joueur joue selon $\varsigma$ et le second joue selon $\tau$ : -autrement dit, $x_0$ est la position initiale, et, si $x_i$ est -défini, $x_{i+1}$ est défini par $\varsigma(x_i)$ ou -$\varsigma(x_1,\ldots,x_i)$ si $i$ est pair et $\tau(x_i)$ ou -$\tau(x_1,\ldots,x_i)$ si $i$ est impair (si $x_{i+1}$ n'est pas +autrement dit, $x_0$ est la position initiale, et, si $x_{i-1}$ est +défini, $x_i$ est défini par $\varsigma(x_{i-1})$ ou +$\varsigma(x_1,\ldots,x_{i-1})$ si $i$ est impair et $\tau(x_{i-1})$ +ou $\tau(x_1,\ldots,x_{i-1})$ si $i$ est pair (si $x_i$ n'est pas défini, la suite s'arrête là). La stratégie (positionnelle ou historique) $\varsigma$ est dite @@ -2430,9 +2429,10 @@ fonctions partielles $\varsigma\colon G \dasharrow G$ telles que de $x$, et que \item si $\varsigma(x_0)$ est défini et si $(x_i)$ est une suite (\textit{a priori} finie ou infinie) partant de $x_0$, dans laquelle - $\varsigma(x_i) = x_{i+1}$ pour $i$ impair, et $x_{i+1}$ est voisin - sortant de $x_i$ pour tout $i$, alors la suite est de longueur finie - et le dernier $x_i$ défini l'est pour un $i$ impair + $x_i = \varsigma(x_{i-1})$ pour $i\geq 1$ impair, et $x_i$ est + voisin sortant de $x_{i-1}$ pour tout $i\geq 1$ [pair], alors la + suite est de longueur finie et le dernier $x_i$ défini l'est pour un + $i$ impair \end{itemize} (i.e., le premier joueur gagne n'importe quelle confrontation à partir d'une position initiale $x_0$ du domaine de définition de $\varsigma$ @@ -2693,9 +2693,9 @@ En particulier, si on utilise le théorème \ref{non-well-founded-definition} ci-dessous pour définir la \emph{plus petite} (pour l'inclusion) fonction partielle $f\colon G \dasharrow Z := \{\mathtt{P}, \mathtt{N}\}$ telle que $f(x)$ vaille -$\mathtt{P}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel -$f(y) = \mathtt{N}$, et que $f(x)$ vaille $\mathtt{N}$ ssi pour tout -voisin sortant $y$ de $x$ on a $f(y) = \mathtt{P}$, alors $f(x)$ vaut +$\mathtt{N}$ ssi $x$ a au moins un voisin sortant $y$ pour lequel +$f(y) = \mathtt{P}$, et que $f(x)$ vaille $\mathtt{P}$ ssi pour tout +voisin sortant $y$ de $x$ on a $f(y) = \mathtt{N}$, alors $f(x)$ vaut $\mathtt{P}$ ou bien $\mathtt{N}$ ou bien est indéfinie lorsque respectivement le premier joueur a une stratégie gagnante, le second joueur en a une, ou les deux ont une stratégie survivante. @@ -2720,9 +2720,9 @@ définie par $f(x) = \mathtt{P}$ lorsque $x \in P$ et $f(x) = vérifiant les propriétés qu'on a dites, i.e., la plus petite telle que $f(x) = \Phi(x, f|_{\outnb(x)})$ avec les notations du théorème \ref{non-well-founded-definition} et $\Phi(x, g)$ valant -$\mathtt{N}$ si $g(y)$ est défini et vaut $\mathtt{N}$ pour au moins +$\mathtt{N}$ si $g(y)$ est défini et vaut $\mathtt{P}$ pour au moins un $y \in \outnb(x)$ et $\mathtt{P}$ si $g(y)$ est défini et vaut -$\mathtt{P}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente +$\mathtt{N}$ pour tout $y \in \outnb(x)$ (comme $\Phi$ est cohérente en la seconde variable, on est bien dans le cas d'application du théorème \ref{non-well-founded-definition}, même si ici on a déjà démontré l'existence d'une plus petite $f$). |