diff options
| -rw-r--r-- | controle-20210412.tex | 268 | ||||
| -rw-r--r-- | controle-20220413.tex | 441 | ||||
| -rw-r--r-- | controle-20230417.tex | 793 | ||||
| -rw-r--r-- | controle-20240422.tex | 576 | ||||
| -rw-r--r-- | notes-mitro206.tex | 882 |
5 files changed, 2619 insertions, 341 deletions
diff --git a/controle-20210412.tex b/controle-20210412.tex index 110f494..8440d92 100644 --- a/controle-20210412.tex +++ b/controle-20210412.tex @@ -91,6 +91,9 @@ long parce que des rappels ont été faits et que la rédaction des questions cherche à éviter toute ambiguïté ; d'autre part, il ne sera pas nécessaire de tout traiter pour obtenir la totalité des points. +Les remarques en petits caractères ne font pas partie du sujet et +peuvent être ignorées. + \medbreak L'usage de tous les documents (notes de cours manuscrites ou @@ -106,7 +109,7 @@ Barème \emph{indicatif} : chaque question numérotée aura approximativement la même valeur (environ $1$ à $1.5$ points). \ifcorrige -Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse). +Ce corrigé comporte 10 pages (page de garde incluse). \else Cet énoncé comporte 5 pages (page de garde incluse). \fi @@ -146,7 +149,8 @@ On rappelle qu'une \emph{stratégie optimale} est une stratégie mixte qui réalise un gain espéré au moins égal à la valeur du jeu contre toute stratégie (pure donc mixte) de l'adversaire. -(0) Quelle est la valeur du jeu dans ce cas ? +\textbf{(0)} Quelle est la valeur du jeu dans ce cas ? (Ne pas faire de +calcul !) \begin{corrige} On a affaire à un jeu à somme nulle \emph{symétrique} (c'est-à-dire @@ -154,7 +158,7 @@ que sa matrice de gains est antisymétrique), donc la valeur du jeu est nulle. \end{corrige} -(1) À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} + +\textbf{(1)} À quelle condition sur $x$ la stratégie $\frac{1}{2}\mathrm{P} + \frac{1}{4}\mathrm{Q} + \frac{1}{4}\mathrm{R}$ (consistant à choisir P avec probabilité $\frac{1}{2}$, et chacun de Q et R avec probabilité $\frac{1}{4}$) est-elle optimale ? @@ -179,14 +183,14 @@ l'adversaire, il faut et il suffit donc que $\frac{x-1}{2} \geq 0$, c'est-à-dire $x\geq 1$. \end{corrige} -(2) À quelle condition sur $x$ l'expression $\frac{1}{x+2}\,\mathrm{P} + +\textbf{(2)} À quelle condition sur $x$ l'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + \frac{1}{x+2}\,\mathrm{S}$ (consistant à choisir R avec probabilité $\frac{x}{x+2}$, et chacun de P et S avec probabilité $\frac{1}{x+2}$) définit-elle une stratégie optimale ? \begin{corrige} L'expression $\frac{1}{x+2}\,\mathrm{P} + \frac{x}{x+2}\,\mathrm{R} + -\frac{1}{x+2}\,\mathrm{S}$ définit une stratégie mixte lorsque ses +\frac{1}{x+2}\,\mathrm{S}$ définit une stratégie (mixte) lorsque ses coefficients sont positifs de somme $1$ : le fait qu'ils soient de somme $1$ est toujours vrai, et ils sont tous positifs lorsque $x\geq 0$. @@ -211,7 +215,7 @@ l'adversaire, il faut et il suffit donc que $\frac{2(1-x)}{x+2} \geq 0$, c'est-à-dire $x\leq 1$, donc finalement $0\leq x\leq 1$. \end{corrige} -(3) Donner une stratégie optimale lorsque $x\leq 0$. +\textbf{(3)} Donner une stratégie optimale lorsque $x\leq 0$. \begin{corrige} Lorsque $x\leq 0$, la stratégie pure $\mathrm{S}$ est optimale @@ -219,7 +223,7 @@ puisqu'elle réalise un gain $\geq 0$ contre toute stratégie (pure donc mixte) de l'adversaire. \end{corrige} -(4) Dans chacun des cas $x=0$ et $x=1$, exhiber une infinité de +\textbf{(4)} Dans chacun des deux cas $x=0$ et $x=1$, exhiber une infinité de stratégies optimales distinctes. \begin{corrige} @@ -240,7 +244,7 @@ encore optimale, c'est-à-dire $\frac{2+t}{6}\,\mathrm{P} + \frac{1-t}{3}\,\mathrm{S}$ pour $t\in[0;1]$. \end{corrige} -(5) En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au +\textbf{(5)} En supposant que $x$ ne soit pas un réel fixé mais \emph{tiré au hasard} selon une loi uniforme entre $0$ et $1$ une fois que les joueurs ont joué (autrement dit, si un joueur choisit P et l'autre S, le joueur qui a choisi P reçoit un gain aléatoire uniforme entre @@ -280,11 +284,12 @@ $\varphi(\alpha) = \omega^\alpha$. On rappelle que $\varphi$ est \emph{strictement croissante} (c'est-à-dire que si $\alpha < \beta$ alors $\varphi(\alpha) < \varphi(\beta)$). -(1) Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie +\textbf{(1)} Rappeler pourquoi $\varphi$ est \emph{continue}, ce qui signifie par définition la chose suivante : si $\delta$ est un ordinal limite, alors $\lim_{\xi\to\delta} \varphi(\xi) = \varphi(\delta)$, où $\lim_{\xi\to\delta} \varphi(\xi)$ est une notation pour -$\sup\{\varphi(\xi) : \xi < \delta\}$. +$\sup\{\varphi(\xi) : \xi < \delta\}$ lorsque $\varphi$ est +croissante. \begin{corrige} La continuité de la fonction $\varphi\colon \alpha \mapsto @@ -295,10 +300,10 @@ l'exponentiation ordinale ($\omega ^ \delta = \lim_{\xi\to\delta} Pour éviter de partir dans des fausses directions, il est conseillé, jusqu'à la question (5) incluse, d'oublier la définition de $\varphi$ -et de retenir simplement que $\varphi$ est strictement croissante et +et de retenir seulement que $\varphi$ est strictement croissante et continue. -(2) Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour +\textbf{(2)} Rappeler pourquoi $\varphi(\alpha) \geq \alpha$ pour tout $\alpha$. \begin{corrige} @@ -321,7 +326,7 @@ contradiction.) On dira qu'un ordinal $\gamma$ est un \emph{point fixe} de $\varphi$ lorsque $\varphi(\gamma) = \gamma$. -(3) Soit dans cette question $\alpha$ un ordinal quelconque : +\textbf{(3)} Soit dans cette question $\alpha$ un ordinal quelconque : considérons la suite $(\gamma_n)$ (indicée par les entiers naturels $n$) définie par $\gamma_0 = \alpha$ et $\gamma_{n+1} = \varphi(\gamma_n)$. Montrer que $(\gamma_n)$ est croissante @@ -341,6 +346,30 @@ bout : montrons que $m\leq n$ implique $\gamma_m \leq \gamma_n$ par récurrence sur $n\geq m$ : pour $n=m$ c'est évident, et si on a $\gamma_m \leq \gamma_n$, alors $\gamma_m \leq \gamma_n \leq \varphi(\gamma_n) = \gamma_{n+1}$ ce qui conclut la récurrence.) + +Montrons maintenant $\varphi(\gamma_\omega) = \gamma_\omega$. Par +continuité de $\varphi$, on a $\varphi(\lim_{n\to\omega} \gamma_n) = +\lim_{n\to\omega} \varphi(\gamma_n)$ (pour être tout à fait complet +dans la démonstration de cette affirmation : $\gamma_\omega$ est par +définition le plus petit ordinal supérieur ou égal à tous les +$\gamma_n$ pour $n<\omega$, donc tout ordinal $\zeta<\gamma_\omega$ +est majoré par un $\gamma_n$ pour un certain $n<\omega$, et par +croissance de $\varphi$ on a alors $\varphi(\zeta)$ majoré par +$\varphi(\gamma_n)$, donc la borne supérieure des $\varphi(\gamma_n)$ +pour $n<\omega$ est aussi la borne supérieure des $\varphi(\zeta)$ +pour $\zeta<\gamma_\omega$ : or cette dernière borne supérieure est +$\varphi(\gamma_omega)$ par continuité de $\varphi$, ce qui montre +$\varphi(\gamma_\omega) = \lim_{n\to\omega} \varphi(\gamma_n)$), +c'est-à-dire $\varphi(\gamma_\omega) = \lim_{n\to\omega} \gamma_{1+n} += \gamma_\omega$, comme affirmé. + +Enfin, si $\delta$ est un point fixe de $\varphi$ et $\delta \geq +\alpha$, alors par récurrence sur $n$ on a $\delta \geq \gamma_n$ pour +tout $n<\omega$ (le cas $n=0$ est l'hypothèse, et $\delta \geq +\gamma_n$ implique $\varphi(\delta) \geq \varphi(\gamma_n)$ par +croissance de $\varphi$, c'est-à-dire $\delta \geq \gamma_{n+1}$), ce +qui donne $\delta \geq \gamma_\omega$ puisque $\gamma_\omega$ est la +borne supérieure des $\gamma_n$ pour $n<\omega$. \end{corrige} La question (3) implique notamment : \emph{pour tout ordinal $\alpha$ @@ -361,9 +390,11 @@ par : $\sup\{\varepsilon_\xi : \xi < \delta\}$). \end{itemize} -(4) Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement +Cette définition a bien un sens d'après ce qu'on vient de dire. + +\textbf{(4)} Montrer que $\iota \mapsto \varepsilon_\iota$ est strictement croissante. Montrer que $\varepsilon_\delta$ est un point fixe -de $\varphi$ aussi pour $\delta$ limite (c'est vrai pour les autres +de $\varphi$ aussi pour $\delta$ limite (c'est vrai dans les autres cas par la définition) : pour cela, on expliquera pourquoi $\varphi(\lim_{\xi\to\delta} \varepsilon_\xi) = \lim_{\xi\to\delta} \varphi(\varepsilon_\xi)$. @@ -425,7 +456,7 @@ $\varphi(\varepsilon_\delta) = \varphi(\lim_{\xi\to\delta} \lim_{\xi\to\delta} \varepsilon_\xi = \varepsilon_\delta$. \end{corrige} -(5) Montrer que tout ordinal $\gamma$ qui est un point fixe de +\textbf{(5)} Montrer que tout ordinal $\gamma$ qui est un point fixe de $\varphi$ est de la forme $\varepsilon_\alpha$ pour un certain ordinal $\alpha$ (on pourra montrer qu'il existe $\alpha$ tel que $\varepsilon_\alpha\geq\gamma$ puis considérer le plus petit @@ -451,6 +482,20 @@ ces $\varepsilon_\xi$, donc on a $\varepsilon_\alpha \leq \gamma$, et on a bien prouvé $\varepsilon_\alpha = \gamma$. \end{corrige} +{\footnotesize\textit{Remarque.} On a donc démontré que la fonction + $\varphi(1,\tiret) \colon \alpha \mapsto \varepsilon_\alpha$, qui + énumère les points fixes de $\varphi(0,\tiret) = \varphi \colon + \alpha \mapsto \omega^\alpha$ strictement croissante continue, est + elle-même strictement croissante et continue. On pourrait donc + continuer le procédé et appeler $\varphi(2,\tiret)$ la fonction + énumérant les points fixes de $\varphi(1,\tiret)$ (c'est-à-dire que + $\varphi(2,0)$ est le plus petit ordinal $\zeta$ tel que $\zeta = + \varepsilon_\zeta$ puis $\varphi(2,1)$ est le suivant, etc.), « et + ainsi de suite ». Ce procédé de construction d'ordinaux s'appelle + les « fonctions de Veblen » : on peut bien sûr continuer en + définissant $\varphi(1,0,0)$ comme le premier ordinal $\delta$ tel + que $\delta = \varphi(\delta,0)$ et au-delà.\par} + \medskip \underline{Deuxième partie.} @@ -465,11 +510,11 @@ résulte de la première partie de cet exercice). On a vu en cours que les ordinaux $<\varepsilon_0$ possèdent une représentation unique sous forme normale de Cantor itérée, et que celle-ci permet de les comparer, de les ajouter et de les multiplier. -On va se pencher ici sur \emph{deux} systèmes différents d'écriture -des ordinaux $<\varepsilon_1$, qu'on appellera « écriture 1 » et -« écriture 2 ». +On va s'intéresser ici aux ordinaux $<\varepsilon_1$, et leur donner +\emph{deux} systèmes différents d'écriture, qu'on appellera +« écriture 1 » et « écriture 2 ». -(6) Soit $\alpha < \varepsilon_1$ un ordinal différent +\textbf{(6)} Soit $\alpha < \varepsilon_1$ un ordinal différent de $\varepsilon_0$ : montrer que dans sa forme normale de Cantor $\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$, tous les exposants $\gamma_i$ sont $<\alpha$ (on pourra utiliser le fait, @@ -501,18 +546,20 @@ $\omega^{\omega^{\varepsilon_0}+1}\,2$ sont des écritures 1. En revanche, $\omega^{\varepsilon_0}$ n'en est pas une (elle ne vérifie pas la contrainte sur les exposants), ni $\varepsilon_0 + 1$ (ce n'est ni le symbole spécial $\varepsilon_0$ ni une forme normale de Cantor), -ni $(\varepsilon_0)^2$. +ni $\varepsilon_0\,2$, ni $(\varepsilon_0)^2$. -(7) Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ -possède bien une écriture 1 unique. Il est facile de voir que cette -écriture 1 permet algorithmiquement de manipuler les ordinaux +\textbf{(7)} Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ +possède bien une écriture 1 unique. Il est alors facile de voir que +cette écriture 1 permet algorithmiquement de manipuler les ordinaux $<\varepsilon_1$ : c'est-à-dire de les comparer, de les ajouter et de les multiplier (on ne demande pas de le justifier, les algorithmes étant essentiellement les mêmes que vus en cours pour les ordinaux -$<\varepsilon_0$) : il faut simplement bien se rappeler dans les -calculs intermédiaires le fait que $\varepsilon_0 = -\omega^{\varepsilon_0}$. Notamment calculer $\varepsilon_0\cdot 2$ et -$\varepsilon_0\cdot \omega$ en écriture 1. Expliquer comment calculer +$<\varepsilon_0$ sur la forme normale de Cantor : il faut simplement +bien se rappeler dans les calculs intermédiaires le fait que +$\varepsilon_0 = \omega^{\varepsilon_0}$ pour convertir +$\varepsilon_0$ en forme normale de Cantor dès qu'on en a besoin). +Calculer notamment $\varepsilon_0\cdot 2$ et $\varepsilon_0\cdot +\omega$ en écriture 1. Expliquer ensuite comment calculer $(\varepsilon_0)^\alpha$ en écriture 1 lorsque $\alpha$ est lui-même donné en écriture 1. Notamment, écrire $(\varepsilon_0)^{\omega 2}$ en écriture 1. @@ -521,15 +568,14 @@ en écriture 1. L'existence et l'unicité de l'écriture 1 résulte du (6) : donné un ordinal $<\varepsilon_1$, soit il est égal à $\varepsilon_0$, auquel cas il a une écriture 1 par définition (et celle-ci est bien unique -car on n'autorise pas de forme normale de Cantor comme -$\omega^{\varepsilon_0}$), soit on l'écrit sous forme normale de -Cantor avec des exposants strictement plus petits que lui, cette -représentation est unique, et on peut recommencer le procédé, ce qui -termine au bout d'un nombre fini d'étapes puisqu'on a affaire à des -ordinaux qui décroissent strictement. (Ou, si on préfère, on montre -par induction transfinie sur $\alpha < \varepsilon_1$ que $\alpha$ -possède une écriture 1 unique par le raisonnement qu'on vient de -dire.) +car on n'autorise pas de forme normale de Cantor pour lui), soit on +l'écrit sous forme normale de Cantor avec des exposants strictement +plus petits que lui, cette représentation est unique, et on peut +recommencer le procédé, ce qui termine au bout d'un nombre fini +d'étapes puisqu'on a affaire à des ordinaux qui décroissent +strictement. (Ou, si on préfère, on montre par induction transfinie +sur $\alpha < \varepsilon_1$ que $\alpha$ possède une écriture 1 +unique par le raisonnement qu'on vient de dire.) Calculons $\varepsilon_0\cdot 2$ en écriture 1 : il suffit de réécrire $\varepsilon_0$ comme $\omega^{\varepsilon_0}$, et alors @@ -537,7 +583,7 @@ $\omega^{\varepsilon_0}\cdot 2$ est une écriture 1 légitime (c'est bien une forme normale de Cantor dont les exposants sont tous écrits en écriture 1 et plus petit que l'ordinal donné). De même, calculons $\varepsilon_0\cdot \omega$ : pour cela, on écrit $\varepsilon_0\cdot -\omega = \omega^\varepsilon_0\cdot \omega = \omega^{\varepsilon_0+1} = +\omega = \omega^{\varepsilon_0}\cdot \omega = \omega^{\varepsilon_0+1} = \omega^{\omega^{\varepsilon_0}+1}$, ce qui est une écriture 1 légitime. @@ -552,12 +598,12 @@ laisse $\varepsilon_0$ comme résultat). Calculons $(\varepsilon_0)^{\omega 2}$ en écriture 1 : on vient de voir qu'il vaut $\omega^{\varepsilon_0\,\omega 2}$, or $\varepsilon_0\,\omega 2 = \omega^{\omega^{\varepsilon_0}+1}\,2$ comme -au-dessus, donc $(\varepsilon_0)^{\omega 2} = +ci-dessus, donc $(\varepsilon_0)^{\omega 2} = \omega^{\omega^{\omega^{\varepsilon_0}+1}\,2}$ (avec le parenthésage : $\omega^{((\omega^{((\omega^{\varepsilon_0})+1)})\cdot 2)}$). \end{corrige} -(8) Indépendamment des questions précédentes, rappeler pourquoi tout +\textbf{(8)} Indépendamment des questions précédentes, rappeler pourquoi tout ordinal $\alpha$ possède une écriture unique sous la forme $(\varepsilon_0)^{\gamma_s}\, \xi_s + \cdots + (\varepsilon_0)^{\gamma_1}\, \xi_1$ où $\gamma_s > \cdots > \gamma_1$ @@ -569,17 +615,18 @@ Il s'agit de l'écriture en base $\tau$ des ordinaux, dans le cas particulier de $\tau = \varepsilon_0$. \end{corrige} -(9) Indépendamment des questions précédentes, montrer que +\textbf{(9)} Indépendamment des questions précédentes, montrer que $\varepsilon_0 + \varepsilon_1 = \varepsilon_1$ (on rappelle que $\omega^\gamma + \omega^{\gamma'} = \omega^{\gamma'}$ lorsque $\gamma < \gamma'$). En déduire que $\varepsilon_0 \cdot \varepsilon_1 = \varepsilon_1$. En déduire que $(\varepsilon_0)^{\varepsilon_1} = \varepsilon_1$. Réciproquement, montrer que si $\delta$ est un -ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors on a aussi -$\omega^\delta = \delta$ (on pourra montrer $\delta \leq \omega^\delta -\leq \omega^{\varepsilon_0 \delta} \leq \delta$) et en déduire que -$\delta \geq \varepsilon_1$. En déduire que $\varepsilon_1$ est le -plus petit ordinal tel que $(\varepsilon_0)^{\delta} = \delta$. +ordinal tel que $(\varepsilon_0)^{\delta} = \delta$ alors il vérifie +aussi $\omega^\delta = \delta$ (on pourra montrer $\delta \leq +\omega^\delta \leq \omega^{\varepsilon_0 \delta} = \delta$) et en +déduire que $\delta \geq \varepsilon_1$. En déduire que +$\varepsilon_1$ est le plus petit ordinal tel que +$(\varepsilon_0)^{\delta} = \delta$. \begin{corrige} On a $\varepsilon_0 + \varepsilon_1 = \omega^{\varepsilon_0} + @@ -600,7 +647,7 @@ $\gamma\mapsto\omega^\gamma$, donc toutes ces inégalités sont des égalités et notamment $\omega^\delta = \delta$. Comme $\varepsilon_1$ est le deuxième point fixe de $\gamma \mapsto \omega^\gamma$, on en déduit que soit $\delta = \varepsilon_0$ soit $\delta \geq -\varepsilon_1$ : le premier est exclu car +\varepsilon_1$ : la première possibilité est exclue car $\varepsilon_0^{\varepsilon_0} > \varepsilon_0$ (par stricte croissance de l'exponentiation ordinale en l'exposant lorsque la base est $\geq 2$), et on a donc $\delta \geq \varepsilon_1$. On a bien @@ -621,10 +668,10 @@ ou bien $\varepsilon_0\,2 + \omega^\omega$ ou encore $(\varepsilon_0)^{\varepsilon_0}\,\omega^\omega\,3$ sont des écritures 2. En revanche, $\omega^{\varepsilon_0+1}$ n'en est pas une (les puissances de $\omega$ ne peuvent apparaître qu'au sein d'une -forme normale de Cantor itérée, donc ne faisant jamais intervenir -$\varepsilon_0$). +forme normale de Cantor itérée, dont l'exposant ne fait donc jamais +intervenir $\varepsilon_0$). -(10) Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ +\textbf{(10)} Expliquer brièvement pourquoi tout ordinal $<\varepsilon_1$ possède bien une écriture 2 unique. Esquisser un algorithme permettant de convertire l'écriture 2 d'un ordinal $<\varepsilon_1$ en écriture 1 (on utilisera la question (7)). @@ -666,19 +713,109 @@ types de têtes (= feuilles de l'arbre) : des têtes normales, et des \emph{œufs} (pouvant donner naissance à de nouvelles hydres). Quand Hercule coupe une tête $x$ normale, l'hydre se reproduit exactement comme on l'a vu en cours, c'est-à-dire qu'elle reproduit autant -d'exemplaires qu'elle le veut de tout le sous-arbre partant du nœud -$y$ parent de $x$ dans l'arbre (ces copies étant ajoutées comme filles -du nœud $z$ parent de $y$), à condition que $y$ ne soit pas la racine -(sinon, l'hydre ne joue pas). En revanche, si Hercule coupe un œuf, -cet œuf est remplacé par une nouvelle hydre, c'est-à-dire par un -sous-arbre, arbitrairement complexe, mais ne comportant pas lui-même -d'œuf. - -(11) En associant à toute position du jeu (= tout arbre enraciné dont +d'exemplaires qu'elle le veut, œufs compris, de tout le sous-arbre +partant du nœud $y$ parent de $x$ dans l'arbre (ces copies étant +ajoutées comme filles du nœud $z$ parent de $y$), à condition que $y$ +ne soit pas la racine (sinon, l'hydre ne joue pas). En revanche, si +Hercule coupe un œuf, cet œuf éclot est remplacé par une nouvelle +hydre, c'est-à-dire par un sous-arbre, arbitrairement complexe (choisi +par le joueur qui contrôle l'hydre), mais ne comportant lui-même pas +d'œuf, qui prend la place de la tête où était situé l'œuf. + +A titre d'exemple, sur le dessin suivant, où les œufs ont été +représentés par des ovales gris, selon la tête coupée par Hercule : +\begin{center} +\begin{tikzpicture}[baseline=0] +\draw[very thin] (-1.5,0) -- (1.5,0); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (0,1) {}; +\node (P2) at (0,2) {}; +\node (P3) at (-1,3) {}; +\node (P4) at (1,3) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw (P0) -- (P1); +\draw (P1) -- (P2); +\draw (P2) -- (P3); +\draw (P2) -- (P4); +\fill[fill=gray] (P3) to[out=0,in=270] ($(P3) + (0.3,0.3)$) to[out=90,in=0] ($(P3) + (0,1.0)$) to[out=180,in=90] ($(P3) + (-0.3,0.3)$) to[out=270,in=180] (P3); +\end{scope} +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node at (P3) {}; +\end{scope} +\end{tikzpicture} +peut devenir +\begin{tikzpicture}[baseline=0] +\draw[very thin] (-1.5,0) -- (1.5,0); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (0,1) {}; +\node (P2) at (0,2) {}; +\node (P3) at (-1,3) {}; +\node (P4) at (1,3) {}; +\node (P3a) at (-1.5,4) {}; +\node (P3b) at (-1,4) {}; +\node (P3c) at (-0.5,4) {}; +\node (P3aa) at (-1.75,4.5) {}; +\node (P3ab) at (-1.25,4.5) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw (P0) -- (P1); +\draw (P1) -- (P2); +\draw (P2) -- (P3); +\draw (P2) -- (P4); +\draw (P3) -- (P3a); +\draw (P3) -- (P3b); +\draw (P3) -- (P3c); +\draw (P3a) -- (P3aa); +\draw (P3a) -- (P3ab); +\end{scope} +\end{tikzpicture} +ou +\begin{tikzpicture}[baseline=0] +\draw[very thin] (-1.5,0) -- (1.5,0); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (0,1) {}; +\node (P2) at (0,2) {}; +\node (P3a) at (-1,3) {}; +\node (P2b) at (0.5,2) {}; +\node (P3b) at (-0.25,3) {}; +\node (P2c) at (1,2) {}; +\node (P3c) at (0.5,3) {}; +\node (P2d) at (1.5,2) {}; +\node (P3d) at (1.25,3) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw (P0) -- (P1); +\draw (P1) -- (P2); +\draw (P1) -- (P2b); +\draw (P1) -- (P2c); +\draw (P1) -- (P2d); +\draw (P2) -- (P3a); +\draw (P2b) -- (P3b); +\draw (P2c) -- (P3c); +\draw (P2d) -- (P3d); +\fill[fill=gray] (P3a) to[out=0,in=270] ($(P3a) + (0.3,0.3)$) to[out=90,in=0] ($(P3a) + (0,1.0)$) to[out=180,in=90] ($(P3a) + (-0.3,0.3)$) to[out=270,in=180] (P3a); +\fill[fill=gray] (P3b) to[out=0,in=270] ($(P3b) + (0.3,0.3)$) to[out=90,in=0] ($(P3b) + (0,1.0)$) to[out=180,in=90] ($(P3b) + (-0.3,0.3)$) to[out=270,in=180] (P3b); +\fill[fill=gray] (P3c) to[out=0,in=270] ($(P3c) + (0.3,0.3)$) to[out=90,in=0] ($(P3c) + (0,1.0)$) to[out=180,in=90] ($(P3c) + (-0.3,0.3)$) to[out=270,in=180] (P3c); +\fill[fill=gray] (P3d) to[out=0,in=270] ($(P3d) + (0.3,0.3)$) to[out=90,in=0] ($(P3d) + (0,1.0)$) to[out=180,in=90] ($(P3d) + (-0.3,0.3)$) to[out=270,in=180] (P3d); +\end{scope} +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node at (P3a) {}; +\node at (P3b) {}; +\node at (P3c) {}; +\node at (P3d) {}; +\end{scope} +\end{tikzpicture} +\end{center} + +\textbf{(11)} En associant à toute position du jeu (= tout arbre enraciné dont certaines feuilles sont qualifiées d'œufs) un ordinal $<\varepsilon_1$, montrer que Hercule gagne toujours, c'est-à-dire qu'il va toujours réduire l'hydre à sa seule racine en -temps fini. +temps fini (quoi qu'il fasse et quoi que fasse l'hydre). \begin{corrige} À toute hydre $T$ on associe un ordinal $o(T) <\varepsilon_1$ par @@ -700,14 +837,14 @@ ce n'est pas surprenant puisque de telles tiges offrent essentiellement les mêmes possibilités à l'hydre.) \end{corrige} -(12) Donner un exemple de position du jeu associé à l'ordinal +\textbf{(12)} Donner un exemple de position du jeu associé à l'ordinal $(\varepsilon_0)^{\varepsilon_0}$ par le système proposé en (11). \begin{corrige} L'hydre suivante (dans laquelle les œufs ont été représentés par des ovales gris) : \begin{center} -\begin{tikzpicture}[baseline=0] +\begin{tikzpicture} \draw[very thin] (-1.5,0) -- (1.5,0); \begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] \node (P0) at (0,0) {}; @@ -736,6 +873,13 @@ a la valeur $\omega^{\omega^{\varepsilon_0\,2}} = (\varepsilon_0)^{\varepsilon_0}$, comme demandé. \end{corrige} +{\footnotesize\textit{Remarque.} Pour rendre ce jeu plus intéressant, + il faudrait sans doute ajouter une règle selon laquelle Hercule ne + peut couper un œuf que s'il ne reste aucune tête non-œuf à couper, + sinon il est assez clair qu'il a intérêt à commencer par éliminer + tous les œufs. Mais cette contrainte, puisqu'elle ne concerne + qu'Hercule n'a aucune influence sur ce qu'on vient de prouver.\par} + % % diff --git a/controle-20220413.tex b/controle-20220413.tex new file mode 100644 index 0000000..5c2448d --- /dev/null +++ b/controle-20220413.tex @@ -0,0 +1,441 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{matrix,calc} +\usepackage{hyperref} +% +%\externaldocument{notes-mitro206}[notes-mitro206.pdf] +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\newcommand{\outnb}{\operatorname{outnb}} +\newcommand{\downstr}{\operatorname{downstr}} +\newcommand{\precs}{\operatorname{precs}} +\newcommand{\mex}{\operatorname{mex}} +\newcommand{\id}{\operatorname{id}} +\newcommand{\limp}{\Longrightarrow} +\newcommand{\gr}{\operatorname{gr}} +\newcommand{\rk}{\operatorname{rk}} +\newcommand{\fuzzy}{\mathrel{\|}} +% +\DeclareUnicodeCharacter{00A0}{~} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% +\begin{document} +\ifcorrige +\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} +\else +\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} +\fi +\author{} +\date{13 avril 2022} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +La longueur du sujet ne doit pas effrayer : l'énoncé est long parce +que des rappels ont été faits et que la rédaction des questions +cherche à éviter toute ambiguïté. Les réponses attendues sont +généralement beaucoup plus courtes que les questions elles-mêmes +(notamment dans le dernier exercice). + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 2h + +Barème \emph{indicatif} : $8+6+6$. + +\ifcorrige +Ce corrigé comporte 10 pages (page de garde incluse). +\else +Cet énoncé comporte 6 pages (page de garde incluse). +\fi + +\vfill +{\noindent\tiny +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +Le but de cet exercice est de tenter une classification des jeux en +forme normale, à deux joueurs, \emph{symétriques} (c'est-à-dire que +les deux joueurs ont les mêmes options et les mêmes gains sous l'effet +de la permutation qui les échange) et avec deux options. + +On considère donc le jeu dont la matrice de gains est la suivante, où +$u,v,x,y$ sont des réels sur lesquels on va discuter (les options sont +étiquetées $C$ et $D$ ; le gain d'Alice est listé en premier, celui de +Bob en second) : + +\begin{center} +\begin{tabular}{r|c|c|} +$\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline +$C$&$u$, $u$&$v$, $x$\\\hline +$D$&$x$, $v$&$y$, $y$\\\hline +\end{tabular} +\end{center} + +On se limitera à l'étude du cas où $u>v$, ce qu'on supposera +désormais. + +(1) Expliquer brièvement pourquoi il ne change rien à l'analyse du jeu +(p.ex., au calcul des équilibres de Nash) de remplacer tous les gains +$t$ d'un joueur donné par $at+b$ où $a>0$ et $b$ est quelconque. En +déduire qu'on peut supposer, dans le jeu ci-dessus, que $u=1$ et +$v=0$, ce qu'on fera désormais : + +\begin{center} +\begin{tabular}{r|c|c|} +$\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline +$C$&$1$, $1$&$0$, $x$\\\hline +$D$&$x$, $0$&$y$, $y$\\\hline +\end{tabular} +\end{center} + +(2) À quelle condition le profil $(C,C)$ (c'est-à-dire : Alice +joue $C$ et Bob joue $C$) est-il un équilibre de Nash ? À quelle +condition $(D,D)$ est-il un équilibre de Nash ? À quelle condition +$(C,D)$ est-il un équilibre de Nash ? Qu'en est-il de $(D,C)$ ? (À +chaque fois, on demande des conditions sous forme d'inégalités portant +sur $x$ et $y$.) + +On suppose dans la suite (pour écarter des cas limites pénibles) que +$x$ n'est pas exactement égal à $1$ et que $y$ n'est pas exactement +égal à $0$. + +(3) Expliquer pourquoi il n'y a pas d'équilibre de Nash dans lequel un +joueur joue une stratégie pure (i.e., soit $C$ soit $D$) et l'autre +une stratégie strictement mixte (i.e., $pC + (1-p)D$ avec $0<p<1$). + +(4) Analyser la possibilité que $(pC + (1-p)D, \; qC + (1-q)D)$, où +$0<p<1$ et $0<q<1$ soit un équilibre de Nash : que doivent valoir +$p$ et $q$ si c'est le cas ? et à quelle condition nécessaire et +suffisante obtient-on effectivement un équilibre de Nash de cette +forme ? (On pourra tracer un graphique, par ailleurs demandé à la +question suivante, pour visualiser le signe de $1-x+y$.) + +(5) Dans le plan de coordonnées $(x,y)$, représenter graphiquement les +domaines des paramètres dans lesquels existent les différents +équilibres de Nash trouvés dans l'analyse. (On rappelle qu'il doit +toujours y en avoir au moins un, ce qui peut permettre de détecter +d'éventuelles erreurs.) Dans quelle partie du diagramme se situent le +dilemme du prisonnier et le dilemme du trouillard respectivement ? + +(La question (6) peut être traitée indépendamment des questions +précédentes.) + +(6) On introduit le nouveau concept suivant : pour un jeu symétrique, +une \textbf{stratégie rationnelle commun} est une stratégie mixte, +donc ici, $rC + (1-r)D$ pour $0\leq 1\leq r$, qui quand elle est jouée +par l'ensemble des joueurs, conduit au gain (forcément le même pour +tous) le plus élevé sous cette contrainte\footnote{Autrement dit, une + stratégie rationnelle commune est une stratégie mixte $s$ telle que + si tous les joueurs jouent $s$, leur espérance de gain commune sera + supérieure ou égale à celle s'ils jouent tous $s'$, quelle que + soit $s'$.}. Dans le jeu considéré ici, calculer l'espérance de +gain commune des joueurs s'ils jouent tous $rC + (1-r)D$ , et en +déduire pour quelle(s) valeur(s) de $r$ cette fonction est maximale, +en discutant éventuellement selon les valeurs de $x,y$. Tracer un +nouveau graphique pour représenter, dans le plan de coordonnés +$(x,y)$, les domaines de paramètres dans lequels existent les +différentes stratégies rationnelles communes (on distinguera : $C$, +$D$ et $rC + (1-r)D$ avec $0<r<1$). + + +% +% +% + +\exercice + +On s'intéresse ici à la variation suivante du jeu de nim (fini) : +après avoir retiré des bâtonnets d'une ligne, un joueur peut en outre, +s'il le souhaite, \emph{couper} la ligne en deux, ce qui crée deux +lignes au lieu d'une, en répartissant comme il le veut les bâtonnets +de la ligne initiale (après en avoir retiré au moins un) entre ces +deux lignes. + +De façon plus formelle, l'état du jeu est donné par la liste des +nombres $n_1,\ldots,n_r \in \mathbb{N}$ de bâtonnets des différentes +lignes du jeu (on peut ignorer ceux pour lesquels $n_i=0$) ; et un +coup du jeu consiste à choisir un $1\leq i\leq r$ et à remplacer $n_i$ +dans la liste soit par un entier neturels $n' < n_i$, soit par +\emph{deux} entiers naturels $n',n''$ tels que $n' + n'' < n_i$ (on +peut d'ailleurs ne considérer que ce deuxième type de coup puisque +prendre $n''=0$ revient à n'avoir que $n'$). Comme d'habitude, le +joueur qui ne peut pas jouer a perdu (i.e., le gagnant est celui qui +retire le dernier bâtonnet) ; et la disposition des lignes ou des +bâtonnets au sein d'une ligne n'a pas d'importance, seul compte leur +nombre (et tout est fini). + +(1) Expliquer pourquoi la valeur de Grundy de la position +$(n_1,\ldots,n_r)$ du jeu est la somme de nim $f(n_1) \oplus \cdots +\oplus f(n_r)$ des valeurs de Grundy $f(n_i)$ des positions ayant une +seule ligne avec $n_i$ bâtonnets (où $f$ est une fonction qui reste à +calculer, avec évidemment $f(0)=0$). + +(2) Expliquer pourquoi $f(n) = \mex\{f(n') \oplus f(n'') \; | \; +n'+n'' < n\}$ est le plus petit entier naturel qui n'est pas de la +forme $f(n') \oplus f(n'')$ où $n',n''$ parcourent les couples +d'entiers naturels tels que $n'+n'' < n$ (et comme d'habitude, $\mex +S$ est le plus petit entier naturel qui n'est pas dans $S$). + +(3) Indépendamment de ce qui précède, expliquer pourquoi $k \oplus +\ell \leq k + \ell$ quels que soient $k,\ell \in \mathbb{N}$. + +(4) Montrer que $f(n) = n$ pour tout $n$. + +(5) Que conclure quant à la stratégie gagnante à la variante proposée +ici du jeu de nim par rapport au jeu de nim standard ? + + +% +% +% + +\exercice + +On s'intéresse dans cet exercice au jeu de \emph{Hackenbush bicolore + en arbre}, défini comme suit. L'état du jeu est représenté par un +arbre (fini, enraciné\footnote{C'est-à-dire que la racine fait partie + de la donnée de l'arbre, ce qui est la convention la plus + courante.}) dont chaque arête est soit coloriée \emph{bleue} soit +\emph{rouge}, mais jamais les deux à la fois (il y a exactement deux +types d'arêtes). Deux joueurs, Blaise et Roxane, alternent et chacun +à son tour choisit une arête de l'arbre, bleue pour Blaise ou rouge +pour Roxane, et l'efface, ce qui fait automatiquement disparaître du +même coup tout le sous-arbre qui descendait de cette arête (voir +figure). L'arête choisie doit avoir la couleur associée au joueur, +c'est-à-dire bleue pour Blaise ou rouge pour Roxane, mais toutes les +arêtes qui en descendent sont effacées quelle que soit leur couleur. +Le jeu se termine lorsque plus aucun coup n'est possible (c'est-à-dire +que le joueur qui doit jouer n'a plus d'arête de sa couleur), auquel +cas, selon la convention habituelle, le joueur qui ne peut plus jouer +a perdu. + +À titre d'exemple, ceci illustre un coup possible de Roxane +(effacement d'une arête rouge et de tout le sous-arbre qui en +descend) : +\begin{center} +\begin{tikzpicture}[baseline=0] +\fill [gray!50!white] (-3.0,0) rectangle (2.0,-0.2); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (-0.75,1) {}; +\node (P2) at (-2.25,2) {}; +\node (P3) at (-2.75,3) {}; +\node (P4) at (-1.75,3) {}; +\node (P5) at (0.75,2) {}; +\node (P6) at (0.00,3) {}; +\node (P7) at (0.75,3) {}; +\node (P8) at (1.50,3) {}; +\node (P9) at (1.75,1) {}; +\node (P10) at (1.75,2) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw[blue] (P0) -- (P1); +\draw[red] (P1) -- (P2); +\draw[red] (P1) -- (P5); +\draw[blue] (P2) -- (P3); +\draw[blue] (P2) -- (P4); +\draw[blue] (P5) -- (P6); +\draw[blue] (P5) -- (P7); +\draw[red] (P5) -- (P8); +\draw[red] (P0) -- (P9); +\draw[blue] (P9) -- (P10); +\end{scope} +\begin{scope}[line width=3pt,gray!50!black] +\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,-0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,0.2)$); +\draw ($0.5*(P1) + 0.5*(P5) + (-0.2,0.2)$) -- ($0.5*(P1) + 0.5*(P5) + (0.2,-0.2)$); +\end{scope} +\end{tikzpicture} +~devient~ +\begin{tikzpicture}[baseline=0] +\fill [gray!50!white] (-3.0,0) rectangle (2.0,-0.2); +\begin{scope}[every node/.style={circle,fill,inner sep=0.5mm}] +\node (P0) at (0,0) {}; +\node (P1) at (-0.75,1) {}; +\node (P2) at (-2.25,2) {}; +\node (P3) at (-2.75,3) {}; +\node (P4) at (-1.75,3) {}; +\node (P9) at (1.75,1) {}; +\node (P10) at (1.75,2) {}; +\end{scope} +\begin{scope}[line width=1.5pt] +\draw[blue] (P0) -- (P1); +\draw[red] (P1) -- (P2); +\draw[blue] (P2) -- (P3); +\draw[blue] (P2) -- (P4); +\draw[red] (P0) -- (P9); +\draw[blue] (P9) -- (P10); +\end{scope} +\end{tikzpicture} +\end{center} + +(1) Expliquer brièvement pourquoi une position de ce jeu peut être +considérée comme une somme disjonctive de différents jeux du même +type. Plus exactement, soit $T$ un arbre bicolore de racine $x$, +soient $y_1,\ldots,y_r$ les fils de $x$, soient $T_1,\ldots,T_r$ les +sous-arbres ayant pour racines $y_1,\ldots,y_r$ et soient +$T'_1,\ldots,T'_r$ les arbres de racine $x$ où $T'_i$ est formé de $x$ +et de $T_i$ (y comprise l'arête entre $x$ et $y_i$) : expliquer +brièvement pourquoi la position représentée par l'arbre $T$ est la +somme disjonctive de celles représentées par $T'_1,\ldots,T'_r$. + +\smallskip + +Si $T$ est un arbre de Hackenbush bicolore, notons $1{:}T$ l'arbre +$T'$ correspondant à placer $T$ au sommet d'une unique arête bleue +reliée à la racine (autrement dit, $T'$ est formé en ajoutant un +nouveau sommet, qui sera la racine, et en ajoutant une arête bleue +entre cette nouvelle racine et l'ancienne racine de $T$). + +On \underline{admet} les résultats suivants : à tout arbre de +Hackenbush bicolore $T$ on peut associer un nombre réel $v(T)$ (sa +\emph{valeur}), de façon que : +\begin{itemize} +\item[(a)] Si $T$ et $T'_1, \ldots, T'_r$ sont comme dans l'énoncé de + la question (1) alors $v(T) = v(T'_1) + \cdots + v(T'_r)$. +\item[(b)] On a $v(-T) = -v(T)$ où $-T$ est l'arbre obtenu en échangeant + les couleurs rouge et bleue dans $T$. +\item[(c)] On a $v(1{:}T) = \varphi_+(v(T))$ où $\varphi_+$ est la + fonction définie par\footnote{Les cas dans la définition de + $\varphi_+$ se chevauchent un peu, et c'est normal : les + définitions sont compatibles aux chevauchements.} +\[ +\varphi_+(v) = \left\{ +\begin{array}{ll} +v+1&\hbox{~si $v\geq 0$}\\ +2^{-n}\,(v+n+1)&\hbox{~si $-n\leq v \leq -n+1$ où $n\in\mathbb{N}$}\\ +\end{array} +\right. +\] +\item[(d)] On a $v(T) \geq 0$ si et seulement si Blaise possède une + stratégie gagnante en jouant en second à partir de la position $T$, + et $v(T) \leq 0$ lorsque Roxane en possède une. +\end{itemize} + +(2) Utiliser ces règles admises pour calculer la valeur de l'arbre +tracé à gauche dans la figure ci-dessus (avant effacement). Pour +éviter de se tromper, on recommande de reproduire l'arbre et +d'indiquer à côté de chaque sommet la valeur du sous-arbre qui en +descend, et à côté de chaque arête la valeur du sous-arbre avec +l'arête en question. En déduire qui a une stratégie gagnante dans +cette position selon le joueur qui commence. + +\smallbreak + +\centerline{* * *} + +Indépendamment de ce qui précède, on va considérer une opération sur +les jeux partisans : si $G$ est un jeu combinatoire partisan, vu comme +un graphe orienté (bien-fondé), on définit un jeu noté $1{:}G$ en +ajoutant une unique position $0$ à $G$ comme on va l'expliquer. Pour +chaque position $z$ de $G$ il y a une position notée $1{:}z$ de +$1{:}G$, et il y a une unique autre position, notée $0$, +dans $1{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête +$1{:}z\, \to \, 1{:}z'$ dans $1{:}G$, coloriée de la même manière que +dans $G$, et il y a de plus une arête $1{:}z\, \to 0$ dans $1{:}G$ +pour chaque $z$, coloriée en bleu (en revanche, $0$ est un puits, +c'est-à-dire qu'aucune arête n'en part) ; la position initiale de +$1{:}G$ est $1{:}z_0$ où $z_0$ est celle de $G$. De façon plus +informelle, pour jouer au jeu $1{:}G$, chaque joueur peut faire un +coup normal ($1{:}z\, \to \, 1{:}z'$) de $G$, mais par ailleurs, +Blaise peut à tout moment appliquer un coup « destruction totale » +$1{:}z\, \to 0$ qui fait terminer immédiatement le jeu (et il a alors +gagné\footnote{Ce jeu considéré tout seul n'est donc pas très amusant + puisque Blaise a toujours la possibilité de gagner + instantanément.}). + +(3) Montrer que si $G \geq H$ on a $1{:}G \geq 1{:}H$. (On rappelle +que $G \geq H$ signifie : « Blaise a une stratégie gagnante s'il joue +en second au jeu $G - H$ défini comme la somme disjonctive du jeu $G$ +et du jeu $-H$ obtenu en échangeant les deux joueurs au jeu $H$ ». +Pour cela, on expliquera comment Blaise peut gagner à $(1{:}G) - +(1{:}H)$ en jouant en second, en supposant qu'il sait gagner à $G - H$ +en jouant en second.) En déduire que si $G \doteq H$ alors $1{:}G +\doteq 1{:}H$. + +{\footnotesize\textit{Remarque.} Ceci justifie partiellement + l'affirmation (c) des règles admises ci-dessus en ce sens que cela + explique que $v(1{:}G)$ ne dépende que de $v(G)$ et pas du détail + de $G$, et aussi que la fonction $\varphi_+$ est croissante.\par} + + + + + +% +% +% +\end{document} diff --git a/controle-20230417.tex b/controle-20230417.tex new file mode 100644 index 0000000..fce95a1 --- /dev/null +++ b/controle-20230417.tex @@ -0,0 +1,793 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{matrix,calc} +\usepackage{hyperref} +% +%\externaldocument{notes-mitro206}[notes-mitro206.pdf] +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\newcommand{\outnb}{\operatorname{outnb}} +\newcommand{\downstr}{\operatorname{downstr}} +\newcommand{\precs}{\operatorname{precs}} +\newcommand{\mex}{\operatorname{mex}} +\newcommand{\id}{\operatorname{id}} +\newcommand{\limp}{\Longrightarrow} +\newcommand{\gr}{\operatorname{gr}} +\newcommand{\rk}{\operatorname{rk}} +\newcommand{\dur}{\operatorname{dur}} +\newcommand{\fuzzy}{\mathrel{\|}} +% +\newcommand{\dblunderline}[1]{\underline{\underline{#1}}} +% +\DeclareUnicodeCharacter{00A0}{~} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% +\begin{document} +\ifcorrige +\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} +\else +\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} +\fi +\author{} +\date{17 avril 2023} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +La longueur du sujet ne doit pas effrayer : l'énoncé est long parce +que des rappels ont été faits et que la rédaction des questions +cherche à éviter toute ambiguïté. De plus, il ne sera pas nécessaire +de traiter la totalité pour avoir la note maximale. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 2h + +Barème \emph{indicatif} : $5+5+5+7$ (sur $20$) + +\ifcorrige +Ce corrigé comporte 8 pages (page de garde incluse). +\else +Cet énoncé comporte 4 pages (page de garde incluse). +\fi + +\vfill +{\noindent\tiny +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +On considère le jeu de nim éventuellement transfini. (On rappelle +qu'il est défini de la manière suivante : une position du jeu est un +tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a +« $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à +décroître strictement \emph{un et un seul} des $\alpha_i$, autrement +dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers +$(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis +à la place de $\alpha_i$.) + +Pour chacune des positions suivantes, dire si c'est une position P +(c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N +(c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce +dernier cas, donner un coup gagnant possible pour le joueur en +question. + +(a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne +avec $2$, et une ligne avec $3$) + +\begin{corrige} +On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si +bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la +position est $0$, et c'est donc une position P. +\end{corrige} + +(b) $(3,6,9)$ + +\begin{corrige} +On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus +2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6 +\oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de +la position est $12$, et c'est donc une position N. + +Pour trouver un coup gagnant, c'est-à-dire un coup vers une +position P, on cherche à annuler la valeur de Grundy : autrement dit, +on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n +\oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus +12 < n$. On vérifie facilement que la seule possibilité est de +réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$ +bâtonnets. Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$. +\end{corrige} + +(c) $(\omega,\omega2,\omega3)$ + +\begin{corrige} +En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 = +2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on +a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de +Grundy de la position est $0$, et c'est donc une position P. +\end{corrige} + +(d) $(\omega,\omega^2,\omega^3)$ + +\begin{corrige} +En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 = +2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc +$\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} + +2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de +Grundy de la position est $\gamma \neq 0$, et c'est cdonc une +position N. + +Comme dans la question (b), on cherche à annuler la valeur de Grundy, +autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne +par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 + +\omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2} +\oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit. +On vérifie facilement que la seule possibilité est de réduire la ligne +ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 + +\omega$ bâtonnets. Bref, le seul coup gagnant est +$(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$. +\end{corrige} + +(e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$ + +\begin{corrige} +En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a +$\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} = +2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega} += 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} = +2^{\omega^\omega}$. Le raisonnement est alors exactement analogue à +la question (d) (car la seule chose qui importe dans cette question +ait qu'on ait affaire à trois puissances de $2$ distinctes) : la +valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} + +2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega + +\omega \neq 0$ donc c'est une position N, et le seul coup gagnant est +$(\omega,\omega^\omega,\omega^{\omega^\omega}) \to +(\omega,\omega^\omega,\omega^\omega + \omega)$. +\end{corrige} + +(f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0 +< \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre +premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme + la limite, c'est-à-dire la borne supérieure, de la suite + $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 = + (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1 + = \omega^{(\varepsilon_n) + 1}$ et $u_2 = + \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas + besoin de ce fait.} vérifiant $\varepsilon = \omega^\varepsilon$. + +\begin{corrige} +Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a +$\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} = +2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} = +2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} = +2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement +vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$). +Le raisonnement est alors exactement analogue aux questions (d) et (e) +(car la seule chose qui importe dans ces questions ait qu'on ait +affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de +la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} + +2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq +0$ donc c'est une position N, et le seul coup gagnant est +$(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1, +\varepsilon_2, \varepsilon_2 + \varepsilon_1)$. +\end{corrige} + +(g) Donner un exemple de position N du jeu de nim (de préférence fini) +avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les +$\alpha_i$ sont deux à deux distincts), où il existe strictement plus +qu'un coup gagnant pour le joueur qui doit jouer. (Pour indication, +ceci est possible à partir de trois lignes de bâtonnets.) + +\begin{corrige} +On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de +bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle +qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement +inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la +question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus +n_3$ et de façon analogue pour les trois autres. On cherche donc, par +exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$. +Ceci n'est pas difficile en prenant par exemple pour $n_1$ une +puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et +de $n_3$ mais telle qu'en l'enlevant on obtienne des nombres +strictement plus petits. Par exemple, la position $(2,6,7)$ (de +valeur de Grundy $2\oplus 6\oplus 7 = 3 =: g$) admet des coups +gagnants vers $(2,5,7)$ ou $(2,6,4)$ ou même $(1,6,7)$. +\end{corrige} + + +% +% +% + +\exercice + +Si $G$ est un graphe orienté bien-fondé (qu'on peut considérer comme +l'ensemble des positions d'un jeu combinatoire auquel il ne manque que +l'information, sans pertinence ici, de la position initiale), on +rappelle qu'on a défini la fonction rang +\[ +\rk(x) := \sup\nolimits^+\{\rk(y) : y\in\outnb(x)\} = \sup\,\{\rk(y)+1 : +y\in\outnb(x)\} +\] +(en notant $\sup^+ S$ le plus petit ordinal strictement supérieur à +tous les ordinaux de $S$ et $\sup S$ le plus petit ordinal supérieur +ou égal à tous les ordinaux de $S$, et $\outnb(x)$ l'ensemble des +voisins sortants de $x$), et la fonction de Grundy +\[ +\gr(x) := \mex\,\{\gr(y) : y\in\outnb(x)\} +\] +(où $\mex S$ désigne le plus petit ordinal qui n'est pas dans $S$), +— ces définitions ayant bien un sens par induction bien-fondée. La +première mesure en quelque sorte la durée du jeu si les deux joueurs +coopèrent pour le faire durer aussi longtemps que possible, et la +seconde nous donne notamment l'information de quel joueur a une +stratégie gagnante. + +On va maintenant définir une fonction qui mesure en quelque sorte la +durée du jeu si le joueur perdant cherche à perdre aussi lentement que +possible tandis que le joueur gagnant cherche à gagner aussi vite que +possible. Précisément, on pose +\[ +\left\{ +\begin{array}{ll} +\dur(x) := \sup\,\{\dur(y)+1 : y\in\outnb(x)\} +&\;\;\text{si $\gr(x) = 0$}\\ +\dur(x) := \min\,\{\dur(y)+1 : y\in\outnb(x)\text{~et~}\gr(y)=0\} +&\;\;\text{si $\gr(x) \neq 0$}\\ +\end{array} +\right. +\] +(où $\min S$ désigne le plus petit ordinal de $S$, si $S$ est un +ensemble non-vide d'ordinaux). + +(1) Expliquer pourquoi cette définition a bien un sens (on +prendra garde au fait que $\min\varnothing$ n'est pas défini). + +\begin{corrige} +Lorsque $\gr(x) \neq 0$, il existe au moins un voisin sortant $y \in +\outnb(x)$ tel que $\gr(y) = 0$ (car le $\mex$ est la plus petite +valeur exclue: si un tel $y$ n'existait pas, le $\mex$ serait $0$) : +ceci assure que le $\min$ dans la deuxième ligne de la définition +porte toujours sur un ensemble non-vide. + +En-dehors de ce fait, la définition ne pose pas de problème : le +$\sup$ d'un ensemble d'ordinaux existe toujours, et la récursivité de +la définition est légitime par induction bien-fondée, c'est-à-dire que +$\dur(x)$ peut faire appel aux valeurs de $\dur(y)$ pour des voisins +sortants $y$ de $x$. (Le fait de faire appel à $\gr(y)$ n'est pas un +problème car on sait que $\gr$ est bien défini, et la distinction en +cas est légitime de toute manière.) +\end{corrige} + +(2) Expliquer rapidement et informellement pourquoi $\dur(x)$ +correspond bien à l'explication intuitive qu'on a donnée. + +\begin{corrige} +Quand $x$ est une position avec $\gr(x) = 0$, c'est-à-dire une +position P, le joueur qui doit jouer est le joueur perdant (n'ayant +pas de stratégie gagnante) : il joue donc vers une position $y$ le +faisant perdre le plus lentement possible, c'est-à-dire avec $\dur(y)$ +aussi grand que possible, d'où la définition $\dur(x) = +\sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ dans ce cas (le $+1$ sert à +compter le coup joué par ce joueur). + +Au contraire, lorsque $\gr(x) \neq 0$, c'est-à-dire que $x$ est une +position N, le joueur qui doit jouer est le joueur gagnant : il joue +donc vers une position $y$ le faisant gagner le plus rapidement +possible, c'est-à-dire avec $\dur(y)$ aussi petit que possible parmi +les coups $x\to y$ gagnants, autrement dit ceux pour lesquels $\gr(y) += 0$, d'où la définition $\dur(x) = \min\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\}$ dans ce cas (le $+1$ sert à +compter le coup joué par ce joueur). +\end{corrige} + +(3) Sur le graphe $G$ représenté ci-dessous, calculer chacune des +fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à +étiqueter les sommets) : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,circle] {A}; +\node (nB) at (0bp,-40bp) [draw,circle] {B}; +\node (nC) at (40bp,0bp) [draw,circle] {C}; +\node (nD) at (40bp,-40bp) [draw,circle] {D}; +\node (nE) at (80bp,0bp) [draw,circle] {E}; +\node (nF) at (80bp,-40bp) [draw,circle] {F}; +\node (nG) at (120bp,-40bp) [draw,circle] {G}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip +Si on joue à partir du sommet A comme position initiale et que, comme +suggéré dans la définition de $\dur$, le joueur perdant cherche à +perdre aussi lentement que possible tandis que le joueur gagnant +cherche à gagner aussi vite que possible, quelle sera le déroulement +du jeu ? + +\begin{corrige} +Les sommets ont été fort sympathiquement étiquetés dans un ordre +compatible avec le rang (tri topologique), c'est-à-dire que chaque +arête pointe vers un sommet situé strictement après dans l'ordre +alphabétique. On effectue donc les calculs dans l'ordre alphabétique +inversé. On trouve, pour le rang : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,circle] {$4$}; +\node (nB) at (0bp,-40bp) [draw,circle] {$3$}; +\node (nC) at (40bp,0bp) [draw,circle] {$3$}; +\node (nD) at (40bp,-40bp) [draw,circle] {$2$}; +\node (nE) at (80bp,0bp) [draw,circle] {$2$}; +\node (nF) at (80bp,-40bp) [draw,circle] {$1$}; +\node (nG) at (120bp,-40bp) [draw,circle] {$0$}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip + +Pour la valeur de Grundy : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,circle] {$0$}; +\node (nB) at (0bp,-40bp) [draw,circle] {$1$}; +\node (nC) at (40bp,0bp) [draw,circle] {$1$}; +\node (nD) at (40bp,-40bp) [draw,circle] {$0$}; +\node (nE) at (80bp,0bp) [draw,circle] {$2$}; +\node (nF) at (80bp,-40bp) [draw,circle] {$1$}; +\node (nG) at (120bp,-40bp) [draw,circle] {$0$}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip + +Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à +suivre, on a entouré en double les sommets de valeur de Grundy $0$) : + +\begin{center}\footnotesize +\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp] +\node (nA) at (0bp,0bp) [draw,double,circle] {$4$}; +\node (nB) at (0bp,-40bp) [draw,circle] {$1$}; +\node (nC) at (40bp,0bp) [draw,circle] {$3$}; +\node (nD) at (40bp,-40bp) [draw,double,circle] {$2$}; +\node (nE) at (80bp,0bp) [draw,circle] {$1$}; +\node (nF) at (80bp,-40bp) [draw,circle] {$1$}; +\node (nG) at (120bp,-40bp) [draw,double,circle] {$0$}; +\draw[->] (nA) -- (nB); +\draw[->] (nA) -- (nC); +\draw[->] (nB) -- (nD); +\draw[->] (nB) to[out=315,in=225] (nG); +\draw[->] (nC) -- (nD); +\draw[->] (nC) -- (nE); +\draw[->] (nD) -- (nF); +\draw[->] (nE) -- (nF); +\draw[->] (nF) -- (nG); +\draw[->] (nE) to[out=0,in=90] (nG); +\end{tikzpicture} +\end{center} +\vskip-\baselineskip + +Si on joue à partir de la position A, le premier joueur, appelons-la +Alice, est en position perdante car la valeur de Grundy est nulle, et +va jouer vers C car c'est ce qui maximise la fonction $\dur$ ; son +adversaire, appelons-le Bob, joue alors vers D car c'est le seul coup +gagnant, après quoi Alice joue vers F (seul coup possible) et Bob joue +vers G. +\end{corrige} + +(4) Montrer que, dans n'importe quel graphe $G$ bien-fondé, et pour +n'importe quel sommet $x$ de $G$, on a $\dur(x) \leq \rk(x)$. + +\begin{corrige} +On montre par induction bien-fondée que $\dur(x) \leq \rk(x)$. On +peut donc faire l'hypothèse qu'on sait que $\dur(y) \leq \rk(y)$ pour +tout voisin sortant $y \in \outnb(x)$ (hypothèse d'induction). Dans +le cas où $\gr(x) = 0$, on a $\dur(x) = \sup\,\{\dur(y)+1 : +y\in\outnb(x)\}$, qui est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\}$ +par hypothèse d'induction (il est clair qu'augmenter au sens large +tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens +large), et ceci vaut $\rk(x)$ par définition. Dans le cas où $\gr(x) +\neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 : +y\in\outnb(x)\}$ de façon évidente ($\min S \leq \sup S$ est clair), +et pour la même raison que précédemment, ceci est $\leq +\sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$. +\end{corrige} + + +% +% +% + +\exercice + +Soit $G$ un graphe orienté dont l'ensemble des sommets est (au plus) +dénombrable, et soit $x_0$ un sommet de $G$. (Il n'y a pas d'autre +hypothèse sur $G$, par exemple on ne suppose pas que $G$ est +bien-fondé.) + +On considère le jeu suivant. Deux joueurs s'affrontent, qu'on +appellera \emph{le Fugueur} et \emph{le Borneur}. Le Fugueur +commence, après quoi ils jouent tour à tour. En partant de $x_0$, +chaque joueur, quand vient son tour, choisit un voisin sortant de la +position actuelle $x$ \emph{ou bien} choisit de conserver $x$ ; +autrement dit, il choisit un élément de $\outnb(x) \cup \{x\}$. (Pour +être parfaitement clair : au premier tour, le Fugueur choisit $x_1 \in +\outnb(x_0) \cup \{x_0\}$, puis le Borneur choisit $x_2 \in +\outnb(x_1) \cup \{x_1\}$, et ainsi de suite.) Le jeu dure infiniment +longtemps (manifestement, les règles permettent toujours à chaque +joueur de faire un coup). Au bout d'un nombre infini de coups, on +considère la suite $(x_n)_{n\in\mathbb{N}}$ de toutes les positions +traversées : +\begin{itemize} +\item si cette suite est d'image finie (c'est-à-dire que l'ensemble + $\{x_n : n\in\mathbb{N}\}$ de toutes les positions traversées est + fini), alors le Borneur a gagné ; +\item sinon, le Fugueur a gagné. +\end{itemize} + +(1) Montrer, en appliquant un des résultats du cours, que l'un des +joueurs a nécessairement une stratégie gagnante (on ne demande pas de +préciser lequel). On pourra préalablement montrer que pour toute +partie $F \subseteq G$, la partie $F^{\mathbb{N}} \subseteq +G^{\mathbb{N}}$ est \emph{fermée} (pour la topologie sur +$G^{\mathbb{N}}$ produit de la topologie +discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}), et +en déduire une propriété de l'ensemble +$\bigcup_{F\text{~fini~}\subseteq G} F^{\mathbb{N}}$ réunion des +$F^{\mathbb{N}}$ où $F$ parcourt toutes les parties \emph{finies} +de $G$. + +\begin{corrige} +Pour commencer, montrons que si $F$ est une partie de $G$ alors +$F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée. Ceci revient à +montrer que son complémentaire est ouvert, autrement dit, que si +$\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, +alors il existe un voisinage fondamental de $\dblunderline{x}$ qui ne +rencontre pas $F^{\mathbb{N}}$. Or si $\dblunderline{x} \in +G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, c'est qu'elle a une +valeur $x_\ell$ qui n'est pas dans $F$, et toute suite commençant par +$x_0,\ldots,x_\ell$ n'est pas dans $F^{\mathbb{N}}$, c'est-à-dire que +le voisinage fondamental $V_{\ell+1}(\dblunderline{x})$ est inclus +dans le complémentaire de $F^{\mathbb{N}}$. Ceci achève de montrer +que $F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée. + +Maintenant, l'ensemble $\mathscr{F}$ des parties finies d'un ensemble +(au plus) dénombrable, en l'occurrence, $G$, est (au plus) +dénombrable. Ce fait peut être tenu pour acquis, mais rappelons +pourquoi il est vrai : en effet, si $G = \{g_i : i\in\mathbb{N}\}$, +alors on peut par exemple énumérer $\mathscr{F}$ à travers les +écritures binaires, ou plus précisément, $\mathscr{F} = \{F_n : +n\in\mathbb{N}\}$ où $F_n$ désigne la partie finie +$\{g_{i_0},\ldots,g_{i_r}\}$ lorsque $n = 2^{i_0} + \cdots + 2^{i_r}$ +avec $i_0,\ldots,i_r$ entiers naturels distincts (autrement dit, $F_0 += \varnothing$, $F_1 = \{g_0\}$, $F_2 = \{g_1\}$, $F_3 = \{g_0,g_1\}$, +etc.). Peu importe le fait qu'il y ait des répétitions dans +l'énumération $F_n$ (un ensemble surjecté par $\mathbb{N}$ est encore +dénombrable). + +Ceci nous permet de dire que $\bigcup_{F\text{~fini~}\subseteq G} +F^{\mathbb{N}}$, autrement dit $\bigcup_{F \in \mathscr{F}} +F^{\mathbb{N}}$, est une réunion dénombrable de fermés +dans $G^{\mathbb{N}}$. Comme un fermé est borélien, c'est une réunion +dénombrable de boréliens, donc c'est encore un borélien. + +Enfin, remarquons que dire que l'ensemble $\{x_n : n\in\mathbb{N}\}$ +est fini revient à dire qu'il est inclus un ensemble fini $F$, +autrement dit, que la suite $\dblunderline{x} = (x_n)$ appartient à +$F^{\mathbb{N}}$ pour un certain ensemble fini $F$, ou, ce qui revient +au même, qu'elle appartient à $\bigcup_{F \in \mathscr{F}} +F^{\mathbb{N}}$. + +On a donc affaire à un jeu de Gale-Stewart défini par l'ensemble de +suites $B := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien (ou +par son complémentaire $A := G^{\mathbb{N}} \setminus B$ si on prend +le point de vue du Fugueur). Le théorème de détermination borélienne +de Martin assure que l'un des joueurs a forcément une stratégie +gagnante. +\end{corrige} + +(2) Indépendamment de la question précédente, donner un exemple de +couple $(G,x_0)$ pour lequel le Borneur possède une stratégie gagnante +à ce jeu. Donner un exemple pour lequel le Fugueur en possède une. +(On cherchera à donner des exemples aussi simples que possibles.) + +\begin{corrige} +Si $G$ est le graphe formé du seul sommet $x_0$, alors le Borneur +gagne trivialement (la suite sera la suite constante). + +Si $G$ est le graphe formé des entiers naturels avec une arête $i \to +j$ lorsque $i<j$ (autrement dit des petits entiers naturels vers les +grands), ou même seulement $i \to i+1$, alors le Fugueur a une +stratégie gagnante consistant à jouer de $i$ vers $i+1$, ce qui assure +que la suite $(x_{2i+1})$ des positions choisies par le Fugueur est +strictement croissante quoi que fasse le Borneur (il ne peut pas +revenir en arrière), et notamment, elle n'est pas d'image finie. +\end{corrige} + + +% +% +% + +\exercice + +On considère une variante \emph{à somme (possiblement) non-nulle} de +Pierre-Papier-Ciseaux, à savoir le jeu en forme normale défini par la +matrice de gain suivante : +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&$U$&$V$&$W$\\\hline +$U$&$x,x$&$-1,+1$&$+1,-1$\\ +$V$&$+1,-1$&$x,x$&$-1,+1$\\ +$W$&$-1,+1$&$+1,-1$&$x,x$\\ +\end{tabular} +\end{center} +où $x$ est un réel et, pour plus de commodité, on a écrit $U$ pour +« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ». (La ligne +correspond à l'option choisie par Alice, la colonne à l'option de Bob, +et chaque case indique le gain d'Alice suivi du gain de Bob.) + +Le but de l'exercice est d'étudier les équilibres de Nash de ce jeu. + +(On prendra bien note, pour simplifier les raisonnements en cas, du +fait que les options ont une symétrie cyclique\footnote{C'est-à-dire + que remplacer $U$ par $V$ et $V$ par $W$ et $W$ par $U$ ne change + rien au jeu.}, et que les joueurs ont eux aussi des rôles +symétriques.) + +(1) Considérons le profil de stratégies mixtes dans lequel les deux +joueurs choisissent chacun chaque option avec probabilité +$\frac{1}{3}$ (c'est-à-dire la stratégie qui est optimale dans le cas +à somme nulle). Pour quelle(s) valeur(s) de $x$ ce profil est-il un +équilibre de Nash ? + +\begin{corrige} +Pour des raisons de symétrie, si l'un des joueurs joue cette stratégie +mixte $\frac{1}{3}U + \frac{1}{3}V + \frac{1}{3}W$, le gain espéré de +chacun des deux joueurs est le même quelle que soit la stratégie pure, +donc aussi mixte, de l'autre joueur. Cette valeur se calcule +d'ailleurs aisément (comme somme des trois colonnes, ou des trois +lignes, de la matrice de gains, affectées des +coefficients $\frac{1}{3}$) : c'est $\frac{1}{3}x$ ; mais la seule +chose qui importe est que l'adversaire ait le même gain espéré quelle +que soit la stratégie pure, donc aussi mixte, qu'il choisit : il n'a +donc pas intérêt à changer unilatéralement sa stratégie. Il s'agit +donc \emph{toujours} d'un équilibre de Nash, quelle que soit la valeur +de $x$. +\end{corrige} + +\emph{On suppose dorénavant que $x<-1$.} + +(2) Existe-t-il un équilibre de Nash dans lequel Alice joue purement +$U$ ? (On raisonnera les options pouvant être dans le support de la +stratégie de Bob en réponse.) En déduire tous les équilibres de Nash +dans lesquels au moins un joueur joue une stratégie pure. + +\begin{corrige} +Si Alice joue purement $U$, les gains de Bob pour les différentes +stratégies pures de sa réponse sont $x$ pour $U$, $+1$ pour $V$ et +$-1$ pour $W$ d'après la matrice de gains. Comme $+1 > -1 > x$, la +seule option qui peut faire partie du support d'une meilleure réponse +de Bob est $V$, autrement dit, si Alice joue purement $U$ dans un +équilibre de Nash, Bob répond forcément purement $V$. Mais par le +même raisonnement (compte tenu de la symétrie cyclique des options et +de la symétrie des joueurs), si Bob joue purement $V$, Alice joue $W$ +(et pas $U$ comme supposé). Il ne peut donc pas y avoir d'équilibre +de Nash dans lequel Alice joue purement $U$. Et de nouveau par +symétrie cyclique des options et symétrie des joueurs, il ne peut y +avoir aucun équilibre de Nash dans lequel un joueur jouerait une +stratégie pure. +\end{corrige} + +(3) Dans cette question et la suivante, envisageons un équilibre de +Nash dans lequel Alice joue la stratégie mixte $pU + (1-p)V$ avec +$0<p<1$. Supposons dans cette question que Bob réponde avec un une +stratégie mixte ayant elle aussi $\{U,V\}$ comme support. Montrer que +$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$. En +utilisant le fait que $\frac{x^2+1}{2x} < -\frac{1}{x}$ lorsque $x<-1$ +(qu'on admettra pour ne pas perdre son temps en calculs inutiles), en +déduire qu'un tel équilibre de Nash n'existe pas. + +\begin{corrige} +Si Alice joue $pU + (1-p)V$, les gains espérés de Bob pour les +différences stratégies pures de sa réponse sont $px-(1-p) = +-1+(x+1)p$ pour $U$, $p + (1-p)x = x-(x-1)p$ pour $V$ et $-p + (1-p) = +1-2p$ pour $W$. Si une meilleure réponse de Bob a $\{U,V\}$ comme +support, ces deux options doivent apporter le même gain espéré, +c'est-à-dire qu'on doit avoir $-1+(x+1)p = x-(x-1)p$, ce qui équivaut +à $p = \frac{x+1}{2x}$, et le gain en question est $\frac{x^2+1}{2x}$, +tandis que le gain espéré pour $W$ est alors $1-2p = -\frac{1}{x}$. +D'après l'inégalité $\frac{x^2+1}{2x} < -\frac{1}{x}$, l'option $W$ +fournit un meilleur gain espéré pour Bob, donc $\{U,V\}$ ne peut pas +être le support d'une meilleure réponse de Bob à $pU + (1-p)V$ +d'Alice. +\end{corrige} + +(4) On considère toujours un équilibre de Nash dans lequel Alice joue +la stratégie mixte $pU + (1-p)V$ avec $0<p<1$. Supposons maintenant +que Bob réponde avec une stratégie mixte ayant (au moins) $U$ et $W$ +dans son support support. Montrer que $p = \frac{2}{x+3}$ (et +que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ lorsque +$-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (de nouveau, on +admettra ces faits pour ne pas perdre de temps en calculs), en déduire +qu'un tel équilibre de Nash n'existe pas. + +\begin{corrige} +On a dit dans la question (3) que si Alice joue $pU + (1-p)V$, les +gains espérés de Bob pour les différences stratégies pures de sa +réponse sont $px-(1-p) = -1+(x+1)p$ pour $U$, $p + (1-p)x = +x-(x-1)p$ pour $V$ et $-p + (1-p) = 1-2p$ pour $W$. Si une meilleure +réponse de Bob a $U$ et $W$ dans son support, ces deux options doivent +apporter le même gain espéré, c'est-à-dire qu'on doit avoir $-1+(x+1)p += 1-2p$, ce qui équivaut à $(x+3)p = 3$, donc $x\neq 3$ et $p = +\frac{2}{x+3}$. D'après les inégalités admises, $p$, qui devrait être +entre $0$ et $1$, ne l'est jamais si $x<-1$, donc un tel équilibre de +Nash n'existe pas. +\end{corrige} + +(5) Expliquer soigneusement pourquoi les questions (2) à (4) montrent +que dans tout équilibre de Nash du jeu considéré, les deux joueurs +jouent une stratégie mixte ayant $\{U,V,W\}$ comme support (i.e., +aucun ensemble strictement plus petit n'est possible). + +\begin{corrige} +On a vu en (2) qu'il n'existe aucun équilibre de Nash dans lequel un +joueur joue une stratégie pure. Supposons maintenant un équilibre de +Nash dans lequel un joueur a deux options dans son support. Par +symétrie, sans perte de généralité, on peut supposer que c'est Alice +et que ces deux options sont $U$ et $V$. Comme les stratégies pures +sont exclues, les supports possibles de la réponse de Bob sont : +$\{U,V\}$, $\{U,W\}$, $\{V,W\}$ et $\{U,V,W\}$. Dans la question (3) +on a exclu $\{U,V\}$ ; dans la question (4), on a exclu $\{U,W\}$ et +$\{U,V,W\}$. Reste le cas où le support de la stratégie de Bob est +$\{V,W\}$ (tandis que celui d'Alice est, on le rappelle, $\{U,V\}$). +Mais quitte à effectuer une symétrie cyclique des options ($U\to W\to +V\to U$) et échanger les joueurs, cela revient au cas où le support de +la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : or +on a déjà exclu ce cas. Il ne reste donc aucune possibilité. +\end{corrige} + +(6) Envisageons maintenant un équilibre de Nash dans lequel Alice joue +une stratégie mixte $pU + p'V + (1-p-p')W$ avec $p>0$, $p'>0$ et +$1-p-p'>0$ et Bob répond par une stratégie ayant elle aussi +$\{U,V,W\}$ comme support. Écrire un système de deux équations +linéaires vérifié par $p,p'$, justifier que ce système est +non-dégénéré et conclure. Quels sont tous les équilibres de Nash du +jeu ? + +\begin{corrige} +Si Alice joue $pU + p'V + (1-p-p')W$, les gains espérés de Bob pour +les différences stratégies pures de sa réponse sont $px - p' + +(1-p-p') = 1 + (x-1)p - 2p'$ pour $U$, $p + p' x - (1-p-p') = -1 + 2p ++ (x+1)p'$ pour $V$ et $-p + p' + (1-p-p')x = x -(x+1)p - +(x-1)p'$ pour $W$. Si une meilleure réponse de Bob a $\{U,V,W\}$ +comme support, ces trois options doivent apporter le même gain espéré, +c'est-à-dire que $1 + (x-1)p - 2p' = -1 + 2p + (x+1)p' = x -(x+1)p - +(x-1)p'$, ou (en soustrayant, disons, le premier membre aux deux +autres) : +\[ +\begin{aligned} +-(x-3)p + (x+3)p' &= 2\\ +- 2xp - (x-3)p' &= -(x-1) +\end{aligned} +\] +Le déterminant de ce système est $(x-3)^2 + 2x(x+3) = 3(x^2+3)$ qui +est non nul quel que soit $x$, donc le système est non-dégénéré : la +solution $p=p'=\frac{1}{3}$ trouvée en (1) est donc la seule solution. + +Bref, on a montré que le seul équilibre de Nash dans lequel les +supports des stratégies d'Alice et Bob sont $\{U,V,W\}$ est celui +décrit en (1) ; comme on a vu en (5) que ceci est la seule possibilité +de support, il s'agit du seul équilibre de Nash du jeu. +\end{corrige} + + + + + +% +% +% +\end{document} diff --git a/controle-20240422.tex b/controle-20240422.tex new file mode 100644 index 0000000..8bab6a4 --- /dev/null +++ b/controle-20240422.tex @@ -0,0 +1,576 @@ +%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? +\documentclass[12pt,a4paper]{article} +\usepackage[a4paper,margin=2.5cm]{geometry} +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +%\usepackage{ucs} +\usepackage{times} +% A tribute to the worthy AMS: +\usepackage{amsmath} +\usepackage{amsfonts} +\usepackage{amssymb} +\usepackage{amsthm} +% +\usepackage{mathrsfs} +\usepackage{wasysym} +\usepackage{url} +% +\usepackage{graphics} +\usepackage[usenames,dvipsnames]{xcolor} +\usepackage{tikz} +\usetikzlibrary{matrix,calc} +\usepackage{hyperref} +% +%\externaldocument{notes-mitro206}[notes-mitro206.pdf] +% +\theoremstyle{definition} +\newtheorem{comcnt}{Tout} +\newcommand\thingy{% +\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } +\newcommand\exercice{% +\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak} +\renewcommand{\qedsymbol}{\smiley} +% +\newcommand{\outnb}{\operatorname{outnb}} +\newcommand{\downstr}{\operatorname{downstr}} +\newcommand{\precs}{\operatorname{precs}} +\newcommand{\mex}{\operatorname{mex}} +\newcommand{\id}{\operatorname{id}} +\newcommand{\limp}{\Longrightarrow} +\newcommand{\gr}{\operatorname{gr}} +\newcommand{\rk}{\operatorname{rk}} +\newcommand{\dur}{\operatorname{dur}} +\newcommand{\fuzzy}{\mathrel{\|}} +% +\newcommand{\dblunderline}[1]{\underline{\underline{#1}}} +% +\DeclareUnicodeCharacter{00A0}{~} +% +\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C} +\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D} +% +\DeclareFontFamily{U}{manual}{} +\DeclareFontShape{U}{manual}{m}{n}{ <-> manfnt }{} +\newcommand{\manfntsymbol}[1]{% + {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}} +\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped +\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2% + \hbox to0pt{\hskip-\hangindent\dbend\hfill}} +% +\newcommand{\spaceout}{\hskip1emplus2emminus.5em} +\newif\ifcorrige +\corrigetrue +\newenvironment{corrige}% +{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi% +\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} +{{\hbox{}\nobreak\hfill\checkmark}% +\ifcorrige\par\smallbreak\else\egroup\par\fi} +% +% +% +\begin{document} +\ifcorrige +\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} +\else +\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} +\fi +\author{} +\date{22 avril 2024} +\maketitle + +\pretolerance=8000 +\tolerance=50000 + +\vskip1truein\relax + +\noindent\textbf{Consignes.} + +Les exercices sont totalement indépendants. Ils pourront être traités +dans un ordre quelconque, mais on demande de faire apparaître de façon +très visible dans les copies où commence chaque exercice. + +\medbreak + +L'usage de tous les documents (notes de cours manuscrites ou +imprimées, feuilles d'exercices, livres) est autorisé. + +L'usage des appareils électroniques est interdit. + +\medbreak + +Durée : 2h + +\ifcorrige +Ce corrigé comporte 6 pages (page de garde incluse). +\else +Cet énoncé comporte 3 pages (page de garde incluse). +\fi + +\vfill +{\noindent\tiny +\immediate\write18{sh ./vc > vcline.tex} +Git: \input{vcline.tex} +\immediate\write18{echo ' (stale)' >> vcline.tex} +\par} + +\pagebreak + + +% +% +% + +\exercice + +\textbf{(1)} On considère le jeu en forme normale défini par la +matrice de gain suivante : +\begin{center} +\begin{tabular}{r|cc} +$\downarrow$Alice, Bob$\rightarrow$&$X$&$Y$\\\hline +$X$&$1$&$0$\\ +$Y$&$0$&$2$\\ +\end{tabular} +\end{center} +Un seul nombre a été inscrit dans chaque case car les gains des deux +joueurs sont \emph{égaux}, et c'est ce nombre-là qui est écrit +(attention, il ne s'agit pas d'un jeu à somme nulle, au contraire : au +lieu d'être opposés, les intérêts des deux joueurs sont parfaitement +identiques). + +Étudier et déterminer tous les équilibres de Nash de ce jeu : on +commencera par considérer ceux en stratégies pures, puis par +considérer les cas où un joueur, ou l'autre, ou les deux, joue une +stratégie strictement mixte (i.e., ayant pour support $\{X,Y\}$). + +\begin{corrige} +Si Alice joue (purement) $X$, les options de Bob apportent les gains +$1$ pour $X$ et $0$ pour $Y$, dont la seule meilleure réponse de Bob +est de jouer purement $X$. De même, si Alice joue (purement) $Y$, les +options de Bob apportent les gains $0$ pour $X$ et $2$ pour $Y$, dont +la seule meilleure réponse de Bob est de jouer purement $Y$. Le rôle +des deux joueurs étant symétrique, ceci prouve que, dans un équilibre +de Nash, si l'un joue purement une des deux options, l'autre doit +jouer la même, et ceci donne bien deux équilibres de Nash, $(X,X)$ +(avec gain $1$) et $(Y,Y)$ (avec gain $2$). + +Si Alice joue une stratégie strictement mixte dans un équilibre de +Nash, on vient de voir que Bob joue $pX + (1-p)Y$, l'espérance de gain +d'Alice doit être la même pour les deux options du support de sa +stratégie, c'est-à-dire que $p = 2(1-p)$, donc $p = \frac{2}{3}$. Par +symétrie, Bob joue aussi cette stratégie, et on vérifie que ceci donne +bien un équilibre de Nash, $(\frac{2}{3}X + \frac{1}{3}Y, \; +\frac{2}{3}X + \frac{1}{3}Y)$. +\end{corrige} + +\textbf{(2)} Plus généralement, on considère un jeu de la forme +suivante : les deux joueurs ont le même ensemble d'options, notons-le +$\{X_1,\ldots,X_N\}$, et ils ont le même gain $u_A(a,b) = u_B(a,b)$ +pour $a,b\in \{X_1,\ldots,X_N\}$, et de plus ce gain vaut $0$ lorsque +$b\neq a$ et il vaut $g_i$ lorsque $a = b = X_i$, où tous les $g_i$ +sont des réels strictement positifs ($g_i > 0$). Pour résumer : +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&$X_1$&$\cdots$&$X_N$\\\hline +$X_1$&$g_1$&$\cdots$&$0$\\ +$\vdots$&$\vdots$&$\ddots$&$\vdots$\\ +$X_N$&$0$&$\cdots$&$g_N$\\ +\end{tabular} +\end{center} + +\textbf{(a)} Montrer que, dans un équilibre de Nash d'un jeu comme on +vient de le dire, si $I \subseteq \{X_1,\ldots,X_N\}$ est le +support\footnote{On rappelle que le support d'une stratégie mixte est +l'ensemble des options qu'elle choisit avec une probabilité $>0$.} de +la stratégie d'Alice, le support $J$ de la stratégie de Bob est inclus +dans $I$. (\emph{Indication :} toute option hors de $I$ apporte un +gain espéré nul, donc strictement moins bon que n'importe quelle +combinaison convexe d'options dans $I$.) En déduire par symétrie +que $I=J$. + +\begin{corrige} +Si $X_j \not\in I$, alors l'option $X_j$ apporte un gain nul à Bob, +tandis que toute option $X_i \in I$ apporte un gain strictement +positif (puisque $g_i$ est pondéré avec un coefficient strictement +positif, tout le reste étant nul). Il s'ensuit qu'une meilleure +réponse possible de Bob ne peut pas inclure $X_j$ : elle ne peut donc +inclure que des options dans $I$. Donc $J \subseteq I$. Et par +symétrie des deux joueurs, $I \subseteq J$. Donc finalement $I = J$. +\end{corrige} + +\textbf{(b)} Toujours en considérant un équilibre de Nash d'un tel +jeu, en notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie (mixte) +d'Alice, montrer que les $g_i p_i$ tels que $p_i > 0$ (c'est-à-dire +$X_i \in I$) sont tous égaux entre eux. En déduire par symétrie le +résultat analogue pour la stratégie de Bob, donc qu'elles sont égales. +En déduire qu'il existe au plus $2^N - 1$ équilibres de Nash, un pour +chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$. + +\begin{corrige} +En notant $p_1 X_1 + \cdots + p_N X_N$ la stratégie d'Alice, pour +toute option $X_i \in J = I$ de Bob, le gain espéré de $X_i$ doit être +toujours le même. Or ce gain est $g_i p_i$. Donc tous les $g_i p_i$ +pour $X_i \in I$ sont égaux. C'est-à-dire que les $p_i$ sont +proportionnels aux $\frac{1}{g_i}$ pour $X_i \in I$ (les autres étant +nuls). Ceci détermine la stratégie d'Alice, et par symétrie c'est +aussi celle de Bob. On a donc trouvé $2^N - 1$ équilibres de Nash +potentiels : pour toute partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on +pose calcule $p_i$ comme le quotient de $\frac{1}{g_i}$ par la somme +des $\frac{1}{g_j}$ pour $X_j \in I$ si $X_i \in I$ (et $0$ sinon), et +Alice et Bob jouent chacun $p_1 X_1 + \cdots + p_N X_N$. +\end{corrige} + +\textbf{(c)} Vérifier que les stratégies mixtes trouvées en (b) sont +bien des équilibres de Nash du jeu, et conclure qu'il a exactement +$2^N - 1$ équilibres de Nash, qu'on décrira explicitement. + +\begin{corrige} +Pour chaque partie non vide $I$ de $\{X_1,\ldots,X_N\}$ on a bien +décrit une stratégie mixte pour chacun des deux joueurs (c'est la +même) : on a bien affaire à des réels $p_i$ positifs de somme $1$. Le +gain espéré de $X_j$ contre $p_1 X_1 + \cdots + p_N X_N$ est $0$ si +$X_j \not\in I$ et $g_j p_j$ (qui ne dépend pas de $j$) si $X_j \in +I$ : on ne peut pas faire mieux (avec une stratégie pure, donc a +fortiori avec une stratégie mixte), donc cette stratégie est bien une +meilleure réponse possible contre elle-même, et on a bien affaire à un +équilibre de Nash. + +Pour résumer : tous les équilibres de Nash sont décrits de la façon +suivante : pour une certaine partie non vide $I$ de +$\{X_1,\ldots,X_N\}$, on pose +\[ +\left\{ +\begin{array}{ll} +p_i = \frac{\textstyle 1/g_i}{\textstyle \sum_{X_j\in I}(1/g_j)}&\text{si $p_i\in I$}\\ +p_i = 0&\text{sinon} +\end{array} +\right. +\] +et les deux joueurs jouent $p_1 X_1 + \cdots + p_N X_N$ : ceci est +bien un équilibre de Nash et tous sont de cette forme (et $I$ est bien +déterminé par l'équilibre puisque c'est le support commun des +stratégies des deux joueurs, donc tous les équilibres qu'on vient de +décrire sont distincts). Il y en a donc exactement $2^N - 1$. +\end{corrige} + + +% +% +% + +\exercice + +On considère un jeu de la forme suivante. Soit $A \subseteq +\mathbb{R}$ un ensemble de réels, soit $X \subseteq \mathbb{R}$ un +ensemble \emph{fini} de réels, et soit enfin $b>1$ un réel. (Toutes +ces données sont fixées à l'avance et sont des paramètres définissant +le jeu. Ils sont supposés connus des deux joueurs.) + +Chaque joueur quand vient son tour choisit un élément $x_i \in X$ : +plus exactement, Alice choisit $x_0$, puis Bob choisit $x_1$, puis +Alice choisit $x_2$, et ainsi de suite. Il n'y a aucune contrainte +sur le choix du $x_i$ et chacun a connaissance de tous les coups +antérieurs. + +Au bout d'un nombre infini de tours, on considère le réel +\[ +u = x_0 + \frac{x_1}{b} + \frac{x_2}{b^2} + \frac{x_3}{b^3} + \cdots +\] +c'est-à-dire la somme de la série +$\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. Cette série converge car elle +converge absolument\footnote{\label{footnote-series-converges}Preuve : +$\sum_{i=0}^{+\infty}\left|\frac{x_i}{b^i}\right| \leq +\sum_{i=0}^{+\infty}\frac{M}{b^i} = \frac{M}{1-b}$ où $M$ est un +majorant des $|x|$ pour $x\in X$, qui existe car $X$ est fini.}. Si +$u\in A$ alors Alice a gagné ; sinon, Bob a gagné. + +(Un cas particulier qu'on peut garder à l'esprit est celui où $X = +\{0,1\}$ et $b = 2$, auquel cas Alice et Bob construisent un nombre +binaire entre $0$ et $2$ en choisissant alternativement ses chiffres : +$u = x_0.x_1 x_2 x_3\cdots$ en binaire.) + +On cherche à montrer que sous certaines conditions sur $A$, l'un des +joueurs a une stratégie gagnante. + +\textbf{(1)} On considère l'application $\psi\colon X^{\mathbb{N}} \to +\mathbb{R}$ qui à une suite $\dblunderline{x} = (x_i)_{i\in\mathbb{N}} +\in X^{\mathbb{N}}$ associe $\sum_{i=0}^{+\infty}\frac{x_i}{b^i}$. +Montrer que si $\psi(\dblunderline{x}) = u$ et $\varepsilon > 0$, +alors il existe $\ell \in \mathbb{N}$ tel que toute suite +$\dblunderline{y}$ commençant par $x_0,\ldots,x_{\ell-1}$ vérifie +$|\psi(\dblunderline{y})-u| < \varepsilon$. Autrement dit, il existe +$\ell$ tel que l'image du $\ell$-ième voisinage +fondamental\footnote{Rappel : $V_\ell(\dblunderline{x})$ est +l'ensemble des suites commençant par les $\ell$ termes +$x_0,\ldots,x_{\ell-1}$.} $V_\ell(\dblunderline{x})$ de +$\dblunderline{x}$ par $\psi$ soit incluse dans la boule ouverte +$B_\varepsilon(u) := +\mathopen]u-\varepsilon,u+\varepsilon\mathclose[$. + (\emph{Indication :} s'inspirer de la + note \ref{footnote-series-converges}.) + +\begin{corrige} +Si $\dblunderline{x}$ et $\dblunderline{y}$ coïncident sur les +termes $i<\ell$, alors $|\psi(\dblunderline{y})-u| = +|\psi(\dblunderline{y})-\dblunderline{x}| = +\left|\sum_{i=\ell}^{+\infty} \frac{x_i}{b^i}\right| \leq +\sum_{i=\ell}^{+\infty} \left|\frac{x_i}{b^i}\right| \leq +\sum_{i=\ell}^{+\infty} \frac{M}{b^i} = \frac{Mb^\ell}{1-b}$. Cette +quantité tend vers $0$ quand $\ell\to+\infty$, donc il existe $\ell$ +tel qu'elle soit $<\varepsilon$. Ceci montre bien que si +$\dblunderline{y} \in V_\ell(\dblunderline{x})$ on a +$|\psi(\dblunderline{y})-u| < \varepsilon$. +\end{corrige} + +\textbf{(2)} En déduire que si $U \subseteq \mathbb{R}$ est ouvert (au +sens de la topologie usuelle des réels\footnote{Rappel : $U \subseteq +\mathbb{R}$ est ouvert lorsque pour tout $u\in U$ il existe +$\varepsilon>0$ tel que $B_\varepsilon(u) \subseteq U$.}), alors +l'image réciproque $\psi^{-1}(U) \subseteq X^{\mathbb{N}}$ est ouverte +(au sens de la topologie produit de la topologie discrète sur +$X^{\mathbb{N}}$, qu'on a considérée en cours). + +\begin{corrige} +Supposons que $U$ soit ouvert. Si $\dblunderline{x} \in +\psi^{-1}(U)$, c'est-à-dire $\psi(\dblunderline{x}) =: u \in U$, comme +$U$ est ouvert, il existe $\varepsilon>0$ tel que $B_\varepsilon(u) +\subseteq U$, et d'après la question (1), il existe $\ell$ tel que +$\psi(V_\ell(\dblunderline{x})) \subseteq B_\varepsilon(u) \subseteq +U$, ce qui signifie $V_\ell(\dblunderline{x}) \subseteq \psi^{-1}(U)$. +On vient de montrer que tout $\dblunderline{x} \in \psi^{-1}(U)$ a un +voisinage fondamental $V_\ell(\dblunderline{x})$ inclus dans +$\psi^{-1}(U)$, c'est-à-dire que $\psi^{-1}(U)$ est ouvert. + +(Note : on a évité dans ce corrigé d'utiliser le mot « continu » car +il n'a pas été défini en cours dans le contexte d'une application de +$X^{\mathbb{N}}$ vers $\mathbb{R}$. Mais bien sûr, il est correct de +dire que $\psi$ est continue en tant qu'application entre espaces +topologiques.) +\end{corrige} + +\textbf{(3)} En déduire que si $A$ est ouvert, ou bien fermé, +dans $\mathbb{R}$, alors l'un des deux joueurs possède une stratégie +gagnante au jeu qu'on a décrit. + +\begin{corrige} +Le jeu qu'on a décrit est exactement le jeu de Gale-Stewart défini par +la partie $\psi^{-1}(A)$. Si $A$ est ouvert, alors la question (2) +montre que $\psi^{-1}(A)$ est ouvert, donc le jeu est déterminé +d'après le théorème de détermination des jeux ouverts. Si $A$ est +fermé, alors son complémentaire $\mathbb{R}\setminus A$ est ouvert, +donc la question (2) montre que $\psi^{-1}(\mathbb{R}\setminus A) = +X^{\mathbb{N}} \setminus \psi^{-1}(A)$ est ouvert, c'est-à-dire que +$\psi^{-1}(A)$ est fermé, donc le jeu est déterminé d'après le +théorème de détermination des jeux fermés. +\end{corrige} + +\textbf{(4)} Montrer aussi ce résultat lorsque $A = \mathbb{Q}$ +(autrement dit, Alice gagne si la somme $u$ de la série est +rationnelle\footnote{Merci d'avance de ne pas prétendre que +$\mathbb{Q}$ est ouvert, ni qu'il est fermé.}). Plus généralement, +montrer ce résultat lorsque $A$ est borélien. + +\begin{corrige} +L'ensemble $\mathbb{Q}$ est la réunion dénombrable des fermés $\{r\}$ +pour $r\in\mathbb{Q}$ : il est donc borélien (dans $\mathbb{R}$) ; +l'image réciproque $\psi^{-1}(\mathbb{Q})$ est donc la réunion +dénombrable des fermés $\psi^{-1}(\{r\})$ : il est donc borélien (dans +$X^{\mathbb{N}}$). D'après le théorème de détermination des jeux +boréliens, le jeu est déterminé. + +Plus généralement, l'ensemble des $B$ tels que $\psi^{-1}(B)$ soit +borélien dans $X^{\mathbb{N}}$ est une tribu (puisque $\psi^{-1}$ +préserve les réunions et intersections quelconques, ainsi que le +complémentaire) et elle contient les ouverts (puisqu'on a vu que +$\psi^{-1}(U)$ est ouvert pour $U$ ouvert). Elle contient donc les +boréliens de $\mathbb{R}$. C'est-à-dire que si $B$ est borélien +dans $\mathbb{R}$ alors $\psi^{-1}(B)$ est borélien dans +$X^{\mathbb{N}}$. D'après le théorème de détermination des jeux +boréliens, le jeu est déterminé dès que $A$ est borélien. +\end{corrige} + + +% +% +% + +\exercice + +On va développer dans cet exercice un algorithme pour calculer la +somme et le produit d'ordinaux écrits en forme normale de Cantor +(itérée). + +\textbf{(1)} On rappelle que $1 + \omega = \omega$. En déduire que si +un ordinal $\alpha$ vérifie $\alpha \geq \omega$, alors on a $1 + +\alpha = \alpha$ (\emph{indication :} justifier qu'on peut écrire +$\alpha = \omega + \beta$). En déduire que $1 + \omega^\gamma = +\omega^\gamma$ lorsque $\gamma > 0$, puis que $\omega^{\gamma_1} + +\omega^{\gamma_2} = \omega^{\gamma_2}$ lorsque $\gamma_1 < \gamma_2$, +et enfin que $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} n_2 = +\omega^{\gamma_2} n_2$ si $n_1,n_2$ sont deux entiers naturels non +nuls (et toujours avec $\gamma_1 < \gamma_2$). + +\begin{corrige} +On a vu que lorsque $\alpha_0 \leq \alpha$, il existe un unique +$\beta$ tel que $\alpha = \alpha_0 + \beta$ : en particulier, si +$\alpha \geq \omega$, on peut écrire $\alpha = \omega + \beta$, et on +en déduit que $1 + \alpha = 1 + \omega + \beta = \omega + \beta = +\alpha$. + +Or si $\gamma > 0$, c'est-à-dire $\gamma \geq 1$, on a $\omega^\gamma +\geq \omega$, et on vient de voir que ceci implique $1 + \omega^\gamma += \omega^\gamma$. + +Si $\gamma_1 < \gamma_2$, on peut écrire $\gamma_2 = \gamma_1 + +\gamma$ (cf. deux paragraphes plus haut), donc $\omega^{\gamma_1} + +\omega^{\gamma_2} = \omega^{\gamma_1} + \omega^{\gamma_1 + \gamma} = +\omega^{\gamma_1} + \omega^{\gamma_1} \, \omega^{\gamma} = +\omega^{\gamma_1} (1 + \omega^\gamma) = \omega^{\gamma_1} \, +\omega^\gamma = \omega^{\gamma_1+\gamma} = \omega^{\gamma_2}$. + +Une fois acquis que $\omega^{\gamma_1} + \omega^{\gamma_2} = +\omega^{\gamma_2}$, on a $\omega^{\gamma_1} n_1 + \omega^{\gamma_2} +n_2 = \omega^{\gamma_1} + \cdots + \omega^{\gamma_1} + +\omega^{\gamma_2} + \cdots + \omega^{\gamma_2}$ (avec $n_1$ termes +$\omega^{\gamma_1}$ et $n_2$ termes $\omega^{\gamma_2}$), et en +utilisant de façon répétée l'égalité qu'on vient de dire, ceci vaut +$\omega^{\gamma_2} + \cdots + \omega^{\gamma_2} = \omega^{\gamma_2} +n_2$, comme annoncé. +\end{corrige} + +\textbf{(2)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1$ (avec $\gamma_s > \cdots > \gamma_1$ et +$n_1,\ldots,n_s$ des entiers naturels non nuls) et $\alpha' = +\omega^{\gamma'_{s'}} n'_{s'} + \cdots + \omega^{\gamma'_1} n'_1$ +(idem) sont deux ordinaux écrits en forme normale de Cantor, en +utilisant les résultats de la question précédente, expliquer comment +calculer $\alpha + \alpha'$, en supposant qu'on sache +algorithmiquement comparer les $\gamma_i$ et les $\gamma'_j$. + +\begin{corrige} +On écrit $\alpha + \alpha' = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1 + \omega^{\gamma'_{s'}} n'_{s'} + \cdots + +\omega^{\gamma'_1} n'_1$ et, d'après ce qu'on vient de voir, dès que +deux termes ne sont pas dans le bon ordre (i.e., si un +$\omega^{\gamma_i} n_i$ précède $\omega^{\gamma_j} n_j$ avec $\gamma_i +< \gamma_j$), alors le premier disparaît purement et simplement ; et +bien sûr, si $\gamma_i = \gamma_j$, les termes fusionnent en +$\omega^{\gamma_i} (n_i+n_j)$ par distributivité à droite. On se +retrouve donc avec l'écriture en forme normale de Cantor de $\alpha + +\alpha'$. +\end{corrige} + +\textbf{(3)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot +3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha + +\alpha'$ et $\alpha' + \alpha$. + +\begin{corrige} +Dans le sens $\alpha + \alpha'$, on a $(\omega^3\cdot 2 + \omega\cdot +3 + 5) + (\omega^2 + \omega\cdot 4) = \omega^3\cdot 2 + \omega^2 + +\omega\cdot 4$. + +Dans le sens $\alpha' + \alpha$, on a $(\omega^2 + \omega\cdot 4) + +(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^3\cdot 2 + \omega\cdot +3 + 5$. +\end{corrige} + +\textbf{(4)} Déduire de la question (2) que si $\alpha = +\omega^{\gamma_s} n_s + \cdots + \omega^{\gamma_1} n_1$ en forme +normale de Cantor et $k \geq 1$ est un entier naturel, alors +$\alpha\cdot k = \omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} +n_{s-1} + \cdots + \omega^{\gamma_1} n_1$ (c'est-à-dire que seul le +coefficient $n_s$ de la plus haute puissance de $\omega$ est multiplié +par $k$ ; \emph{indication} : on a $\alpha\cdot k = \alpha + \cdots + +\alpha$ avec $k$ termes identiques). + +\begin{corrige} +En écrivant $\alpha\cdot k = \alpha + \cdots + \alpha$ (qui résulte de +la distributivité à droite) et en appliquant les règles expliquées +en (2), on voit que tous les termes autres que le plus haut de tous +les termes autres que le dernier de la terme disparaissent purement et +simplement (ils sont absorbés par le terme le plus haut du $\alpha$ +suivant), donc seul subsistent $k-1$ copies de $\omega^{\gamma_s} n_s$ +plus le dernier $\alpha$, ce qui donne bien $\alpha\cdot k = +\omega^{\gamma_s} n_sk + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + +\omega^{\gamma_1} n_1$ comme annoncé. +\end{corrige} + +\textbf{(5)} En déduire que, toujours pour $\alpha = \omega^{\gamma_s} +n_s + \cdots + \omega^{\gamma_1} n_1$, on a $\alpha\cdot\omega = +\omega^{\gamma_s+1}$ (\emph{indication} : on pourra calculer +$\lim_{k\to\omega} \alpha \cdot k$), et plus généralement $\alpha\cdot +\omega^{\gamma'} = \omega^{\gamma_s+\gamma'}$ si $\gamma'\geq 1$ +(\emph{indication} : on pourra écrire $\gamma' = 1+\gamma''$). + +\begin{corrige} +On cherche à calculer $\alpha\cdot\omega = \lim_{k\to\omega} \alpha \cdot +k$ (rappelons que cette limite est juste une borne supérieure). Par +comparaison des formes normales de Cantor, $\omega^{\gamma_s+1}$ est +plus grand que tous les $\alpha\cdot k = \omega^{\gamma_s} n_sk + +\omega^{\gamma_{s-1}} n_{s-1} + \cdots + \omega^{\gamma_1} n_1$, donc +$\omega^{\gamma_s+1} \geq \lim_{k\to\omega} \alpha \cdot k$. Mais +inversement, la forme normale de Cantor de tout ordinal +$<\omega^{\gamma_s+1}$ commence par un terme $\leq\omega^{\gamma_s} +N$, donc majoré par $\alpha\cdot k$ pour $k$ assez grand (certainement +pour $k\geq N$) : donc $\lim_{k\to\omega} \alpha \cdot k$ ne peut pas +être $<\omega^{\gamma_s+1}$. Donc c'est exactement +$\omega^{\gamma_s+1}$, et on a prouvé $\alpha\cdot\omega = +\omega^{\gamma_s+1}$. + +Plus généralement, si $\gamma'\geq 1$, on peut écrire $\gamma' = +1+\gamma''$ comme on l'a déjà rappelé plus haut, et +$\alpha\cdot\omega^{\gamma'} = \alpha\cdot\omega^{1+\gamma''} = +\alpha\cdot\omega\omega^{\gamma''} = +\omega^{\gamma_s+1}\omega^{\gamma''} = \omega^{\gamma_s+1+\gamma''} = +\omega^{\gamma_s+\gamma'}$. +\end{corrige} + +\textbf{(6)} Si $\alpha = \omega^{\gamma_s} n_s + \cdots + +\omega^{\gamma_1} n_1$ et $\alpha' = \omega^{\gamma'_{s'}} n'_{s'} + +\cdots + \omega^{\gamma'_1} n'_1$ sont deux ordinaux écrits en forme +normale de Cantor, en utilisant les résultats de la question +précédente, expliquer comment calculer $\alpha \cdot \alpha'$, en +supposant qu'on sache algorithmiquement comparer et ajouter les +$\gamma_i$ et les $\gamma'_j$. + +\begin{corrige} +Par distributivité à droite et comme on sait déjà calculer des sommes, +on peut se ramener au cas où $\alpha'$ est un seul terme +$\omega^{\gamma'} n'$. Par associativité, il suffit de savoir +calculer le produit par $\omega^{\gamma'}$ à droite, et par $n'$. Le +produit par $\omega^{\gamma'}$ est trivial si $\gamma'=0$ et est réglé +par la question (5) si $\gamma'>0$. Et le produit par $n'$ est réglé +par la question (4). + +Un peu plus concrètement, pour chaque terme de $\alpha'$ pour lequel +$\gamma'_j > 0$, on a $\alpha\cdot \omega^{\gamma'_j} n'_j = +\omega^{\gamma_s + \gamma'_j} n_s n_j$, et le terme fini, s'il existe +(c'est-à-dire si $\gamma'_1 = 0$) vaut $\alpha\cdot n'_1 = +\omega^{\gamma_s} n_s n'_1 + \omega^{\gamma_{s-1}} n_{s-1} + \cdots + +\omega^{\gamma_1} n_1$. Il n'y a plus qu'à ajouter tous ces termes +dans l'ordre (qui est déjà le bon, et qui donne déjà une forme normale +de Cantor, puisque $\gamma_s + \gamma'_s > \cdots + \gamma_s + +\gamma'_2 > \gamma_s > \cdots > \gamma_1$). +\end{corrige} + +\textbf{(7)} Application : si $\alpha = \omega^3\cdot 2 + \omega\cdot +3 + 5$ et $\alpha' = \omega^2 + \omega\cdot 4$, calculer $\alpha \cdot +\alpha'$ et $\alpha' \cdot \alpha$. + +\begin{corrige} +Dans le sens $\alpha\alpha'$ on trouve $(\omega^3\cdot 2 + \omega\cdot +3 + 5) (\omega^2 + \omega\cdot 4) = \omega^5 + \omega^4\cdot 4$ (il +n'y a pas de terme fini à la fin de $\alpha'$ donc seul le premier +terme de $\alpha$ survit). + +Dans le sens $\alpha'\alpha$ on trouve $(\omega^2 + \omega\cdot 4) +(\omega^3\cdot 2 + \omega\cdot 3 + 5) = \omega^5\cdot 2 + +\omega^3\cdot 3 + \omega^2\cdot 5 + \omega\cdot 4$. +\end{corrige} + + + +% +% +% +\end{document} diff --git a/notes-mitro206.tex b/notes-mitro206.tex index fb055b0..d5fb37f 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1022,7 +1022,9 @@ surréels de Conway. \section{Jeux en forme normale}\label{section-games-in-normal-form} -\setcounter{comcnt}{0} +\setcounter{subsection}{-1} + +\subsection{Rappels sur les convexes} \thingy Pour cette section, on rappelle les définitions suivants : une \index{affine (combinaison)|see{combinaison affine}}\defin{combinaison @@ -1035,9 +1037,19 @@ $\lambda_1,\ldots,\lambda_m$ vérifient $\sum_{i=1}^m \lambda_i = 1$ forme $\frac{\sum_{i=1}^m \lambda_i x_i}{\sum_{i=1}^m \lambda_i}$ où $\lambda_1,\ldots,\lambda_m$ vérifient $\sum_{i=1}^m \lambda_i \neq 0$ : on parle alors de \defin{barycentre} de $x_1,\ldots,x_m$ affecté -des coefficients $\lambda_1,\ldots,\lambda_m$). - -Une \index{convexe (combinaison)|see{combinaison +des poids $\lambda_1,\ldots,\lambda_m$). + +Lorsque $x_1,\ldots,x_m$ sont tels que la combinaison affine est +déterminée par ses coefficients, autrement dit lorsque l'application +$(\lambda_1,\ldots,\lambda_m) \mapsto \sum_{i=1}^m \lambda_i x_i$ +définie sur l'ensemble des $(\lambda_1,\ldots,\lambda_m)$ tels que +$\sum_{i=1}^m \lambda_i = 1$, est injective, on dit que +$x_1,\ldots,x_m$ sont \index{affinement indépendants + (points)}\defin{affinement indépendants} (ou affinement libres). Il +revient au même de dire que $x_2-x_1,\ldots,x_m-x_1$ sont linéairement +indépendants. + +\thingy Une \index{convexe (combinaison)|see{combinaison convexe}}\defin{combinaison convexe} est une combinaison affine $\sum_{i=1}^m \lambda_i x_i$ où $\lambda_1,\ldots,\lambda_m$ sont \emph{positifs} ($\lambda_1,\ldots,\lambda_m \geq 0$) et vérifient @@ -1048,16 +1060,88 @@ Un \defin{convexe} de $\mathbb{R}^m$ est une partie stable par combinaisons convexes (c'est-à-dire que $C$ est dit convexe lorsque si $x_1,\ldots,x_m \in C$ et $\lambda_1,\ldots\lambda_m\geq 0$ vérifient $\sum_{i=1}^m \lambda_i = 1$ alors $\sum_{i=1}^m \lambda_i x_i \in -C$). - -Une \index{affine (application)}\textbf{application affine} $u\colon -\mathbb{R}^p \to \mathbb{R}^q$ est une fonction qui préserve les -combinaisons affines (autrement dit, si $\sum_{i=1}^m \lambda_i = 1$ -alors $u\Big(\sum_{i=1}^m \lambda_i x_i\Big) = \sum_{i=1}^m \lambda_i -u(x_i)$). Il revient au même de dire que $u$ est la somme d'une -constante (dans $\mathbb{R}^q$) et d'une application linéaire +C$). Par associativité du barycentre, il revient au même d'imposer +cette condition pour $m=2$, c'est-à-dire que $C \subseteq +\mathbb{R}^m$ est convexe ssi on a $[x,y] \subseteq C$ pour tous +$x,y\in C$, où $[x,y] := \{\lambda x + (1-\lambda) y : \lambda \in +[0;1]\}$. + +Une intersection quelconque de convexes étant manifestement un +convexe, on peut parler du plus petit convexe contenant une partie $A +\subseteq \mathbb{R}^m$, appelé \index{convexe + (enveloppe)|see{enveloppe convexe}}\defin{enveloppe convexe} +de $A$ : il s'agit simplement de l'ensemble de toutes les combinaisons +convexes des points de $A$ (i.e., des ensembles \emph{finis} de points +de $A$). L'enveloppe convexe d'une partie finie s'appelle un +\defin{polytope} (convexe). L'enveloppe convexe d'une partie $A$ +affinement libre et finie\footnote{Une partie affinement libre de + $\mathbb{R}^m$ a au plus $m+1$ points, donc le mot « fini » est + redondant dans ce cadre, mais la définition peut s'étendre en + dimension infinie auquel cas il n'est plus inutile.} s'appelle +\defin{simplexe} de sommets $A$. + +\thingy Une \index{affine (application)}\textbf{application affine} +$u\colon \mathbb{R}^p \to \mathbb{R}^q$ est une fonction qui préserve +les combinaisons affines (autrement dit, si $\sum_{i=1}^m \lambda_i = +1$ alors $u\Big(\sum_{i=1}^m \lambda_i x_i\Big) = \sum_{i=1}^m +\lambda_i\, u(x_i)$). Il revient au même de dire que $u$ est la somme +d'une constante (dans $\mathbb{R}^q$) et d'une application linéaire $\mathbb{R}^p \to \mathbb{R}^q$. +On aura fréquemment besoin du fait évident suivant : +\begin{prop}\label{affine-functions-take-extrema-at-boundary} +Soit $A \subseteq \mathbb{R}^m$ un ensemble fini et $C$ son enveloppe +convexe, et soit $u \colon \mathbb{R}^m \to \mathbb{R}$ une +application affine. Alors $u(a) \leq M$ pour tout $a \in A$ implique +$u(s) \leq M$ pour tout $s \in C$. Ou, si on préfère, $\max\{u(s) : +s\in C\}$ existe et vaut $\max\{u(a) : a\in A\}$ (et la même +affirmation en remplaçant $\max$ par $\min$ vaut aussi). +\end{prop} + +En français : « une fonction affine sur un polytope atteint ses bornes +sur un sommet de ce dernier ». + +\begin{proof} +Tout point $s$ de $C$ est combinaison convexe de points de $A$, +c'est-à-dire $s = \sum_{i=1}^n \lambda_i x_i$ avec $x_i \in A$ et +$\lambda_i \geq 0$ vérifiant $\sum_{i=1}^n \lambda_i = 1$. Comme $u$ +est affine, on a alors $u(s) = \sum_{i=1}^n \lambda_i\, u(x_i)$. Si +$u(a) \leq M$ pour tout $a\in A$, ceci implique $u(s) \leq +\sum_{i=1}^n \lambda_i\, M = M$, comme annoncé. + +Pour en déduire l'affirmation sur le $\max$, il suffit d'appliquer ce +qu'on vient de démontrer pour $M = \max\{u(a) : a\in A\}$ (qui existe +puisque $A$ est fini) : on a $u(s) \leq M$ pour tout $s \in C$, et +comme les éléments de $A$ sont dans $C$, ceci montre bien $\max\{u(s) +: s\in C\} = \max\{u(a) : a\in A\}$. +\end{proof} + +\begin{prop}\label{affine-functions-take-no-strict-extrema-inside} +Reprenant le contexte de la proposition précédente ($A \subseteq +\mathbb{R}^m$ un ensemble fini, $C$ son enveloppe convexe, et $u +\colon \mathbb{R}^m \to \mathbb{R}$ affine), soit $M := \max_{a \in A} +u$ (dont on vient de voir que c'est aussi $\max_{s\in C} u$) : alors +une combinaison convexe $s$ à coefficients \emph{strictement positifs} +de points de $A$ (i.e., $s = \sum_{i=1}^n \lambda_i x_i$ avec $x_i \in +A$ et $\lambda_i > 0$ vérifiant $\sum_{i=1}^n \lambda_i = 1$) vérifie +$u(s) = M$, si et seulement si chacun des points en question vérifie +aussi cette propriété (i.e., on a $u(x_i) = M$ pour tout $i$). +\end{prop} + +\begin{proof} +On vient de voir que $u(x_i) \leq M$ pour tout $i$ implique $u(s) \leq +M$. Si on a $u(x_j) < M$ pour un certain $j$, alors on a $\lambda_j\, +u(x_j) < \lambda_j\, M$, donc en sommant avec les autres $\lambda_i\, +u(x_i) \leq \lambda_i M$ on trouve $u(s) = \sum_{i=1}^n \lambda_i\, +u(x_i) < \sum_{i=1}^n \lambda_i\, M = M$. Réciproquement, si $u(x_i) += M$ pour tout $i$, il est évident que $u(s) = M$. +\end{proof} + +On peut aussi reformuler ce résultat en affirmant que la partie de $C$ +où $u$ prend sa valeur maximale $M$ est l'enveloppe convexe de la +partie de $A$ où elle prend cette valeur. + + \subsection{Généralités} \begin{defn}\label{definition-game-in-normal-form} @@ -1086,36 +1170,51 @@ fait que les joueurs peuvent également jouer de façon probabiliste, ce qui amène à introduire la notion de stratégie mixte : \begin{defn}\label{definition-mixed-strategy-abst} -Donné un ensemble $B$ fini d'« options », on appelle \index{mixte (stratégie)}\defin{stratégie - mixte} sur $B$ une fonction $s\colon B\to\mathbb{R}$ telle que -$s(b)\geq 0$ pour tout $b\in B$ et $\sum_{b\in B} s(b) = 1$ : -autrement dit, il s'agit d'une distribution de probabilités sur $B$. - -Le \defin[support (d'une stratégie mixte)]{support} de $s$ est l'ensemble des options $b\in B$ pour -lesquelles $s(b) > 0$. - -Parfois, on préférera considérer la stratégie comme la combinaison -formelle $\sum_{b\in B} s(b)\cdot b$ (« formelle » signifiant que le -produit $t\cdot b$ utilisé ici n'a pas de sens intrinsèque : il est -défini par son écriture ; l'écriture $\sum_{b\in B} s(b)\cdot b$ est -donc une simple notation pour $s$). Autrement dit, ceci correspond à -voir une stratégie mixte comme une combinaison convexe d'éléments -de $B$, i.e., un point du simplexe affine dont les sommets sont les -éléments de $B$. En particulier, un élément $b$ de $B$ (stratégie -pure) sera identifié à l'élément de $S_B$ qui affecte le poids $1$ -à $b$ et $0$ à tout autre élément. +Donné un ensemble $B$ fini d'« options », on appelle \index{mixte + (stratégie)}\defin{stratégie mixte} sur $B$ une fonction $s\colon +B\to\mathbb{R}$ telle que $s(b)\geq 0$ pour tout $b\in B$ et +$\sum_{b\in B} s(b) = 1$ : autrement dit, il s'agit d'une distribution +de probabilités sur $B$. + +Le \defin[support (d'une stratégie mixte)]{support} de $s$ est +l'ensemble des options $b\in B$ pour lesquelles $s(b) > 0$. +\end{defn} + +On identifiera un élément $b$ de $B$ à la fonction (stratégie pure) +$\delta_b \colon B\to\mathbb{R}$ qui prend la valeur $1$ en $b$ et $0$ +ailleurs (distribution de probabilités de Dirac en $b$). Ceci permet +de considérer $B$ comme une partie de l'ensemble $S_B$ des stratégies +mixtes, et d'identifier une stratégie mixte $s\colon B\to\mathbb{R}$ +quelconque sur $B$ à la combinaison convexe $\sum_{b\in B} s(b)\cdot +b$ des stratégies pures : i.e., on peut considérer les stratégies +mixtes comme des combinaison convexes formelles\footnote{Le mot + « formel » signifie ici que la combinaison n'a pas d'autre sens que + comme l'expression par laquelle elle est définie, par exemple + $\frac{1}{3}\text{Pierre} + \frac{1}{3}\text{Papier} + + \frac{1}{3}\text{Ciseaux}$ est une combinaison convexe formelle de + $\{\text{Pierre}, \text{Papier}, \text{Ciseaux}\}$ représentant la + probabilité uniforme sur cet ensemble.} des éléments de $B$. + +On passera indifféremment entre ces trois points de vue sur les +stratégies mixtes : fonctions $s\colon B\to\mathbb{R}$ (positives de +somme $1$), mesures de probabilités sur $B$, ou bien combinaisons +convexes formelles d'éléments de $B$. En tout état de cause, l'ensemble $S_B$ des stratégies mixtes sur $B$ -sera vu (notamment comme espace topologique) comme le fermé de -$\mathbb{R}^B$ défini par l'intersection des demi-espaces de -coordonnées positives et de l'hyperplan défini par la somme des -coordonnées égale à $1$. -\end{defn} +sera vu comme la partie de $\mathbb{R}^B$ définie par l'intersection +des demi-espaces de coordonnées positives et de l'hyperplan défini par +la somme des coordonnées égale à $1$ : il s'agit d'un \emph{convexe + fermé}, qui est l'enveloppe convexe des points de $B$ identifiés +ainsi qu'on vient de le dire aux $\delta_b = +(0,\ldots,0,1,0,\ldots,0)$, c'est-à-dire que $S_B$ est le +\defin{simplexe} d'ensemble de sommets $B$ (identifié à l'ensemble +des $\delta_b$). \begin{defn}\label{definition-mixed-strategy-game} Pour un jeu comme défini en \ref{definition-game-in-normal-form}, une stratégie mixte pour le joueur $i$ est donc une fonction $s\colon A_i -\to\mathbb{R}$ comme on vient de le dire. On notera parfois $S_i$ +\to\mathbb{R}$ comme on vient de le dire +en \ref{definition-mixed-strategy-abst}. On notera parfois $S_i$ l'ensemble des stratégies mixtes du joueur $i$. Un \defin{profil de stratégies mixtes} est un élément du produit cartésien $S := S_1 \times \cdots \times S_N$. @@ -1131,55 +1230,86 @@ parler de profil de stratégies pures. \end{defn} \thingy\label{remark-mixed-stragy-profile-versus-correlated-profile} -Il va de soi qu'un profil de stratégies mixtes, i.e., un -élément de $S := S_1 \times \cdots \times S_N$, i.e., la donnée d'une -distribution de probabilité sur chaque $A_i$, n'est pas la même chose -qu'une distribution de probabilités sur $A := A_1 \times \cdots \times -A_N$. Néanmoins, on peut voir les profils de stratégies mixtes comme -des distributions particulières sur $A$, à savoir celles pour -lesquelles les marginales (i.e., les projections sur un des $A_i$) -sont indépendantes. Concrètement, ceci signifie que donné -$(s_1,\ldots,s_N) \in S$, on en déduit un $s\colon A\to\mathbb{R}$, -aussi une distribution de probabilité, par la définition suivante : -$s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ (produit des -$s_i(a_i)$). On identifiera parfois abusivement l'élément -$(s_1,\ldots,s_N) \in S$ à la distribution $s\colon A\to\mathbb{R}$ -qu'on vient de décrire (ce n'est pas un problème car $s_i$ se déduit -de $s$ : précisément, $s_i(b) = \sum_{a\,:\, a_i = b} s(a)$ où la somme -est prise sur les $a \in A$ tels que $a_i = b$). - -\danger (Il faudra prendre garde au fait qu'on peut voir $S$ soit -comme une partie $S_1\times\cdots\times S_N$ de +Il va de soi qu'un profil de stratégies mixtes, i.e., un élément de $S +:= S_1 \times \cdots \times S_N$, i.e., la donnée d'une distribution +de probabilité sur chaque $A_i$, \emph{n'est pas la même chose} qu'une +distribution de probabilités sur $A := A_1 \times \cdots \times A_N$. + +Néanmoins, si $(s_1,\ldots,s_N) \in S$, on définit une distribution de +probabilités $s\colon A\to\mathbb{R}$ (un élément de $S_A$, si on +veut) de la façon suivante : +\[ +s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N) +\tag{$*$} +\] +(produit des $s_i(a_i)$). + +Probabilistiquement, cette formule revient à dire qu'on tire un +élément $a_i$ de $A_i$ selon la distribution $s_i$ \emph{de façon + indépendante} pour chaque $i$ de manière à former un $N$-uplet +$(a_1,\ldots,a_N)$. La formule ($*$) servira donc à représenter +l'hypothèse que les joueurs ont accès à des sources de hasard qui sont +indépendantes (si Alice tire son coup à pile ou face et que Bob fait +de même, les pièces tirées par Alice et Bob sont des variables +aléatoires indépendantes). Les distributions de probabilités $s$ +sur $A$ définies par la formule ($*$) sont précisément celles dont +composantes sont indépendantes, et qui sont alors complètement +déterminées par leurs \emph{distributions + marginales}\footnote{\label{footnote-marginals}La $i$-ième + \defin{marginale} d'une variable aléatoire sur $A_1\times \cdots + \times A_N$ est simplement sa $i$-ième composante (= projection + sur $A_i$). La $i$-ième \textbf{distribution marginale} de la + distribution de probabilités $s \colon A \to \mathbb{R}$ est donc la + distribution de probabilités $s_i \colon A_i \to \mathbb{R}$ qui à + $b\in A_i$ associe la somme des $s(a_1,\ldots,a_N)$ prise sur tous + les $N$-uplets $(a_1,\ldots,a_N)$ tels que $a_i = + b$.} $s_1,\ldots,s_N$. + +On identifiera parfois abusivement l'élément $(s_1,\ldots,s_N) \in S$ +à la distribution $s\colon A\to\mathbb{R}$ qu'on vient de décrire (ce +n'est pas un problème car $s_i$ se déduit de $s$ : précisément, +$s_i(b) = \sum_{a\,:\, a_i = b} s(a)$ où la somme est prise sur les $a +\in A$ tels que $a_i = b$, cf. note \ref{footnote-marginals}). + +\danger Il faudra prendre garde au fait que, du coup, $S$ peut se voir +\emph{soit} comme la partie $S_1\times\cdots\times S_N$ de $\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$ formé des -$N$-uplets $(s_1,\ldots,s_N)$, soit comme la partie de $\mathbb{R}^A = -\mathbb{R}^{A_1\times\cdots\times A_N}$ formé des fonctions de la -forme $s\colon (a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ comme on -l'a expliqué au paragraphe précédent. Ces deux points de vue ont un -sens et ont parfois un intérêt, mais ils ne partagent pas les mêmes -propriétés. Par exemple, $S$ est convexe en tant que partie -$S_1\times\cdots\times S_N$ de $\mathbb{R}^{A_1}\times\cdots\times -\mathbb{R}^{A_N}$, mais pas en tant que partie de $\mathbb{R}^A$.) +$N$-uplets $(s_1,\ldots,s_N)$, \emph{soit} comme la partie de +$\mathbb{R}^A = \mathbb{R}^{A_1\times\cdots\times A_N}$ formé des +fonctions de la forme $s\colon (a_1,\ldots,a_N) \mapsto s_1(a_1)\cdots +s_N(a_N)$ comme on l'a expliqué aux paragraphes précédents. Ces deux +points de vue ont un sens et ont parfois un intérêt, mais ils ne +partagent pas les mêmes propriétés. Par exemple, $S$ est convexe en +tant que partie $S_1\times\cdots\times S_N$ de +$\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$, mais pas en +tant que partie de $\mathbb{R}^A$. Néanmoins, ce double point de vue +ne devrait pas causer de confusion. Ceci conduit à faire la définition suivante : -\begin{defn} +\begin{defn}\label{definition-mixed-strategy-gain} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on -appelle \defin[gain espéré]{gain [espéré]} du joueur $i$ selon ce profil la -quantité +appelle \defin[gain espéré]{gain [espéré]} du joueur $i$ selon ce +profil la quantité \[ u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a) \] -(ceci définit $u_i$ comme fonction de $S_1\times\cdots \times S_N$ -vers $\mathbb{R}$). +c'est-à-dire selon la distribution de probabilités définie par la +formule ($*$) +de \ref{remark-mixed-stragy-profile-versus-correlated-profile}. Ceci +étend $u_i$ en une function de $S := S_1\times\cdots \times S_N$ +vers $\mathbb{R}$, qu'on dénotera par le même symbole car il n'en +résultera pas de confusion. \end{defn} Selon l'approche qu'on veut avoir, on peut dire qu'on a défini $u_i(s)$ comme l'espérance de $u_i(a)$ si chaque $a_j$ est tiré indépendamment selon la distribution de probabilité $s_i$ ; ou bien qu'on a utilisé l'unique prolongement de $u_i$ au produit des -simplexes $S_i$ qui soit affine en chaque variable $s_i$. +simplexes $S_i$ qui soit affine en chaque variable $s_i$ +(« multi-affine »). @@ -1188,26 +1318,37 @@ simplexes $S_i$ qui soit affine en chaque variable $s_i$. \begin{defn}\label{definition-best-response-and-nash-equilibrium} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si -$s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_1 \times \cdots -\times S_{i-1} \times S_{i+1} \times \cdots \times S_N$ est un profil -de stratégies mixtes pour tous les joueurs autres que le joueur $i$, -on dit que la stratégie mixte $s_! \in S_i$ est une \defin{meilleure - réponse} (resp. la meilleure réponse \textbf{stricte}) contre $s_?$ -lorsque pour tout $t \in S_i$ on a $u_i(s_?,s_!) \geq u_i(s_?,t)$ -(resp. lorsque pour tout $t \in S_i$ différent de $s_!$ on a -$u_i(s_?,s_!) > u_i(s_?,t)$), où $(s_?,t)$ désigne l'élément de -$S_1\times \cdots \times S_N$ obtenu en insérant $t \in S_i$ comme -$i$-ième composante entre $s_{i-1}$ et $s_{i+1}$, c'est-à-dire le gain -[espéré] obtenu en jouant $t$ contre $s_?$. +$s_? := (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N) \in S_{?i} := S_1 +\times \cdots \times S_{i-1} \times S_{i+1} \times \cdots \times S_N$ +est un profil de stratégies mixtes pour tous les joueurs autres que le +joueur $i$, on dit que la stratégie mixte $s_! \in S_i$ est une +\defin{meilleure réponse} (resp. la meilleure réponse +\textbf{stricte}) contre $s_?$ lorsque pour tout $t \in S_i$ on a +$u_i(s_?,s_!) \geq u_i(s_?,t)$ (resp. lorsque pour tout $t \in S_i$ +différent de $s_!$ on a $u_i(s_?,s_!) > u_i(s_?,t)$), où $(s_?,t)$ +désigne l'élément de $S_1\times \cdots \times S_N$ obtenu en insérant +$t \in S_i$ comme $i$-ième composante entre $s_{i-1}$ et $s_{i+1}$, +c'est-à-dire le gain [espéré] obtenu en jouant $t$ contre $s_?$. Un profil de stratégies mixtes $s = (s_1,\ldots,s_N)$ (pour l'ensemble -des joueurs) est dit être un \index{Nash (équilibre de)}\defin{équilibre de Nash} (resp., un -équilibre de Nash \defin[strict (équilibre de Nash)]{strict}) lorsque pour tout $1\leq i \leq N$, -la stratégie $s_i$ pour le joueur $i$ est une meilleure réponse -(resp. la meilleure réponse stricte) contre le profil $s_{?i}$ pour -les autres joueurs obtenu en supprimant la composante $s_i$ de $s$. +des joueurs) est dit être un \index{Nash (équilibre + de)}\defin{équilibre de Nash} (resp., un équilibre de Nash +\defin[strict (équilibre de Nash)]{strict}) lorsque pour tout $1\leq i +\leq N$, la stratégie $s_i$ pour le joueur $i$ est une meilleure +réponse (resp. la meilleure réponse stricte) contre le profil $s_{?i} +:= (s_1,\ldots,s_{i-1},s_{i+1},\ldots,s_N)$ pour les autres joueurs +obtenu en supprimant la composante $s_i$ de $s$. \end{defn} +Concrètement, donc, un équilibre de Nash est donc un profil de +stratégies mixtes de l'ensemble des joueurs dans lequel \emph{aucun + joueur n'a intérêt à changer unilatéralement sa stratégie} (au sens +où faire un tel changement lui apporterait une espérance de gain +strictement supérieure). Un équilibre de Nash \emph{strict} +correspond à la situation où tout changement unilatéral de stratégie +d'un joueur lui apporterait une espérance de gain strictement +inférieure. + \begin{prop}\label{stupid-remark-best-mixed-strategies} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si @@ -1223,28 +1364,58 @@ En particulier, une meilleure réponse stricte est nécessairement une stratégie pure. \end{prop} \begin{proof} -Tout ceci résulte du fait que le gain espéré $u_i(s_?,t)$ est une -fonction affine de $t \in S_i$ (et une fonction affine sur un simplexe -prend son maximum — ou son minimum — sur un des sommets de ce -simplexe, et ne peut le prendre à l'intérieur que si elle prend aussi -cette valeur sur les sommets). - -Plus précisément : $u_i(s_?,t)$ (pour $t \in S_i$) est combinaison -convexe avec pour coefficients $t(a)$ pour $a\in A_i$, des -$u_i(s_?,a)$. Si $v$ est le maximum des $u_i(s_?,a)$ (qui sont en -nombre fini donc ce maximum existe), alors $v$ est aussi le maximum de -toute combinaison convexe $u_i(s_?,t)$ des $u_i(s_?,a)$ : c'est-à-dire -que $t\in S_i$ est une meilleure réponse possible contre $s_?$ si et -seulement si $u_i(s_?,t) = v$. En particulier, tout $a \in A_i$ qui -réalise ce maximum $v$ est une meilleure réponse possible -(contre $s_?$) qui est une stratégie pure. D'autre part, une -combinaison convexe $u_i(s_?,t)$ de valeurs $\leq v$ ne peut être -égale à $v$ que si toutes les valeurs $u_i(s_?,a)$ entrant -effectivement (c'est-à-dire avec un coefficient $>0$) dans la -combinaison sont égales à $v$ (s'il y en avait une $<v$, elle -entraînerait forcément une moyenne pondérée $<v$), et réciproquement. +Tout ceci résulte essentiellement des propositions +\ref{affine-functions-take-extrema-at-boundary} et \ref{affine-functions-take-no-strict-extrema-inside} : +le gain espéré $u_i(s_?,t)$ du joueur $i$ (une fois fixé le +profil $s_?$ de tous les autres joueurs) est une fonction affine de la +stratégie $t \in S_i$ du joueur $i$, et une fonction affine sur un +simplexe prend son maximum sur un sommet du simplexe, et ne peut la +prendre à l'intérieur d'une face (= enveloppe convexe d'un +sous-ensemble des sommets) que si elle la prend également en chaque +sommet de cette face. + +Plus précisément, soit $v = \max_{t \in S_i} u_i(s_?,t)$, dont la +proposition \ref{affine-functions-take-extrema-at-boundary} garantit +l'existence ; une meilleure réponse possible contre $s_?$ est +précisément un $t$ réalisant $u_i(s_?,t) = v$ : il résulte de la +proposition citée que $v$ est aussi $\max_{a \in A_i} u_i(s_?,a)$, +c'est-à-dire qu'il existe une stratégie \emph{pure} $a \in A_i$ qui +est une meilleure réponse possible contre $s_?$. Par ailleurs, si +$s_!$ est une meilleure réponse, i.e., $u_i(s_?,s_!) = v$, alors la +proposition \ref{affine-functions-take-no-strict-extrema-inside} +(appliquée avec pour $x_1,\ldots,x_n$ les points du support de $s_!$) +montre que chaque stratégie pure $a$ appartenant au support de $s_!$ +vérifie aussi $u_i(s_?,a) = v$. + +Comme une meilleure réponse stricte est unique, elle est forcément +pure d'après ce qu'on vient de voir. \end{proof} +\textbf{Reformulation.} Un profil de stratégies mixtes +$(s_1,\ldots,s_N) \in S_1\times \cdots\times S_N$ est un équilibre de +Nash si et seulement si, pour chaque $i$, +\begin{itemize} +\item pour tout $a$ dans le support de $s_i$, le gain espéré + $u_i(s_{?i},a)$ (rappelons que ceci est une notation pour + $u_i(s_1,\ldots,s_{i-1},a,s_{i+1},\ldots,s_N$) prend la \emph{même} + valeur, et +\item cette valeur est supérieure ou égale à $u_i(s_{?i},b)$ pour + tout $b\in A_i$. +\end{itemize} + +\smallskip + +On vient de voir que \emph{lorsque les stratégies de tous les autres + joueurs sont fixées} (à $s_?$ dans la proposition ci-dessus), le +joueur $i$ a une meilleure réponse en stratégie pure : on pourrait +être tenté d'en conclure, mais ce serait une erreur, que les +stratégies mixtes n'apportent donc rien à l'histoire, et qu'un +équilibre de Nash existe forcément en stratégies pures : \emph{ce + n'est pas le cas}. Néanmoins, les équilibres de Nash existent bien +en stratégies mixtes, et c'est le résultat central du domaine (ayant +essentiellement valu à son auteur le prix d'économie de la banque de +Suède à la mémoire d'Alfred Nobel en 1994) : + \begin{thm}[John Nash, 1951]\label{theorem-nash-equilibria} Pour un jeu en forme normale comme en \ref{definition-game-in-normal-form}, il existe un équilibre de @@ -1304,9 +1475,10 @@ mais elle peut donner l'impression qu'on commet une « erreur D'après la première expression donnée, il est clair qu'on a bien $s^\sharp_i \in S_i$, et qu'on a donc bien défini une fonction -$T\colon S\to S$. Cette fonction est continue, donc admet un point -fixe $s$ d'après \ref{brouwer-fixed-point-theorem} (notons qu'ici, $S$ -est vu comme le convexe $S_1\times\cdots\times S_N$ dans +$T\colon S\to S$. Cette fonction est continue (comme composée de +fonctions continues), donc admet un point fixe $s$ +d'après \ref{brouwer-fixed-point-theorem} (notons qu'ici, $S$ est vu +comme le convexe $S_1\times\cdots\times S_N$ dans $\mathbb{R}^{A_1}\times\cdots\times \mathbb{R}^{A_N}$). On va montrer que $s$ est un équilibre de Nash. @@ -1340,18 +1512,18 @@ Pour $N=2$, une méthode qui peut fonctionner dans des cas suffisamment petits consiste à énumérer tous les supports (cf. \ref{definition-mixed-strategy-abst}) possibles des stratégies mixtes des joueurs dans un équilibre de Nash, c'est-à-dire toutes les -$(2^{\#A_1}-1)\penalty0\times\penalty0(2^{\#A_2}-1)$ -données de parties non vides de -$A_1$ et $A_2$, et, pour chacune, appliquer le raisonnement suivant : -si $s_i$ est une meilleure réponse possible pour le joueur $i$ (contre -la stratégie $s_{?i}$ de l'autre joueur) alors \emph{toutes les - options du support de $s_i$ ont la même espérance de gain} -(contre $s_{?i}$ ; cf. \ref{stupid-remark-best-mixed-strategies}), ce -qui fournit un jeu d'égalités linéaires sur les valeurs de $s_{?i}$. -En rassemblant ces inégalités (ainsi que celles qui affirment que la -somme des valeurs de $s_i$ et de $s_{?i}$ valent $1$), on arrive -« normalement » à trouver tous les équilibres de Nash possibles : voir -les exercices +$(2^{\#A_1}-1)\penalty0\times\penalty0(2^{\#A_2}-1)$ données de +parties non vides de $A_1$ et $A_2$, et, pour chacune, appliquer le +raisonnement suivant : si $s_i$ est une meilleure réponse possible +pour le joueur $i$ (contre la stratégie $s_{?i}$ de l'autre joueur) +alors \emph{toutes les options du support de $s_i$ ont la même + espérance de gain} (contre $s_{?i}$ ; +cf. \ref{stupid-remark-best-mixed-strategies}), ce qui fournit un jeu +d'égalités linéaires sur les valeurs de $s_{?i}$. En rassemblant ces +inégalités (ainsi que celles qui affirment que la somme des valeurs de +$s_i$ et de $s_{?i}$ valent $1$), on arrive « normalement » à trouver +tous les équilibres de Nash possibles : voir \ref{dove-or-hawk} +ci-dessous, ainsi que les exercices \ref{normal-form-game-exercise-two-by-two} et \ref{normal-form-game-exercise-three-by-three} (dernières questions) pour des exemples. @@ -1361,6 +1533,67 @@ algorithmiquement possible en théorie en vertu d'un théorème de Tarski et Seidenberg sur la décidabilité des systèmes d'équations algébriques réels, mais possiblement inextricable dans la pratique.) +\thingy\label{dove-or-hawk-redux} Pour donner un exemple, revenons sur +le \index{trouillard (jeu du)}jeu du trouillard défini +en \ref{dove-or-hawk} et dressons un tableau de l'espérance de gain +pour quelques stratégies mixtes ainsi que la stratégie mixte +« générique » : + +{\footnotesize +\begin{center} +\begin{tabular}{r|c|c|c|c|c|} +$\downarrow$Alice, Bob$\rightarrow$&Colombe&Faucon&$\frac{2}{3}C+\frac{1}{3}F$&$\frac{1}{2}C+\frac{1}{2}F$&$qC+(1-q)F$\\\hline +Colombe&$2,2$&\textcolor{blue}{$0,4$}&$\frac{4}{3},\frac{8}{3}$&$1,3$&{\tiny $2q, 4-2q$}\\\hline +Faucon&\textcolor{blue}{$4,0$}&$-4,-4$&$\frac{4}{3},-\frac{4}{3}$&$0,-2$&{\tiny $-4+8q, -4+4q$}\\\hline +$\frac{2}{3}C+\frac{1}{3}F$&$\frac{8}{3},\frac{4}{3}$&$-\frac{4}{3},\frac{4}{3}$&\textcolor{blue}{$\frac{4}{3},\frac{4}{3}$}&$\frac{2}{3},\frac{4}{3}$&{\tiny $-\frac{4}{3}+4q, \frac{4}{3}$}\\\hline +$\frac{1}{2}C+\frac{1}{2}F$&$3,1$&$-2,0$&$\frac{4}{3},\frac{2}{3}$&$\frac{1}{2},\frac{1}{2}$&$-2+5q,q$\\\hline +$pC+(1-p)F$&{\tiny $4-2p,2p$}&{\tiny $-4+2p,-4+8p$}&{\tiny $\frac{4}{3},-\frac{4}{3}+4p$}&{\tiny $p,-2+5p$}&$(\dagger)$\\\hline +\end{tabular} +\end{center} +\par\noindent +où $(\dagger) = (-4 + 4p + 8q - 6pq, - 4 + 8p + 4q - 6pq)$. +\par} + +\smallskip + +Les trois profils $(C,F)$ (i.e., Alice joue Colombe et Bob joue +Faucon), $(F,C)$ et $(\frac{2}{3}C+\frac{1}{3}F, +\frac{2}{3}C+\frac{1}{3}F)$ sont des équilibres de Nash : cela résulte +du fait que, quand on regarde la case correspondante du tableau, le +premier nombre est maximum sur la colonne (c'est-à-dire qu'Alice n'a +pas intérêt à changer unilatéralement sa stratégie) et le second est +maximum sur la ligne (c'est-à-dire que Bob n'a pas intérêt à changer +unilatéralement sa stratégie) : chacun de ces maxima peut se tester +simplement contre les stratégies pures de l'adversaire (i.e., les deux +premières lignes ou colonnes). Pour trouver ces équilibres et +vérifier qu'il n'y en a pas d'autre, on peut : +\begin{itemize} +\item commencer par rechercher les équilibres de Nash où chacun des + deux joueurs joue une stratégie pure (ceci revient à regarder + chacune des quatre cases du tableau initial et chercher si le + premier nombre est maximal sur la colonne et le second maximal sur + la ligne) ; +\item considérer la possibilité d'un équilibre de Nash où l'un des + joueurs joue une stratégie pure et l'autre une stratégie mixte + supportée par les deux options : si par exemple Alice joue + $pC+(1-p)F$ avec $p>0$ et Bob joue $a \in \{C,F\}$, + d'après \ref{stupid-remark-best-mixed-strategies}, le gain d'Alice + dans les cases $(C,a)$ et $(F,a)$ doit être le même, ce qui n'est + pas le cas, donc il n'y a pas de tel équilibre (pas plus que dans le + cas correspondant pour Bob) ; +\item enfin, rechercher les équilibres de Nash où chacun des deux + joueurs joue une stratégie supportée par les deux options, soit ici + $pC+(1-p)F$ pour Alice et $qC+(1-q)F$ pour Bob avec $0<p<1$ et + $0<q<1$ : d'après \ref{stupid-remark-best-mixed-strategies} le gain + espéré d'Alice doit être le même contre $qC+(1-q)F$ indifféremment + qu'elle joue Colombe ou Faucon, ce qui implique $2q = -4+8q$ donc + $q=\frac{2}{3}$, et symétriquement, le gain espéré de Bob doit être + le même contre $pC+(1-p)F$ indifféremment qu'il joue Colombe ou + Faucon, ce qui implique $2p = -4+8p$ donc $p=\frac{2}{3}$, si bien + que le seul équilibre de Nash de cette nature est celui qu'on a + décrit (et il faut vérifier qu'il en est bien un). +\end{itemize} + \thingy Mentionnons en complément une notion plus générale que celle d'équilibre de Nash : si $s\colon A \to \mathbb{R}$ (où $A := A_1\times\cdots\times A_N$) est cette fois une distribution de @@ -1419,182 +1652,270 @@ dire que $(s_1,\ldots,s_N)$ est un équilibre de Nash. Autrement dit : \subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games} +Plaçons nous maintenant dans le cadre d'un jeu à somme nulle, +c'est-à-dire qu'il y a $N=2$ joueurs, et qu'ils ont des gains +opposés : disons qu'on appelle $u = u_1$ le gain du joueur $1$ +(« Alice »), le gain du joueur $2$ (« Bob ») étant alors $u_2 = -u$ et +n'a pas besoin d'être écrit dans le tableau. Ainsi, Alice cherche à +\emph{maximiser} $u$ et Bob cherche à le \emph{minimiser} (puisque +maximiser $-u$ revient à minimiser $u$). + +En considérant le jeu du point de vue de sa matrice de gains (où, de +nouveau, on n'a écrit que le gain d'Alice), Alice cherche à choisir +une ligne qui maximiser la valeur écrite dans le tableau et Bob +cherche à choisir une colonne qui mimimise la valeur écrite. Mais en +général, si $u\colon A_1 \times A_2 \to \mathbb{R}$ est un tableau +fini de nombres réels, $\max_{a \in A_1} \min_{b\in A_2} u(a,b)$ ne +coïncide pas avec $\min_{b\in A_2} \max_{a \in A_1} u(a,b)$ (on a +seulement l'inégalité $\max_{a \in A_1} \min_{b\in A_2} u(a,b) \leq +\min_{b\in A_2} \max_{a \in A_1} u(a,b)$, qui sera démontrée ci-dessus +au début de la démonstration de \ref{theorem-minimax}). L'observation +cruciale est que, quand on passe des ensembles finis $A_i$ de +stratégies pures aux simplexes $S_i$ de stratégies mixtes, on a alors +une égalité : + \begin{thm}[« du minimax », J. von Neumann, 1928]\label{theorem-minimax} -Soient $C$ et $C'$ deux convexes compacts dans des espaces affines -réels de dimension finie, et $u\colon C\times C' \to \mathbb{R}$ -une application bi-affine (c'est-à-dire, affine en chaque variable -séparément). Alors +Soient $A_1,A_2$ deux ensembles finis et $S_1,S_2$ les simplexes de +stratégies mixtes (cf. \ref{definition-mixed-strategy-abst}) +sur $A_1,A_2$ ; soit $u\colon A_1\times A_2 \to \mathbb{R}$ une +fonction quelconque, et on notera encore $u$ son unique extension +(explicitée en \ref{definition-mixed-strategy-gain}) en une fonction +$S_1\times S_2 \to \mathbb{R}$ affine en chaque variable. On a +alors : \[ -\max_{x\in C} \min_{y\in C'} u(x,y) = -\min_{y\in C'} \max_{x\in C} u(x,y) +\max_{x\in S_1} \min_{y\in S_2} u(x,y) = +\min_{y\in S_2} \max_{x\in S_1} u(x,y) \] +(Ceci sous-entend notamment ces $\min$ et $\max$ existent bien.) + +Plus généralement, si $S_1$ et $S_2$ sont deux convexes compacts dans +des espaces affines réels de dimension finie, et $u\colon S_1\times +S_2 \to \mathbb{R}$ une application affine en chaque variable +séparément, alors on a l'égalité ci-dessus. \end{thm} \begin{proof} -Tout d'abord, l'inégalité dans un sens est évidente : on a +Plaçons-nous d'abord dans le cas (qui intéresse la théorie des jeux) +où $A_1,A_2$ sont deux ensembles finis et $S_1,S_2$ les simplexes de +stratégies mixtes. + +Tout d'abord, montrons l'existence des $\min$ et $\max$ annoncés ainsi +que l'inégalité dans le sens $\max\min \leq \min\max$. On a vu +en \ref{affine-functions-take-extrema-at-boundary} que $\min_{y\in + S_2} u(x,y)$ existe et vaut $\min_{b\in A_2} u(x,b)$ pour tout $x\in +S_1$ : ceci montre que la fonction $x \mapsto \min_{y\in S_2} u(x,y)$ +s'écrit encore $x \mapsto \min_{b\in A_2} u(x,b)$, donc il s'agit du +minimum d'un nombre \emph{fini} de fonctions continues (affines) +sur $S_1$, donc elle est encore continue et atteint ses bornes sur +l'ensemble compact $S_1$ : il existe donc $x_* \in S_1$ où cette +fonction atteint son maximum. Soit de même $y_* \in S_2$ un point où +$y \mapsto \max_{x\in S_1} u(x,y)$ atteint son minimum. On a alors : \[ -\max_{x\in C} \min_{y\in C'} u(x,y) -= \min_{y\in C'} u(x_*,y) -\leq u(x_*,y_*) \leq \max_{x\in C} u(x,y_*) = -\min_{y\in C'} \max_{x\in C} u(x,y) +\max_{x\in S_1} \min_{y\in S_2} u(x,y) += \min_{y\in S_2} u(x_*,y) +\leq u(x_*,y_*) \leq \max_{x\in S_1} u(x,y_*) = +\min_{y\in S_2} \max_{x\in S_1} u(x,y) \] -où $x_* \in C$ est un point où $\max_{x\in C} \min_{y\in C'} -u(x,y)$ est atteint et $y_* \in C'$ un point où $\min_{y\in C'} -\max_{x\in C} u(x,y)$ l'est. Il s'agit donc de prouver -l'inégalité de sens contraire. - -Commençons par supposer que $C$ est l'enveloppe convexe d'un nombre -fini de points $(x_i)_{i\in I}$ et $C'$ de $(y_j)_{j\in J}$, et on -expliquera plus loin comment se ramener à ce cas (même si c'est le -seul qui servira dans le cadre de la théorie des jeux). Lorsque cette -hypothèse est vérifiée, on va définir une fonction $T\colon C\times C' -\to C\times C'$ de la façon suivante. Donnons-nous $(x,y) \in C\times -C'$. Pour chaque $i\in I$, on définit $\varphi_i(x,y) = \max (0,\; -u(x_i,y)-u(x,y))$, et de même on pose $\psi_j(x,y) = \max (0,\; -u(x,y)-u(x,y_j))$. Posons enfin $T(x,y) = (x^\sharp,y^\sharp)$ où -$x^\sharp$ et $y^\sharp$ (qui dépendent tous les deux de $x$ et $y$ à -la fois, malgré la notation) sont définis comme suit. On appelle -$x^\sharp$ le barycentre de $x$ affecté du coefficient $1$ et des -$x_i$ (pour $i\in I$) affectés des coefficients respectifs -$\varphi_i(x,y)$, c'est-à-dire $x^\sharp = \frac{x + \sum_{i\in I} - \varphi_i(x,y)\,x_i}{1 + \sum_{i\in I} \varphi_i(x,y)}$ ; et soit de -même $y^\sharp$ le barycentre de $y$ avec coefficient $1$ et des $y_i$ -avec les coefficients $\psi_i(x,y)$. Clairement, $x^\sharp$ et -$y^\sharp$ sont dans $C$ et $C'$ respectivement (il s'agit de -barycentres à coefficients positifs, c'est-à-dire de combinaisons -convexes). La fonction $T\colon C\times C' \to C\times C'$ définie -par $T(x,y) = (x^\sharp,y^\sharp)$ est continue. Par ailleurs, on a -$x^\sharp = x$ si et seulement si $x$ réalise $\max_{\tilde x\in C} -u(\tilde x,y)$ (un sens est évident, et pour l'autre il suffit de se -convaincre que s'il existe $\tilde x$ tel que $u(\tilde x,y) > u(x,y)$ -alors il y a un $i$ tel que ceci soit vrai en remplaçant $\tilde x$ -par $x_i$, et on a alors $\varphi_i(x,y)>0$ donc $u(x^\sharp,y) > -u(x,y)$) ; et on a un résultat analogue pour $y$. La fonction $T$ -continue du compact convexe $C\times C'$ vers lui-même y admet -d'après \ref{brouwer-fixed-point-theorem} un -point fixe $(x_0,y_0)$, vérifiant donc $(x_0^\sharp, y_0^\sharp) = -(x_0,y_0)$, c'est-à-dire que $u (x_0,y_0) = \max_{x\in C} u(x,y_0) = -\min_{y\in C'} u(x_0, y)$. On a donc maintenant +La première relation est la définition de $x_*$, la seconde est la +définition du $\min$, la troisième la définition du $\max$, et la +quatrième est la définition de $y_*$. (Notons que tout ceci vaut dans +n'importe quel contexte où les $\min$ et $\max$ existent, notamment +ceci prouve aussi $\max_{a \in A_1} \min_{b\in A_2} u(a,b) \leq +\min_{b\in A_2} \max_{a \in A_1} u(a,b)$ affirmé ci-dessus.) + +Il s'agit maintenant de prouver l'inégalité de sens contraire. + +Considérons $(x_0,y_0)$ un équilibre de Nash du jeu à somme nulle dont +la matrice de gains est donnée par $u$ pour le joueur $1$ (et $-u$ +pour le joueur $2$) : on sait qu'un tel équilibre existe +d'après \ref{theorem-nash-equilibria}. On a alors \[ -\max_{x\in C} \min_{y\in C'} u(x,y) -\geq \min_{y\in C'} u(x_0,y) = u(x_0,y_0) -= \max_{x\in C} u(x,y_0) \geq -\min_{y\in C'} \max_{x\in C} u(x,y) +\max_{x\in S_1} \min_{y\in S_2} u(x,y) +\geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0) += \max_{x\in S_1} u(x,y_0) \geq +\min_{y\in S_2} \max_{x\in S_1} u(x,y) \] -ce qu'on voulait. - -Pour se ramener au cas où $C$ et $C'$ sont enveloppes convexes d'un -nombre fini de points, on observe que pour tout $\varepsilon>0$ il -existe $\Sigma$ et $\Sigma'$ des enveloppes convexes d'un nombre fini -de points (= polytopes) contenues dans $C$ et $C'$ respectivement et -telles que pour tout $x\in C$ on ait $\min_{y\in C'} u(x,y) > -\min_{y\in\Sigma'} u(x,y)-\varepsilon$ et $\max_{x\in C} u(x,y) < -\max_{x\in\Sigma} u(x,y)+\varepsilon$ (explication : il est trivial -que pour chaque $x$ il existe un $\Sigma'$ vérifiant la condition -demandée, le point intéressant est qu'un unique $\Sigma'$ peut -convenir pour tous les $x$ ; mais pour chaque $\Sigma'$ donné, -l'ensemble des $x$ pour lesquels il convient est un ouvert de $C$, qui -est compact, donc un nombre fini de ces ouverts recouvrent $C$, et on -prend l'enveloppe convexe de la réunion des $\Sigma'$ en question ; on -procède de même pour $\Sigma$). On a alors $\max_{x\in C} \min_{y\in - C'} u(x,y) > \max_{x\in \Sigma} \min_{y\in \Sigma'} u(x,y) - -\varepsilon$ et une inégalité analogue pour l'autre membre : on en -déduit l'inégalité recherchée à $2\varepsilon$ près, mais comme on -peut prendre $\varepsilon$ arbitrairement petit, on a ce qu'on -voulait. +Ici, la première relation est la définition du $\max$, la seconde +traduit le fait que (dans la définition de l'équilibre de Nash) Bob +fait une meilleure réponse possible à $x_0$, la troisième traduit le +fait qu'Alice fait une meilleure réponse possible à $y_0$, et la +quatrième est la définition du $\min$. + +Ceci achève de montrer $\max_{x\in S_1} \min_{y\in S_2} u(x,y) = +\min_{y\in S_2} \max_{x\in S_1} u(x,y)$ lorsque $S_1$ et $S_2$ sont +deux simplexes dans $\mathbb{R}^n$, et $u\colon S_1\times S_2 \to +\mathbb{R}$ une application affine en chaque variable séparément. Si +maintenant $S_1$ et $S_2$ sont deux polytopes, c'est-à-dire chacun +l'enveloppe d'un nombre fini de points $A_1$ et $A_2$ +dans $\mathbb{R}^n$, mais plus forcément des simplexes (c'est-à-dire +qu'on ne suppose plus les points de $A_i$ affinement indépendants), la +même conclusion vaut encore : en effet, si on appelle $S'_i$ le +simplexe construit abstraitement sur $A_i$ (i.e., l'ensemble des +fonctions $s\colon A_i \to \mathbb{R}$ positives de somme $1$), et +$\varpi_i \colon S'_i \to S_i$ la fonction (affine et surjective) +envoyant $s\colon A_i \to \mathbb{R}$ positive de somme $1$ sur la +somme des $s(a)\cdot a$ (dans le $\mathbb{R}^n$ où vivent $A_i$ +et $S_i$), alors la fonction $u\colon S_1\times S_2 \to \mathbb{R}$ +donnée définit une fonction $u'\colon S'_1\times S'_2 \to \mathbb{R}$, +elle aussi affine en chaque variable, par $u'(x,y) = u(\varpi_1(x), +\varpi_2(y))$, et il est évident que les extrema de $u'$ sur $S'_1 +\times S'_2$ coïncident avec ceux de $u$ sur $S_1 \times S_2$, donc la +conclusion qui précède, appliquée à $u'$, donne la conclusion désirée +sur $u$. + +Enfin, si $S_1$ et $S_2$ sont seulement supposés être des convexes +compacts dans $\mathbb{R}^n$, on observe que pour tout $\varepsilon>0$ +il existe $\Sigma_1$ et $\Sigma_2$ des polytopes contenus dans $S_1$ +et $S_2$ respectivement et tels que pour tout $x\in S_1$ on ait +$\min_{y\in S_2} u(x,y) > \min_{y\in\Sigma_2} u(x,y)-\varepsilon$ et +$\max_{x\in S_1} u(x,y) < \max_{x\in\Sigma_1} u(x,y)+\varepsilon$ +(explication : il est trivial que pour chaque $x$ il existe un +$\Sigma_2$ vérifiant la condition demandée, le point intéressant est +qu'un unique $\Sigma_2$ peut convenir pour tous les $x$ ; mais pour +chaque $\Sigma_2$ donné, l'ensemble des $x$ pour lesquels il convient +est un ouvert de $S_1$, qui est compact, donc un nombre fini de ces +ouverts recouvrent $S_1$, et on prend l'enveloppe convexe de la +réunion des $\Sigma_2$ en question ; on procède de même pour +$\Sigma_1$). On a alors $\max_{x\in S_1} \min_{y\in S_2} u(x,y) > +\max_{x\in \Sigma_1} \min_{y\in \Sigma_2} u(x,y) - \varepsilon$ et une +inégalité analogue pour l'autre membre : on en déduit l'inégalité +recherchée à $2\varepsilon$ près, mais comme on peut prendre +$\varepsilon$ arbitrairement petit, on a ce qu'on voulait. \end{proof} +Le corollaire suivant explicite la situation particulière où, en +outre, le jeu est symétrique entre les deux joueurs (c'est-à-dire que +sa matrice de gains écrite pour un seul joueur est, elle, +\emph{anti}symétrique) : + \begin{cor}\label{symmetric-zero-sum-game} -Soit $C$ un convexe compact dans un espace affine réel de dimension -finie, et $u\colon C^2 \to \mathbb{R}$ une application bi-affine -antisymétrique (i.e., $u(y,x) = -u(x,y)$). Alors il -existe $x\in C$ tel que pour tout $y\in C$ on ait $u(x,y)\geq 0$ -(et la valeur commune des deux membres de l'égalité du -théorème \ref{theorem-minimax} est $0$). +Soient $A$ un ensemble fini et $S$ le simplexe de stratégies mixtes +sur $A$ ; soit $u\colon A^2 \to \mathbb{R}$ une application +antisymétrique (i.e., $u(b,a) = -u(a,b)$), et on notera encore $u$ son +unique extension affine en chaque variable en une fonction $S^2 \to +\mathbb{R}$ affine en chaque variable. Alors la valeur commune des +deux membres de l'égalité du théorème \ref{theorem-minimax} est $0$ : +il existe $x\in S$ tel que pour tout $y\in S$ on ait $u(x,y)\geq 0$. + +Plus généralement, si $S$ est un convexe compact dans un espace affine +réel de dimension finie, et $u\colon S^2 \to \mathbb{R}$ une +application antisymétrique (i.e., $u(y,x) = -u(x,y)$) et affine en +chaque variable séparément, la même conclusion vaut. \end{cor} \begin{proof} -On applique le théorème : il donne $\max_{x\in C}\penalty0 \min_{y\in - C} u(x,y) = \min_{y\in C}\penalty0 \max_{x\in C} u(x,y)$. Mais -puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in C} -\max_{x\in C} (-u(y,x))$, soit, en renommant les variables liées, -$\min_{x\in C}\penalty0 \max_{y\in C} (-u(x,y)) = -\max_{x\in - C}\penalty0 \min_{y\in C} u(x,y)$. Par conséquent, $\max_{x\in - C}\penalty0 \min_{y\in C} u(x,y) = 0$ (il est son propre opposé), et -en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in C} u(x,y) = +On applique le théorème : il donne $\max_{x\in S}\penalty0 \min_{y\in + S} u(x,y) = \min_{y\in S}\penalty0 \max_{x\in S} u(x,y)$. Mais +puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in S} +\max_{x\in S} (-u(y,x))$, soit, en renommant les variables liées, +$\min_{x\in S}\penalty0 \max_{y\in S} (-u(x,y)) = -\max_{x\in + S}\penalty0 \min_{y\in S} u(x,y)$. Par conséquent, $\max_{x\in + S}\penalty0 \min_{y\in S} u(x,y) = 0$ (il est son propre opposé), et +en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in S} u(x,y) = 0$, ce qu'on voulait prouver. \end{proof} -%% TODO: rendre ça plus clair ; énoncer un théorème précis pour les -%% phrases en italiques. - -\thingy\label{minimax-for-games} Le théorème \ref{theorem-minimax} -s'applique à la théorie des jeux de la manière suivante : si on -considère un jeu à deux joueurs à somme nulle, en notant $S_1$ et -$S_2$ les ensembles des stratégies mixtes des deux joueurs, et $u -\colon S_1 \times S_2 \to \mathbb{R}$ le gain espéré du joueur $1$, le -gain du joueur $2$ étant donc $-u$, le fait que $(x_0,y_0)$ soit un -équilibre de Nash se traduit par le fait que $x_0$ soit la meilleure -réponse possible de $1$ contre $y_0$, i.e., $u(x_0,y_0) = \max_{x\in - S_1} u(x,y_0)$, et le fait que $y_0$ soit la meilleure réponse -possible de $2$ contre $x_0$, c'est-à-dire $u(x_0,y_0) = \min_{y\in - S_2} u(x_0,y)$ (puisque $2$ cherche à maximiser $-u$, c'est-à-dire -minimiser $u$). Comme on l'a expliqué dans la preuve, on a -\[ -\max_{x\in S_1} \min_{y\in S_2} u(x,y) -\geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0) -= \max_{x\in S_1} u(x,y_0) \geq -\min_{y\in S_2} \max_{x\in S_1} u(x,y) -\] -donc en fait il y a égalité partout : tout équilibre de Nash réalise -la même valeur $u(x_0,y_0) = \max_{x\in S_1} \min_{y\in S_2} u(x,y) = -\min_{y\in S_2} \max_{x\in S_1} u(x,y)$, qu'on appelle la -\defin[valeur (d'un jeu à somme nulle)]{valeur} du jeu à somme nulle. - -On peut donc parler de \index{optimale (stratégie)}\defin{stratégie - optimale} pour le joueur $1$, resp. $2$ pour désigner une composante -$x_0$, resp. $y_0$, d'un équilibre de Nash, i.e., vérifiant -$\min_{y\in S_2} u(x_0,y) = \max_{x\in S_1} \min_{y\in S_2} u(x,y)$, -resp. $\max_{x\in S_1} u(x,y_0) = \min_{y\in S_2} \max_{x\in S_1} -u(x,y)$, ces deux quantités étant égales à la valeur du jeu. - -Moralité : \emph{dans un jeu à somme nulle, un profil de stratégies +\smallskip + +Considérons maintenant les applications du +théorème \ref{theorem-minimax} dans le cadre de la théorie des jeux. +Commençons par définir les concepts suivants : + +\begin{defn}\label{definition-zero-sum-game-value-and-optimum} +Pour un jeu à somme nulle défini par une matrice de gains $u \colon +A_1 \times A_2 \to \mathbb{R}$ : +\begin{itemize} +\item La \defin[valeur (d'un jeu à somme nulle)]{valeur} est la valeur + commune $\max_{x\in S_1} \min_{y\in S_2} u(x,y) = \min_{y\in S_2} + \max_{x\in S_1} u(x,y)$ où $S_1,S_2$ sont les simplexes de + stratégies mixtes des joueurs $1$ et $2$ respectivement (et $u(x,y)$ + l'espérance de gain explicitée + en \ref{definition-mixed-strategy-gain}). +\item Une stratégie mixte du joueur $1$ qui réalise $\max_{x\in S_1} + \min_{y\in S_2} u(x,y)$ (resp. une stratégie mixte du joueur $2$ qui + réalise $\min_{y\in S_2} \max_{x\in S_1} u(x,y)$) est dite + \index{optimale (stratégie)}\defin{stratégie optimale} pour le + joueur en question. +\end{itemize} +\end{defn} + +Le théorème \ref{theorem-minimax} (et, pour le dernier point, le +corollaire \ref{symmetric-zero-sum-game}) a alors les conséquences +suivantes : + +\begin{prop}\label{minimax-for-games} Pour un jeu à somme nulle défini +par une matrice de gains $u \colon A_1 \times A_2 \to \mathbb{R}$ : +\begin{itemize} +\item[(i)] Un profil $(x_0,y_0) \in S_1\times S_2$ de stratégies + mixtes est un équilibre de Nash si et seulement si $x_0$ et $y_0$ + sont chacun une stratégie optimale pour le joueur correspondant. +\item[(ii)] Tous les équilibres de Nash ont la même valeur de gain + espéré, à savoir la valeur du jeu $v$ (pour le joueur 1). +\item[(iii)] Une stratégie mixte $x_0 \in S_1$ du joueur $1$ est une + stratégie optimale pour celui-ci si et seulement si $u(x_0,b) \geq + v$ pour tout $b\in A_2$ (où $v$ désigne la valeur du jeu). Une + stratégie mixte $y_0 \in S_2$ du joueur $2$ est une stratégie + optimale pour celui-ci si et seulement si $u(a,y_0) \leq v$ pour + tout $a\in A_1$. +\item[(iv)] L'ensemble $T_1$ des stratégies optimales du joueur $1$ + est un convexe, de même que l'ensemble $T_2$ des stratégies + optimales du joueur $2$. (L'ensemble des équilibres de Nash est + donc aussi un convexe, à savoir $T_1 \times T_2$.) +\item[(v)] Si le jeu est symétrique, c'est-à-dire $A_2 = A_1 =: A$ et + $u(b,a) = -u(a,b)$ (matrice de gains antisymétrique), alors la + valeur du jeu est nulle. +\end{itemize} +\end{prop} + +\begin{proof} +(i) : On a vu au cours de la preuve de \ref{theorem-minimax} que si + $(x_0,y_0)$ est un équilibre de Nash, alors $\max_{x\in S_1} + \min_{y\in S_2} u(x,y) \geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0) = + \max_{x\in S_1} u(x,y_0) \geq \min_{y\in S_2} \max_{x\in S_1} + u(x,y)$, mais comme les deux termes extrêmes sont égaux, en fait + toutes ces inégalités sont des égalités, donc $x_0$ réalise bien le + maximum $\max_{x\in S_1} \min_{y\in S_2} u(x,y)$ et $y_0$ le minimum + $\min_{y\in S_2} \max_{x\in S_1} u(x,y)$, i.e., ils sont des + stratégies optimales. Réciproquement, si $x_*$ est une stratégie + optimale du joueur $1$ et $y_*$ du joueur $2$, on a vu au cours de + la même preuve qu'on a $\max_{x\in S_1} \min_{y\in S_2} u(x,y) = + \min_{y\in S_2} u(x_*,y) \leq u(x_*,y_*) \leq \max_{x\in S_1} + u(x,y_*) = \min_{y\in S_2} \max_{x\in S_1} u(x,y)$, et, de nouveau, + totues ces inégalités sont des égalités, donc $x_*$ est une + meilleure réponse possible pour le joueur $1$ contre $y_*$ et $y_*$ + est une meilleure réponse possible pour le joueur $2$ contre $x_*$, + ce qui signifie que $(x_*,y_*)$ est un équilibre de Nash. + +Le point (ii) résulte de ce qui vient d'être dit. + +(iii) : Par définition, $x_0$ est optimale ssi $\min_{y\in S_2} +u(x_0,y) = v$, ou, comme on ne peut pas faire plus que le maximum, +$\min_{y\in S_2} u(x_0,y) \geq v$. Mais on a vu +en \ref{affine-functions-take-extrema-at-boundary} que $\min_{y\in + S_2} u(x_0,y) = \min_{b\in A_2} u(x_0,b)$, c'est-à-dire que $x_0$ +est optimale si et seulement si $\min_{b\in A_2} u(x_0,b) \geq v$, ce +qui revient bien à dire $u(x_0,b) \geq v$ pour tout $b$. Le cas de +l'autre joueur est analogue. + +(iv) : Il résulte du point précédent que $T_1$ est l'intersections des +ensembles $\{x \in S_1 : u(x,b)\geq v\}$ où $b$ parcourt $A_2$ : mais +chacun de ces ensembles est convexe, donc leur intersection l'est +aussi. Le cas de $T_2$ est analogue. La parenthèse est une redite du +point (i). + +Le point (v) n'est qu'une redite du +corollaire \ref{symmetric-zero-sum-game}. +\end{proof} + +Répétons : \emph{dans un jeu à somme nulle, un profil de stratégies est un équilibre de Nash si et seulement si chaque joueur joue une - stratégie optimale} (l'ensemble des stratégies optimales étant -défini pour chaque joueur indépendamment). - -Le corollaire \ref{symmetric-zero-sum-game} nous apprend (de façon peu -surprenante) que si le jeu à somme nulle est \emph{symétrique} (ce qui -signifie que $u$ est antisymétrique), alors la valeur du jeu est -nulle. - -\thingy Dans le contexte ci-dessus, on peut légèrement reformuler le -minimax : si on se rappelle (cf. \ref{stupid-remark-best-mixed-strategies}) -qu'une fonction affine sur un - simplexe prend son maximum (ou son minimum) sur un des sommets du -simplexe, cela signifie que, quel que soit $x\in S_1$ fixé, le minimum -$\min_{y\in S_2} u(x,y)$ est en fait atteint sur une stratégie -\emph{pure}, $\min_{y\in S_2} u(x,y) = \min_{b\in A_2} u(x,b)$ (avec -$A_2$ l'ensemble des sommets de $S_2$, i.e., l'ensemble des stratégies -pures du joueur $2$), et de même $\max_{x\in S_1} u(x,y) = \max_{a\in - A_1} u(a,y)$ quel que soit $y \in S_2$. \emph{Ceci ne signifie pas} -qu'il existe un équilibre de Nash en stratégies pures (penser à -pierre-papier-ciseaux). Néanmoins, cela signifie que pour calculer la -pire valeur possible $\min_{y\in S_2} u(x,y)$ d'une stratégie $x$ du -joueur $1$, celui-ci peut ne considérer que les réponses en stratégies -pures du joueur $2$. - -Si on appelle $v$ la valeur du jeu, l'ensemble des $x$ tels que -$u(x,y) \geq v$ pour tout $y\in S_2$, c'est-à-dire l'ensemble des -stratégies optimales pour le joueur $1$, coïncide donc avec l'ensemble -des $x$ tels que $u(x,b) \geq v$ pour tout $b\in A_2$. En -particulier, c'est un convexe compact dans $S_1$ (puisque chaque -inégalité $u(x,b) \geq v$ définit un convexe compact dans $S_1$ vu que -$x \mapsto u(x,b)$ est affine) : \emph{en moyennant deux stratégies - optimales pour un joueur on obtient encore une telle stratégie} -(notamment, l'ensemble des équilibres de Nash est un convexe de -$S_1\times S_2$ — puisque c'est le produit du convexe des stratégies -optimales pour le premier joueur par celui des stratégies optimales -pour le second — affirmation qui n'est pas vraie en général pour des -jeux qui ne sont pas à somme nulle). + stratégie optimale}, l'ensemble des stratégies optimales étant un +convexe (défini pour chaque joueur indépendamment). + +L'ensemble des stratégies optimales d'un joueur donné est « très +souvent » un singleton, ce qui fait qu'on parle parfois abusivement de +« la » stratégie optimale. + +Reste maintenant à expliquer comment calculer les stratégies +optimales : \begin{algo}\label{zero-sum-games-by-linear-programming-algorithm} Donnée une fonction $u\colon A_1 \times A_2 \to \mathbb{R}$ (avec @@ -1613,6 +1934,9 @@ $\#A_1 + 1$ variables avec des contraintes de positivité sur $\#A_1$ d'entre elles, une contrainte d'égalité et $\#A_2$ inégalités affines. \end{algo} +(La correction de cet algorithme découle à peu près immédiatement du +point (iii) ci-dessus.) + \thingy Pour ramener ce problème à un problème de programmation linéaire en \emph{forme normale} (maximiser $\textbf{p} x$ sous les contraintes $\textbf{M} x \leq \textbf{q}$ et $x\geq 0$), on sépare la @@ -1623,7 +1947,7 @@ devient de maximiser $v_+ - v_-$ sous les contraintes \[-\sum_{a\in A_1} x_a \leq -1\] \[(\forall b\in A_2)\;v_+ - v_- - \sum_{a \in A_1} u(a,b)\, x_a \leq 0\] Le problème dual (minimiser ${^{\mathrm{t}}\textbf{q}} y$ sous les -contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{q}}$ +contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{p}}$ et $y\geq 0$) est alors de minimiser $w_+ - w_-$ sous les contraintes \[w_+\geq 0,\; w_- \geq 0,\;\; (\forall b\in A_2)\;y_b \geq 0\] \[\sum_{b\in A_2} y_b \geq 1\] |