diff options
| -rw-r--r-- | notes-mitro206.tex | 341 |
1 files changed, 340 insertions, 1 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 9f9f8ca..43545a1 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1853,7 +1853,7 @@ d'après \ref{strategies-forall-exists-lemma}, (a) il existe un $x$ tel que $(x_0,\ldots,x_{i-1},x)$ ne soit pas gagnante pour Alice : choisissons-un tel $x$ et posons $\tau((x_0,\ldots,x_{i-1})) := x$ : toujours d'après \ref{strategies-forall-exists-lemma}, (b) quel que -soit $x' \in X$, la position $(x_0,\ldots,x_{i-1},x,y)$ n'est pas +soit $y \in X$, la position $(x_0,\ldots,x_{i-1},x,y)$ n'est pas gagnante pour Alice (et c'est de nouveau à Bob de jouer). Aux points où $\tau$ n'a pas été défini par ce qui vient d'être dit, on le définit de façon arbitraire. @@ -5217,6 +5217,345 @@ où Roxane commence (exactement analogue : Roxane choisit $(x_0,x_1) \subsection{Jeux de Gale-Stewart et détermination} +\exercice + +On considère dans cet exercice une variante des jeux de Gale-Stewart +où au lieu qu'un joueur « gagne » et l'autre « perde », il va leur +être attribué un gain réel comme dans les jeux à somme nulle. Plus +exactement, ce type de jeu est décrit comme suit. On fixe un ensemble +$X$ (non vide) et une fonction $u \colon X^{\mathbb{N}} \to +\mathbb{R}$ dite fonction de gain d'Alice (la fonction de gain de Bob +serait $-u$). Alice et Bob choisissent tour à tour un élément de $X$ +comme pour un jeu de Gale-Stewart, et jouent un nombre infini de +coups, « à la fin » desquels la suite $\underline{x} = +(x_0,x_1,x_2,\ldots)$ définit un élément $\underline{x} \in +X^{\mathbb{N}}$. Le gain d'Alice est alors $u(\underline{x})$ (le but +d'Alice est de le maximiser) et le gain de Bob est $-u(\underline{x})$ +(le but de Bob est de maximiser cette quantité, c'est-à-dire de +minimiser $u(\underline{x})$). + +\smallbreak + +(1) Expliquer pourquoi ce type de jeu peut être considéré comme une +généralisation des jeux de Gale-Stewart. + +\begin{corrige} +Si $G_X(A)$ où $A \subseteq X^{\mathbb{N}}$ est un jeu de Gale-Stewart +défini par un sous-ensemble $A$ de $X^{\mathbb{N}}$, on peut définir +une fonction $u \colon X^{\mathbb{N}} \to \mathbb{R}$ par +$u(\underline{x}) = 1$ si $x\in A$ et $u(\underline{x}) = -1$ +si $x\not\in A$, c'est-à-dire utiliser la valeur $+1$ pour un gain +d'Alice et $-1$ pour un gain de Bob. Les buts d'Alice et de Bob dans +le jeu défini par cette fonction sont alors exactement les mêmes que +dans le jeu $G_X(A)$. +\end{corrige} + +\smallbreak + +(2) On suppose désormais que $u \colon X^{\mathbb{N}} \to \mathbb{R}$ +est \emph{continue}, ce qui signifie par définition que pour tout +$\underline{x} \in X^{\mathbb{N}}$ et tout $\varepsilon > 0$ réel, il +existe $\ell$ tel que pour tout $y \in V_\ell(\underline{x})$ on ait +$|u(\underline{y}) - u(\underline{x})| < \varepsilon$. Montrer que +quel que soit $v \in\mathbb{R}$ l'ensemble des $\underline{x}$ tels +que $u(\underline{x}) > v$ est ouvert, et de même pour l'ensemble des +$\underline{x}$ tels que $u(\underline{x}) < v$. + +\begin{corrige} +Fixons un réel $v$. Montrons que l'ensemble $A_v$ des $\underline{x}$ +tels que $u(\underline{x}) > v$ est ouvert. Si $\underline{x}$ est +dans $A_v$, i.e., vérifie $u(\underline{x}) > v$, alors la définition +de la continuité appliquée à ce $\underline{x}$ et à $\varepsilon := +u(\underline{x}) - v$ assure qu'il existe $\ell$ tel que pour tout $y +\in V_\ell(\underline{x})$ on ait $|u(\underline{y}) - +u(\underline{x})| < \varepsilon$, et cette dernière inégalité implique +$u(\underline{y}) > u(\underline{x}) - \varepsilon = v$, donc on a +encore $u(\underline{y}) > v$, autrement dit $\underline{y} \in A_v$. +On a donc montré que pour tout $\underline{x}$ dans $A_v$ il existe +$\ell$ tel que tout $\underline{y}$ dans $V_\ell(\underline{x})$ soit +encore dans $A_v$, c'est exactement dire que $A_v$ est ouvert. Le cas +de l'enesmble $B_v$ des $\underline{x}$ tels que $u(\underline{x}) < +v$ est exactement analogue (on prendra $\varepsilon := v - +u(\underline{x})$). +\end{corrige} + +\smallbreak + +(3) (a) En déduire que pour tout $v$ réel, soit Alice possède une +stratégie lui garantissant un gain $\geq v$, soit Bob possède une +stratégie lui garantissant qu'Alice aura un gain $\leq v$ +(c'est-à-dire que lui, Bob, aura un gain $\geq -v$).\spaceout +(b) Montrer que les deux ne peuvent se produire simultanément que pour +\emph{au plus un} réel $v$. Un tel $v$ s'appelle la \textbf{valeur} +du jeu. + +\begin{corrige} +(a) Quel que soit $v$ réel, on vient de voir que l'ensemble $A_v$ des + $\underline{x}$ tels que $u(\underline{x}) > v$ est ouvert. La + détermination des jeux de Gale-Stewart ouverts + (théorème \ref{gale-stewart-theorem}) implique donc que soit Alice a + une stratégie lui garantissant de tomber dans $A_v$, c'est-à-dire un + gain $>v$, et \textit{a fortiori $\geq v$}, soit Bob a une stratégie + qui lui garantit de tomber dans le complémentaire de $A_v$, + c'est-à-dire garantissant qu'Alice aura un gain $\leq v$. + +(b) S'il existait deux réels $v' < v$ tels qu'Alice possède une + stratégie lui garantissant un gain $\geq v$ et que Bob possède une + stratégie lui garantissant qu'Alice aura un gain $\leq v'$, on + aurait une contradiction lorsque ces deux joueurs jouent leurs + stratégies respectives. +\end{corrige} + +\smallbreak + +(4) Indépendamment de tout ce qui précède, montrer que si $w$ est un +réel et $I_0$ et $I_1$ deux parties de $\mathbb{R}$ vérifiant (i) si +$v \in I_0$ et $v' < v$ alors $v' \in I_0$ et de même pour $I_1$, et +(ii) tout $v < w$ appartient à $I_0 \cup I_1$, alors en fait soit tout +$v<w$ appartient à $I_0$ soit tout $v<w$ appartient à $I_1$. (On +pourra considérer à quel $I_a$ appartient $w - \frac{1}{n}$ et faire +varier $n$.) + +\begin{corrige} +Pour chaque entier $n>0$, on a $w - \frac{1}{n} \in I_0 \cup I_1$ +d'après (ii), disons donc $w - \frac{1}{n} \in I_{a(n)}$ avec $a(n) +\in \{0,1\}$. Soit il existe une infinité de valeurs de $n$ telles +que $a(n)$ vaille $0$, soit $a(n)$ vaut constamment $1$ à partir d'un +certain point — et en particulier, il existe une infinité de valeurs +de $n$ telles que $a(n)$ vaille $1$. Bref, dans tous les cas, il +existe $b \in \{0,1\}$ tel que $a(n)$ prenne une infinité de fois la +valeur $b$, c'est-à-dire $w - \frac{1}{n} \in I_b$ une infinité +de $n$, autrement dit, pour des $n$ arbitrairement grands. Mais si +$v<w$, on peut trouver $n$ plus grand que $1/(w-v)$ tel que $w - +\frac{1}{n} \in I_b$ d'après ce qu'on vient de dire, or $v < +w-\frac{1}{n}$, et la propriété (i) montre alors que $v \in I_b$ : on +a bien montré que tout $v<w$ appartient à $I_b$. +\end{corrige} + +\smallbreak + +(5) On suppose désormais que $X = \{0,1\}$ (et toujours que $u$ est +continue). Le but de cette question est de montrer (pour $w \in +\mathbb{R}$) que si Alice possède pour tout $v < w$ une stratégie lui +garantissant un gain $\geq v$, alors en fait Alice possède une +stratégie lui garantissant un gain $\geq w$ : autrement dit, si Alice +peut se garantir n'importe quel gain $v < w$ alors elle peut se +garantir le gain $w$ lui-même. Pour abréger, on dira qu'une position +est « $v$-gagnante [pour Alice] » si Alice possède une stratégie lui +garantissant un gain $\geq v$ à partir de cette position (on notera +qu'une position $v$-gagnante est évidemment $v'$-gagnante pour +tout $v' < v$) ; et on dira qu'une position est « presque $w$-gagnante +[pour Alice] » si elle est $v$-gagnante pour tout $v < w$. + +On cherche donc à montrer, en s'inspirant de la démonstration du +théorème de Gale-Stewart, que si la position initiale (ou, en fait, +une position quelconque) est presque $w$-gagnante, alors elle est +$w$-gagnante.\spaceout (a) Montrer que si une position +$(z_0,\ldots,z_{i-1})$ où c'est à Alice de jouer est presque +$w$-gagnante, alors \emph{il existe} $x \in X$ (un coup d'Alice) tel +que $(z_0,\ldots,z_{i-1},x)$ soit presque $w$-gagnante (on pourra +utiliser (4)).\spaceout (b) Montrer que si une position +$(z_0,\ldots,z_{i-1})$ où c'est à Bob de jouer est presque +$w$-gagnante, alors \emph{pour tout} $x \in X$ (coup de Bob), la +position $(z_0,\ldots,z_{i-1},x)$ est presque $w$-gagnante.\spaceout +(c) Montrer que si $\underline{x} \in X^{\mathbb{N}}$ et +$u(\underline{x}) < w$ alors il existe $\ell$ tel que +$(x_0,\ldots,x_{\ell-1})$ ne soit pas presque $w$-gagnante.\spaceout +(d) En déduire (en construisant une stratégie d'Alice qui cherche à +rester dans des positions presque $w$-gagnantes) que si la position +initiale est presque $w$-gagnante, alors elle est $w$-gagnante. + +\begin{corrige} +(a) Si $\underline{z} := (z_0,\ldots,z_{i-1})$ est une position où + c'est à Alice de jouer qui est presque $w$-gagnante, elle est + $v$-gagnante pour tout $v < w$, autrement dit, pour chaque $v < w$, + Alice possède une stratégie qui lui garantit un gain $\geq v$. + D'après \ref{strategies-forall-exists-reformulation}, cela signifie + que pour chaque $v < w$, il existe un coup $x \in X$ d'Alice tel que + la position $\underline{z}x = (z_0,\ldots,z_{i-1},x)$ soit + $v$-gagnante. Pour $x \in \{0,1\}$, soit $I_x$ l'ensemble des $v$ + tels que la position $\underline{z}x = (z_0,\ldots,z_{i-1},x)$ soit + $v$-gagnante : la propriété (i) de la question (4) a été observée + dans la question, et la propriété (ii) est exactement la phrase + précédente. On déduit de la question (4) qu'il existe $x \in + \{0,1\}$ tel que la position $\underline{z}x = + (z_0,\ldots,z_{i-1},x)$ soit $v$-gagnante pour tout $v<w$, autrement + dit, soit presque $w$-gagnante, ce qu'on voulait montrer. + +(b) Si $\underline{z} := (z_0,\ldots,z_{i-1})$ est une position où + c'est à Bob de jouer qui est presque $w$-gagnante, elle est + $v$-gagnante pour tout $v < w$, autrement dit, pour chaque $v < w$, + Alice possède une stratégie qui lui garantit un gain $\geq v$. + D'après \ref{strategies-forall-exists-reformulation}, cela signifie + que pour chaque $v < w$, et pour chaque coup $x \in X$ de Bob, la + position $\underline{z}x = (z_0,\ldots,z_{i-1},x)$ est $v$-gagnante. + En permutant les quantificateurs : pour chaque coup $x \in X$ de Bob + et pour chaque $v < w$, la position $\underline{z}x$ est + $v$-gagnante. C'est bien dire que pour chaque coup $x\in X$ de Bob, + la position $\underline{z}x$ est presque $w$-gagnante, ce qu'on + voulait montrer. + +(c) Si $u(\underline{x}) < w$, et si $v$ est choisi tel que + $u(\underline{x}) < v < w$, alors par continuité de $u$ + (cf. question (2)), il existe $\ell$ tel que $u$ soit $<v$ sur + $V_\ell(\underline{x})$, autrement dit, aucune confrontation qui + prolonge $x_0,\ldots,x_{\ell-1}$ ne peut donner un gain $\geq v$ à + Alice, et en particulier, la position $x_0,\ldots,x_{\ell-1}$ n'est + pas $v$-gagnante, donc elle n'est pas presque $w$-gagnante. + +(d) Si $(x_0,\ldots,x_{i-1})$ est une position où c'est à Alice de + jouer et qui est presque $w$-gagnante, alors d'après (a) il existe + un $x$ tel que $(x_0,\ldots,x_{i-1},x)$ soit presque $w$-gagnante : + choisissons-un tel $x$ et posons $\tau((x_0,\ldots,x_{i-1})) := x$ : + d'après (b), quel que soit $y \in X$, la position + $(x_0,\ldots,x_{i-1},x,y)$ est presque $w$-gagnante (et c'est de + nouveau à elle de jouer). Aux points où $\tau$ n'a pas été défini + par ce qui vient d'être dit, on le définit de façon arbitraire. + +Si $\underline{x} = (x_0,x_1,x_2,\ldots)$ est une confrontation où +Alice joue selon $\tau$, on voit par récurrence sur $i$ que chacune +des positions $(x_0,\ldots,x_{i-1})$ est presque $w$-gagnante si la +position initiale l'est : pour $i=0$ c'est l'hypothèse faite (à savoir +que la position initiale est presque $w$-gagnante), pour les positions +où c'est à Alice de jouer, c'est la construction de $\tau$ qui assure +la récurrence (cf. (a) ci-dessus), et pour les positions où c'est à +Bob de jouer, c'est la question (b) qui assure la récurrence. Mais la +question (c) assure qu'on a alors $u(\underline{x}) \geq w$. On a +donc bien défini une stratégie qui garantit à Alice un gain $\geq w$. +\end{corrige} + +\smallbreak + +(6) (On suppose toujours que $X = \{0,1\}$ que $u$ est +continue.)\spaceout (a) Montrer que si $u$ est bornée, alors la valeur +du jeu existe, autrement dit, il existe $v$ tel qu'Alice possède une +stratégie lui garantissant un gain $\geq v$ et que Bob possède une +stratégie lui garantissant qu'Alice aura un gain $\leq v$. (On pourra +considérer la borne supérieure $w$ des $v$ pour lesquels Alice possède +une stratégie lui garantissant un gain $\geq v$, et appliquer la +question (5).)\spaceout (b) En considérant une fonction comme +$\arctan\circ u$ ou $\tanh\circ u$, montrer qu'on peut s'affranchir de +l'hypothèse « $u$ est bornée ».\spaceout (bonus) Déduire de ce qui +précède que toute fonction continue $u\colon \{0,1\}^{\mathbb{N}} \to +\mathbb{R}$ est bornée et atteint ses bornes (on pourra considérer un +jeu où les coups de Bob sont purement et simplement ignorés). + +\begin{corrige} +(a) Soit $I$ l'ensemble des $v$ pour lesquels Alice possède une + stratégie lui garantissant un gain $\geq v$ (i.e., pour lesquels la + position initiale est $v$-gagnante, dans la terminologie de (4)). + Si $v$ est strictement supérieur à un majorant de $u$ (qui existe + car $u$ est supposée bornée), il est évident qu'il est impossible + d'obtenir un gain $\geq v$, donc $v$ majore strictement $I$. Si $v$ + est strictement inférieur à un minorant de $u$, il est évident qu'il + est impossible de \emph{ne pas} obtenir un gain $\geq v$, donc + $v\in I$. Soit $w := \sup I$, qui existe puisque $I$ est non vide + et majoré. Si $v < w$, alors il existe $v' \in I$ tel que $v<v'<w$, + ce qui implique que $v \in I$ (puisqu'une stratégie garantissant un + gain $\geq v'$ garantit \textit{a fortiori} un gain $\geq v$). On + voit donc qu'Alice a une stratégie lui garantissant un gain $\geq v$ + pour tout $v < w$. La question (5) montre alors qu'Alice a une + stratégie lui garantissant un gain $\geq w$. \textit{A contrario}, + si $v > w$, alors Alice n'a pas de stratégie lui garantissant un + gain $\geq v$, donc Bob a une stratégie lui garantissant qu'Alice + aura un gain $\leq v$ (d'après la question (3)(a)). En appliquant + l'analogue pour Bob de la question (5) (qui s'en déduit en + échangeant les joueurs, c'est-à-dire en changeant $u$ en $-u$), Bob + a lui aussi une stratégie lui garantissant qu'Alice aura un + gain $\leq w$. On a bien prouvé que $w$ est la valeur du jeu. + +(b) Si $u$ n'est plus supposée bornée, soit $\tilde u = h\circ u$ où + $h\colon\mathbb{R}\to\mathbb{R}$ est une fonction continue bornée et + strictement croissante (par exemple $\arctan$ ou $\tanh$). Alors + $\tilde u$ est continue et bornée, donc la question précédente + montre que le jeu qu'elle définit a une valeur $\tilde w$. Cette + valeur ne peut pas être strictement supérieure à toute valeur de $h$ + (vu qu'Alice a une stratégie lui garantissant un gain $\geq\tilde + w$) ni strictement inférieure à toute valeur de $h$ (vu que Bob a + une stratégie lui garantissant qu'Alice aura un gain $\leq\tilde + w$). C'est donc (en utilisant les valeurs intermédiaires) que + $\tilde w = h(w)$ pour un certain $w$. Alors il est clair qu'une + stratégie garantissant à Alice un gain $\geq\tilde w$ dans le jeu + défini par $\tilde u$ lui garantit un gain $\geq w$ dans le jeu + défini par $u$, et de même pour Bob : ceci montre que $w$ est la + valeur du jeu défini par $u$. + +(bonus) Si $u$ est une fonction continue $\{0,1\}^{\mathbb{N}} \to + \mathbb{R}$, en considérant la fonction $\hat u\colon + \{0,1\}^{\mathbb{N}} \to \mathbb{R}$ qui ignore les coups joués par + Bob et calcule $u$ sur les coups joués par Alice (i.e., + formellement, $\hat u(\underline{x}) = u(\check{\underline{x})}$ où + $\check x_i = x_{2i}$), il est clair qu'Alice a une stratégie lui + garantissant un gain $\geq v$ si et seulement si $u$ prend une + valeur $\geq v$. Comme on vient de voir qu'il existe un plus grand + tel $v$ (la valeur du jeu), cela signifie bien que $u$ est bornée et + atteint ses bornes. +%% +%% Montrons que $u$ est majorée (la minoration est exactement analogue, +%% ou s'obtient en remplaçant $u$ par $-u$). Si ce n'est pas le cas, +%% pour chaque $n$ entier naturel, on peut choisir un +%% $\underline{z}_{(n)} \in X^{\mathbb{N}}$ tel que +%% $u(\underline{z}_{(n)}) \geq n$, et on va aboutir à une contradiction. +%% +%% Montrons que la suite $\underline{z}_{(n)}$ possède une valeur +%% d'adhérence, c'est-à-dire, qu'il existe $\underline{y}$ tel que +%% $\underline{z}_{(n)}$ passe infiniment souvent dans n'importe quel +%% voisinage fondamental de $\underline{y}$. Pour cela, considérons le +%% premier terme $z_{(n),0}$ de $\underline{z}_{(n)}$ : comme il +%% appartient à $X = \{0,1\}$, il doit valoir infiniment souvent $0$ ou +%% infiniment souvent $1$ : appelons $y_0$ une valeur qu'il prend pour +%% une infinité de $n$. Parmi l'ensemble des $n$ tels que $z_{(n),0} = +%% y_0$ (on vient de s'assurer qu'il est infini), le terme $z_{(n),1}$ +%% doit lui aussi valoir infiniment souvent $0$ ou infiniment +%% souvent $1$ : appelons $y_1$ une valeur qu'il prend pour une infinité +%% de $n$ (autrement dit, il existe une infinité de $n$ tels que +%% $z_{(n),0} = y_0$ \emph{et} $z_{(n),1} = y_1$). On procède ainsi par +%% récurrence sur $k$ : parmi l'ensemble des $n$ tels que $z_{(n),i} = +%% y_i$ pour tout $i<k$ (dont on s'est assuré par hypothèse de récurrence +%% qu'il est infini), le terme $z_{(n),k}$ doit lui aussi valoir +%% infiniment souvent $0$ ou infiniment souvent $1$ : on appelle $y_k$ +%% une valeur qu'il prend pour une infinité de $n$ (autrement dit, il +%% existe une infinité de $n$ tels que $z_{(n),i} = y_i$ pour tout $i\leq +%% k$). Ceci définit une suite $\underline{y} = (y_0,y_1,y_2,\ldots)$ +%% qui possède la propriété que pour tout $k$ il existe une infinité de +%% $n$ pour lesquels $z_{(n),i} = y_i$ pour tout $i < k$ : autrement dit, +%% $\underline{z}_{(n)}$ appartient infiniment souvent au voisinage +%% fondamental $V_k(\underline{y})$. +%% +%% Or la valeur $u(\underline{y})$ est un réel, disons $<N$ pour un +%% certain entier $N$ : par continuité de $u$ (cf. question (2)), il +%% existe $k$ tel que $u$ soit $<N$ sur $V_k(\underline{y})$. Notamment, +%% si $\underline{z}_{(n)} \in V_k(\underline{y})$ alors $n < N$. Ceci +%% contredit le fait qu'une infinité de $\underline{z}_{(n)}$ est censée +%% appartenir à $V_k(\underline{y})$. +%% +%% (De façon plus sophistiquée, on peut aussi écrire : l'espace +%% topologique $X = \{0,1\}$ est \emph{compact} car discret et fini, donc +%% $X^{\mathbb{N}}$ est également compact par le théorème de Tychonoff, +%% et l'image d'un compact par une fonction continue est un compact, donc +%% en particulier bornée dans $\mathbb{R}$.) +\end{corrige} + +\smallbreak + +(7) Soit $u \colon \{0,1\}^{\mathbb{N}} \to \mathbb{R}$ qui à +$(x_0,x_1,x_2,\ldots)$ associe $\sum_{i=0} x_i 2^{-i}$ (le nombre réel +dont la représentation binaire est donnée par $0$ virgule la suite +des $x_i$). Vérifier que $u$ est continue et calculer la valeur du +jeu qu'elle définit (quelle est la stratégie optimale pour Alice et +pour Bob ?). + +\begin{corrige} +(7) La fonction $u$ est continue car si $\varepsilon < 2^{-\ell-1}$ + alors la valeur $u(\underline{x})$ est définie à $\varepsilon$ près + par la donnée des $\ell$ premiers termes de la + suite $\underline{x}$. Il est évident qu'Alice a intérêt à ne jouer + que des $1$ (jouer autre chose ne ferait que diminuer son gain) et + Bob que des $0$. La valeur du jeu est donc $u(0,1,0,1,0,1,\ldots) = + \frac{1}{2}$. +\end{corrige} + + \subsection{Théorie de l'induction bien-fondée} \subsection{Introduction aux ordinaux} |