diff options
Diffstat (limited to 'controle-20250626.tex')
| -rw-r--r-- | controle-20250626.tex | 291 |
1 files changed, 276 insertions, 15 deletions
diff --git a/controle-20250626.tex b/controle-20250626.tex index 6786bed..9406b12 100644 --- a/controle-20250626.tex +++ b/controle-20250626.tex @@ -92,6 +92,8 @@ 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. +Une traduction anglaise indicative suit l'énoncé en français. + \medbreak L'usage de tous les documents (notes de cours manuscrites ou @@ -101,7 +103,7 @@ L'usage des appareils électroniques est interdit. \medbreak -Durée : 2h +% Durée : 2h \ifcorrige Ce corrigé comporte \textcolor{red}{XXX} pages (page de garde incluse). @@ -123,7 +125,7 @@ Git: \input{vcline.tex} % % -\exercise +\exercise\label{normal-form-games-exercise} \textbf{(1)} On considère le jeu en forme normale symétrique à somme nulle défini par la matrice de gains suivante : @@ -288,14 +290,14 @@ meilleur possible ici. % % -\exercise +\exercise\label{modified-nim-exercise} On considère dans cet exercice le jeu suivant : Alice et Bob ont devant eux des piles de jetons, qui représentent l'état du jeu (= la position). Chaque pile contient un certain nombre fini (entier naturel) de jetons. Les piles sont numérotées par des -entiers naturelles, mais il n'y en a qu'un nombre fini qui soient +entiers naturels, mais il n'y en a qu'un nombre fini qui soient non-vides (i.e., qui aient $>0$ jetons). Pour représenter la position mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, n_k)$ où $n_i$ est le nombre de jetons de la pile numérotée $i$, et où ceci @@ -537,7 +539,7 @@ démonstration. % % -\exercise +\exercise\label{indeterminacy-exercise} On se propose dans cet exercice de montrer qu'il existe une partie $A \subseteq \{0,1\}^{\mathbb{N}}$ tel que le jeu de Gale-Stewart $G(A) @@ -697,16 +699,16 @@ $(\tau_\xi)_{\xi<\mathfrak{c}}$ des stratégies de Bob. On les définira après la question (9), mais on n'a pas besoin d'en savoir plus pour l'instant. -\textbf{(7)} En supposant préalablement définis des éléments -$(a_\xi)_{\xi<\alpha}$ et $(b_\xi)_{\xi<\alpha}$ de -$\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, déduire en une -ligne des questions précédentes qu'il existe $b'$ qui soit de la forme -$\sigma_\alpha \ast y$ (pour un certain $y \in \{0,1\}^{\mathbb{N}}$), -mais différent de tous les $a_\xi$ pour $\xi<\alpha$. Expliquer aussi -pourquoi il existe $a'$ qui soit de la forme $z \ast \tau_\alpha$ -(pour un certain $z \in \{0,1\}^{\mathbb{N}}$), mais différent de tous -les $b_\xi$ pour $\xi<\alpha$ et également différent du $b'$ qu'on -vient de trouver. +\textbf{(7)} En supposant donnés des éléments $(a_\xi)_{\xi<\alpha}$ +et $(b_\xi)_{\xi<\alpha}$ de $\{0,1\}^{\mathbb{N}}$, où $\alpha < +\mathfrak{c}$, déduire en une ligne des questions précédentes qu'il +existe $b'$ qui soit de la forme $\sigma_\alpha \ast y$ (pour un +certain $y \in \{0,1\}^{\mathbb{N}}$), mais différent de tous les +$a_\xi$ pour $\xi<\alpha$. Expliquer aussi pourquoi il existe $a'$ +qui soit de la forme $z \ast \tau_\alpha$ (pour un certain $z \in +\{0,1\}^{\mathbb{N}}$), mais différent de tous les $b_\xi$ +pour $\xi<\alpha$ et également différent du $b'$ qu'on vient de +trouver. \begin{corrige} On pose $b' = \sigma_\alpha \ast y$, où l'existence de $y$ a été @@ -814,6 +816,265 @@ plus généralemnt boréliennes de $\{0,1\}^{\mathbb{N}}$. Ici on doit conclure que la partie $A$ n'est pas borélienne. \end{corrige} +% +% +% + +\begin{otherlanguage}{english} + +\vskip1in\penalty-1000 + +\centerline{\hbox to2truein{\hrulefill}} +\centerline{\textbf{English translation}} + +\footnotesize + +(This translation is provided to help understand the French version, +but the French remains the only official text and should be referred +to in case of ambiguity or doubt, as this translation has not been +checked carefully.) + +\medbreak + +\textbf{Exercise \ref{normal-form-games-exercise}.} + +\textbf{(1)} Consider the zero-sum symmetric normal form game defined +by the following payoff matrix: +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors\\\hline +Rock&$0$&$-1$&$+1$\\ +Paper&$+1$&$0$&$-1$\\ +Scissors&$-1$&$+1$&$0$\\ +\end{tabular} +\end{center} +(Only Alice's payoff has been entered in each cell because the two +players' payoffs are opposite.) + +What are all the Nash equilibria of this game? + +\textbf{(2)} We now want to add a new option “Foobar” to the above +game, that is, we consider the game in normal form (still symmetric +and zero-sum) defined by the payoff matrix: +\begin{center} +\begin{tabular}{r|cccc} +$\downarrow$Alice, Bob$\rightarrow$&Rock&Paper&Scissors&Foobar\\\hline +Rock&$0$&$-1$&$+1$&$-x$\\ +Paper&$+1$&$0$&$-1$&$-y$\\ +Scissors&$-1$&$+1$&$0$&$-z$\\ +Foobar&$x$&$y$&$z$&$0$\\ +\end{tabular} +\end{center} +(The following three sub-questions are independent.) + +\textbf{\hphantom{(2)} (a)} Under what (necessary and sufficient) +condition on $x,y,z$ are the Nash equilibria found in (1) still Nash +equilibria for this new game?\quad\textbf{(b)} Under what (necessary +and sufficient) condition on $x,y,z$ is there a Nash equilibrium where +both players play the Foobar option (with +certainty)?\quad\textbf{(c)} Under what (necessary and sufficient) +condition on $x,y,z$ is there a Nash equilibrium where both players +play $\frac{1}{2}\text{Rock} + \frac{1}{2}\text{Foobar}$ (i.e., Rock +or Foobar each with probability $\frac{1}{2}$)? + +\textbf{(3)} We change the game: we now use the payoff matrix written +in (1), but this time the payoffs of the two players will be equal +instead of opposite (so it is no longer a zero-sum game! the players +are allies and no longer adversaries). The table gives the value of +the common payoff for both players. + +\textbf{\hphantom{(3)} (a)} Show that the Nash equilibria found in (1) +are still Nash equilibria of this new game. \quad\textbf{(b)} Give at +least one Nash equilibrium different from these. Comment briefly on +the possible difference in payoff between the Nash equilibria found in +(a) and (b). + +\medbreak + +\textbf{Exercise \ref{modified-nim-exercise}.} + +In this exercise, we consider the following game: + +Alice and Bob have piles of tokens in front of them, which represent +the state of the game (= the position). Each pile contains a finite +number (natural numbers) of tokens. The piles are numbered by natural +numbers, but only a finite number are non-empty (i.e., have $>0$ +tokens). To represent the position mathematically, we will use the +list $(n_0, n_1, n_2, \ldots, n_k)$ where $n_i$ is the number of +tokens in pile numbered i, and this implicitly means that all piles +$\geq k$ are empty. A player's move consists of removing exactly one +token from a given pile $i$ of their choice, and adding as many tokens +as they wish (including zero) to each of the piles $j<i$, including +adding different numbers to different piles. For example, from +position $(0,3,2)$ one can play to $(42,1000,1)$ or to $(0,2,2)$ or to +$(696\,729\,600,2,2)$. + +As usual, the player who cannot play has lost, meaning the one who +takes the last token has won. + +\medskip + +\textbf{(1)} Show that the game just defined necessarily ends in a +finite number of moves, regardless of the initial position and +regardless of the moves made by the players. (Careful justification +is required here.) + +\textbf{Definition:} Let us call a position “totally even” when the +number $n_i$ of tokens in each pile is even, and “not totally even” +when least one of the $n_i$ is odd. + +\textbf{(2)} Show that any move played from a totally even position +necessarily leads to a not totally even position. + +\textbf{(3)} Show that from any not totally even position there is at +least one move leading to a totally even position. + +\textbf{(4)} Deduce which positions in the game the first player has a +winning strategy, and which ones the second player has one. (Very +careful justification is required.) + +\textbf{(5)} Calculate, as a function of $n$, the Grundy value of +position $(n)$ (i.e., if there is only the pile numbered $0$, and +if it contains $n$ tokens). + +\textbf{(6)} Deduce the Grundy value of the positions $(0,1)$ and +$(1,1)$, then more generally of $(n,1)$ as a function of $n$. + +\textbf{(7)} Deduce the Grundy value of the positions $(0,2)$ and +$(1,2)$, and more generally of $(n_0,n_1)$ as a function of $n_0,n_1$. + +\textbf{(8)} Deduce the Grundy value of the position $(0,0,1)$. + +\textbf{(9)} Conjecture a general formula for the Grundy value +of any position $(n_0,n_1,\ldots,n_k)$. + +\textbf{(10)} Prove this formula. (This question is more difficult, +and it may be appropriate to save it for the end. One can draw +inspiration from the proof given in class of the calculation of the +Grundy value for the game of nim.) + +\medbreak + +\textbf{Exercise \ref{indeterminacy-exercise}.} + +In this exercise, we aim to show that there exists a game $A \subseteq +\{0,1\}^{\mathbb{N}}$ such that the Gale-Stewart game $G(A) := +G_{\{0,1\}}(A)$ is not determined (i.e., such that neither player has +a winning strategy). + +(The proof has been divided into questions allowing short answers, +sometimes as short as a single line.) + +\medskip + +\textbf{(1)} Show that there exists a bijection $h_{\mathrm{A}}$ +(resp. $h_{\mathrm{B}}$) between $\{0,1\}^{\mathbb{N}}$ and the set of +Alice's (resp. Bob's) strategies in the game $G(A)$. (\emph{Hint:} one +can quickly explain why there exists a bijection between $\mathbb{N}$ +and the set of positions where it is Alice's, or Bob's, turn to play.) + +\textbf{(2)} We \emph{admit} that there exists a well-ordering +relation $\preceq$ on $\{0,1\}^{\mathbb{N}}$. Deduce that there +exists an ordinal $\gamma$ and a bijection $\xi \mapsto u_\xi$ between +the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$ and the +set $\{0,1\}^{\mathbb{N}}$ (in other words, the $u_\xi$ are pairwise +distinct and $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$). + +\textbf{(3)} Explain in one line why there exists a smallest +ordinal $\gamma$ such that there exists a surjection $\xi \mapsto u_\xi$ +from the set $\{\xi < \gamma\}$ of ordinals smaller than $\gamma$ +to the set $\{0,1\}^{\mathbb{N}}$. + +\textbf{Definition:} We will denote $\mathfrak{c}$ the ordinal whose +existence we just justified, i.e., the smallest $\gamma$ such that we +can write $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ for a +certain function $\xi \mapsto u_\xi$, which we fix in the +following. + +\textbf{(4)} \textbf{(a)} If $(v_\xi)_{\xi<\alpha}$ are any elements +of $\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, explain in +one line why there exists an element $x$ of $\{0,1\}^{\mathbb{N}}$ +different from all the $v_\xi$.\quad\textbf{(b)} If $w$ is also an +element of $\{0,1\}^{\mathbb{N}}$, explain why we can find $x$ that is +different from $w$ (and still different from the $v_\xi$). + +\textbf{Definition:} If $\sigma$ is a strategy for Alice in the game +$G(A)$ and $y \in \{0,1\}^{\mathbb{N}}$, we denote by $\sigma \ast y$ +the confrontation in which Alice plays according to $\sigma$ and Bob +plays simply the successive terms of $y$ (independently of what Alice +does; i.e.,\footnote{To remove any doubt: $\sigma \ast y$ is the +sequence $(t_n)_{n\in\mathbb{N}}$ defined by induction by: $t_{2m} = +\sigma((t_0,\ldots,t_{2m-1}))$ and $t_{2m+1} = y_m$.} $\sigma \ast y$ +is a binary sequence whose sequence of odd terms, those played by Bob, +is given by $y$, while Alice plays the even terms according to the +strategy $\sigma$). Symmetrically, if $\tau$ is a strategy for Bob +and $z \in \{0,1\}^{\mathbb{N}}$, we define $z \ast \tau$ as the +confrontation in which Alice plays the terms of the sequence $z$ and +Bob plays according to $\tau$. + +\textbf{(5)} If $\sigma$ is a strategy for Alice, explain in one line +why the function $y \mapsto \sigma \ast y$ (from +$\{0,1\}^{\mathbb{N}}$ to $\{0,1\}^{\mathbb{N}}$) is injective. + +\textbf{(6)} If $(a_\xi)_{\xi<\alpha}$ are any elements of +$\{0,1\}^{\mathbb{N}}$, where $\alpha < \mathfrak{c}$, deduce from +(4)(a) and (5) that there exists $y \in \{0,1\}^{\mathbb{N}}$ such +that $\sigma \ast y$ is different from all $a_\xi$ for $\xi<\alpha$. + +\textbf{Assumption:} In questions (7) to (9), we assume that +$(\sigma_\xi)_{\xi<\mathfrak{c}}$ are strategies for Alice and +$(\tau_\xi)_{\xi<\mathfrak{c}}$ are strategies for Bob. We will +define them after question (9), but we don't need to know more about +them for now. + +\textbf{(7)} Assuming we are given elements $(a_\xi)_{\xi<\alpha}$ and +$(b_\xi)_{\xi<\alpha}$ of $\{0,1\}^{\mathbb{N}}$, where $\alpha < +\mathfrak{c}$, deduce in one line from the previous questions that +there exists $b'$ which is of the form $\sigma_\alpha \ast y$ (for +some $y \in \{0,1\}^{\mathbb{N}}$), but different from all $a_\xi$ for +$\xi<\alpha$. Also explain why there exists $a'$ that is of the form +$z \ast \tau_\alpha$ (for some $z \in \{0,1\}^{\mathbb{N}}$), but +different from all $b_\xi$ for $\xi<\alpha$ and also different from +the $b'$ that we have just found. + +We will admit that it poses no problem to \emph{choose} such $a'$ and +$b'$ as a function of all the other parameters. + +\textbf{(8)} Deduce from all of the above that there exist $(a_\xi)_{\xi +< \mathfrak{c}}$ and $(b_\xi)_{\xi < \mathfrak{c}}$ such that: +\begin{itemize} +\item none of the $a_\xi$ is equal to any of the $b_\zeta$ (i.e., for +all $\xi<\mathfrak{c}$ and all $\zeta<\mathfrak{c}$, we have $a_\xi +\neq b_\zeta$), +\item for all $\xi < \mathfrak{c}$, there exists $y \in +\{0,1\}^{\mathbb{N}}$ such that $b_\xi = \sigma_\xi \ast y$, +\item for all $\xi < \mathfrak{c}$, there exists $z \in +\{0,1\}^{\mathbb{N}}$ such that $a_\xi = z \ast \tau_\xi$. +\end{itemize} +(This is all we will need to know for the following questions.) + +\textbf{Definition:} Let us now call $A = \{a_\xi : \xi < +\mathfrak{c}\}$ the set of the $a_\xi$ that we just constructed +in (8). + +\textbf{(9)} Show that, for all $\xi$, the strategy $\tau_\xi$ is not +a winning one for Bob in the game $G(A)$. Show that the strategy +$\sigma_\xi$ is not a winning one for Alice in this same game (note: +this is not completely symmetric since $A$ is the set of $a_\alpha$). + +\textbf{Definition:} Now let $\sigma_\xi := h_{\mathrm{A}}(u_\xi)$ +where $h_{\mathrm{A}}$ was defined in (1) and $u_\xi$ in (3), and +similarly $\tau_\xi := h_{\mathrm{B}}(u_\xi)$. + +\textbf{(10)} Show that neither Alice nor Bob have a winning strategy +in the game $G(A)$. + +\textbf{(11)} Why doesn't this contradict the results seen in class? +What can be said about the subset $A$? + +\end{otherlanguage} + + % |