summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-03-06 13:36:46 +0100
committerDavid A. Madore <david+git@madore.org>2017-03-06 13:36:46 +0100
commit549e3a809163635a3195629b69673a7c1c2c3699 (patch)
tree55808a153fe76433a85b604a28e13856907217e7
parentc1d360c35628e4c56c6d5934f019fc293e9265f3 (diff)
downloadmitro206-549e3a809163635a3195629b69673a7c1c2c3699.tar.gz
mitro206-549e3a809163635a3195629b69673a7c1c2c3699.tar.bz2
mitro206-549e3a809163635a3195629b69673a7c1c2c3699.zip
Some renumbering (change (i,i+1) to (i-1,i)) and a couple more small fixes.
-rw-r--r--notes-mitro206.tex76
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$).