%% This is a LaTeX document. Hey, Emacs, -*- latex -*- , get it? \documentclass[12pt,a4paper]{article} \usepackage[a4paper,margin=2.5cm]{geometry} \usepackage[french]{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}{Whatever} \newcommand\thingy{% \refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} } \newcommand\exercise{% \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}}} % \renewcommand{\thefootnote}{\fnsymbol{footnote}} % \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 \corrigefalse \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{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} \else \title{CSC-4MI06-TP / MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} \date{2025-06-26} \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 \textcolor{red}{XXX} pages (page de garde incluse). \else Cet énoncé comporte \textcolor{red}{XXX} 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 % % % \exercise \textbf{(1)} On considère le jeu en forme normale symétrique à somme nulle défini par la matrice de gains suivante : \begin{center} \begin{tabular}{r|ccc} $\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux\\\hline Pierre&$\hphantom{+}0$&$-1$&$+1$\\ Papier&$+1$&$\hphantom{+}0$&$-1$\\ Ciseaux&$-1$&$+1$&$\hphantom{+}0$\\ \end{tabular} \end{center} (Seul le gain d'Alice a été inscrit dans chaque case car les gains des deux joueurs sont opposés.) Rappeler brièvement quels sont tous les équilibres de Nash de ce jeu. \smallskip \textbf{(2)} On souhaite maintenant ajouter une nouvelle option au jeu ci-dessus, c'est-à-dire qu'on considère le jeu en forme normale (toujours symétrique et à somme nulle) défini par la matrice de gains : \begin{center} \begin{tabular}{r|cccc} $\downarrow$Alice, Bob$\rightarrow$&Pierre&Papier&Ciseaux&Foobar\\\hline Pierre&$0$&$-1$&$+1$&$-x$\\ Papier&$+1$&$0$&$-1$&$-y$\\ Ciseaux&$-1$&$+1$&$0$&$-z$\\ Foobar&$x$&$y$&$z$&$0$\\ \end{tabular} \end{center} (Les trois sous-questions qui suivent sont indépendantes.) \textbf{\hphantom{(2)} (a)} À quelle condition (nécessaire et suffisante) sur $x,y,z$ les équilibres de Nash trouvés en (1) sont-ils encore des équilibres de Nash pour ce nouveau jeu ?\quad\textbf{(b)} À quelle condition (nécessaire et suffisante) sur $x,y,z$ y a-t-il un équilibre de Nash où les deux joueurs jouent l'option Foobar (de façon certaine) ?\quad\textbf{(c)} À quelle condition (nécessaire et suffisante) sur $x,y,z$ y a-t-il un équilibre de Nash où les deux joueurs jouent Pierre ou Foobar chacun avec probabilité $\frac{1}{2}$ ? \smallskip \textbf{(3)} On reprend maintenant la matrice de gains écrite en (1), mais cette fois les gains des deux joueurs seront \emph{égaux} au lieu d'être opposés (ce n'est donc plus un jeu à somme nulle !), le tableau donnant la valeur du gain commun aux deux joueurs. \textbf{\hphantom{(3)} (a)} Montrer que les équilibres de Nash trouvés en (1) sont encore des équilibres de Nash de ce nouveau jeu.\quad\textbf{(b)} Donner au moins un équilibre de Nash différent de ceux-ci. % % % \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. Les piles sont numérotées $0$, $1$, $2$, etc. Chaque pile contient un certain nombre fini (entier naturel) de jetons. Il n'y a qu'un nombre fini de piles non vides (c'est-à-dire, ayant un nombre non-nul de jetons). Pour représenter la position mathématiquement, on utilisera la liste $(n_0, n_1, n_2, \ldots, n_{k-1})$ où $n_i$ est le nombre de jetons de la pile numérotée $i$, et où ceci signifie implicitement que toutes les piles $\geq k$ sont vides. Un coup d'un joueur consiste à retirer \emph{exactement un} jeton d'une certaine pile $i$, de son choix, et d'ajouter \emph{autant qu'il le souhaite} (y compris $0$) jetons à chacune des piles $j\epsilon$ tel que $\eta = \omega^\eta$. % % % \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) := G_{\{0,1\}}(A)$ ne soit pas déterminé (i.e., tel qu'aucun des deux joueurs n'ait de stratégie gagnante). (La démonstration a été découpées en questions admettant des réponses très courtes, parfois d'une seule ligne. Aucune ne demande de raisonnement compliqué.) \textbf{(1)} Montrer qu'il existe une bijection $h_{\mathrm{A}}$ (resp. $h_{\mathrm{B}}$) entre $\{0,1\}^{\mathbb{N}}$ et l'ensemble des stratégies d'Alice (resp. de Bob) au jeu $G(A)$. (\emph{Indication :} on pourra expliquer rapidement pourquoi il existe une bijection entre $\mathbb{N}$ et l'ensemble des positions où c'est à Alice, resp. à Bob, de jouer.) \textbf{(2)} On \emph{admet}\footnote{Plus généralement, on peut montrer qu'il existe une relation de bon ordre sur n'importe quel ensemble (théorème du bon ordre).} qu'il existe une relation de bon ordre $\preceq$ sur $\{0,1\}^{\mathbb{N}}$. En déduire qu'il existe un ordinal $\gamma$ et une bijection $\xi \mapsto u_\xi$ entre l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$ et l'ensemble $\{0,1\}^{\mathbb{N}}$ (autrement dit, les $u_\xi$ sont deux à deux distincts et $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$). \textbf{(3)} Expliquer en une ligne, pourquoi il existe un plus petit ordinal $\gamma$ tel qu'il existe une surjection $\xi \mapsto u_\xi$ de l'ensemble $\{\xi < \gamma\}$ des ordinaux plus petits que $\gamma$ sur l'ensemble $\{0,1\}^{\mathbb{N}}$. \textbf{Définition :} On notera $\mathfrak{c}$ l'ordinal dont on vient de justifier l'existence (i.e., le plus petit $\gamma$ tel qu'on puisse écrire $\{u_\xi : \xi < \gamma\} = \{0,1\}^{\mathbb{N}}$ pour une certaine fonction $\xi \mapsto u_\xi$). \textbf{(4)} Si $(v_\xi)_{\xi<\alpha}$ sont des éléments quelconques de $\{0,1\}^{\mathbb{N}}$, où $\alpha < \mathfrak{c}$, expliquer en une ligne pourquoi il existe un élément de $\{0,1\}^{\mathbb{N}}$ différent de tous les $v_\xi$. \textbf{Définition :} Si $\sigma$ est une stratégie d'Alice au jeu $G(A)$ et $y \in \{0,1\}^{\mathbb{N}}$, on note $\sigma \ast y$ la confrontation dans laquelle Alice joue selon $\sigma$ et Bob joue simplement les termes successifs de $y$ (indépendamment de ce que fait Alice ; i.e., $\sigma \ast y$ est une suite binaire dont la suite des termes impairs, ceux joués par Bob, est donnée par $y$, tandis qu'Alice joue les termes pairs selon la stratégie $\sigma$). \textbf{(5)} Si $\sigma$ est une stratégie d'Alice, expliquer en une ligne pourquoi la fonction $y \mapsto \sigma \ast y$ (de $\{0,1\}^{\mathbb{N}}$ vers $\{0,1\}^{\mathbb{N}}$) est injective. \textbf{(6)} Si $(a_\xi)_{\xi<\alpha}$ sont des éléments quelconques de $\{0,1\}^{\mathbb{N}}$ où $\alpha < \mathfrak{c}$, déduire de (4) et (5) pourquoi il existe $y \in \{0,1\}^{\mathbb{N}}$ tel que $\sigma \ast y$ soit différent de tous les $a_\xi$. \textbf{Supposition :} Dans les questions (7) à (8), on suppose que $(\sigma_\xi)_{\xi<\mathfrak{c}}$ sont des stratégies d'Alice et $(\tau_\xi)_{\xi<\mathfrak{c}}$ des stratégies de Bob. On les définira après la question (8), 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 des questions précédentes qu'il existe $b_\alpha$ qui soit de la forme $\sigma_\alpha \ast y$ (pour un certain $y \in \{0,1\}^{\mathbb{N}}$), mais qui soit différent de tous les $a_\xi$ ; et, symétriquement, qu'il existe $a_\alpha$ 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$. On \emph{admettra} qu'il ne pose pas de problème pour choisir\footnote{Ceci constitue une utilisation de l'axiome du choix (qui a d'ailleurs déjà été utilisé dans ce qu'on a admis à la question (2)).} de tels $a_\alpha$ et $b_\alpha$. \textbf{(8)} Déduire de tout ce qui précède qu'il existe $(a_\xi)_{\xi < \mathfrak{c}}$ et $(b_\xi)_{\xi < \mathfrak{c}}$ tels que : \begin{itemize} \item aucun des $a_\xi$ n'est égal à aucun des $b_\zeta$, \item pour tout $\xi < \mathfrak{c}$, on a $b_\xi = \sigma_\xi \ast y$ pour un certain $y \in \{0,1\}^{\mathbb{N}}$, \item pour tout $\xi < \mathfrak{c}$, on a $a_\xi = z \ast \tau_\xi$ pour un certain $z \in \{0,1\}^{\mathbb{N}}$. \end{itemize} (C'est tout ce qu'on aura besoin de savoir pour la suite.) \textbf{Définitions :} Posons maintenant $\sigma_\xi := h_{\mathrm{A}}(u_\xi)$ où $h_{\mathrm{A}}$ a été définie en (1) et $u_\xi$ en (3), et de même $\tau_\xi := h_{\mathrm{B}}(u_\xi)$. On pose enfin $A = \{a_\xi : \xi < \mathfrak{c}\}$ l'ensemble des $a_\xi$ qu'on vient de construire en (8). \textbf{(9)} Montrer que, quel que soit $\xi$, la stratégie $\sigma_\xi$ n'est pas gagnante pour Alice au jeu $G(A)$. Montrer que la stratégie $\tau_\xi$ n'est pas gagnante pour Bob à ce même jeu (attention, ce n'est pas exactement symétrique vu que $A$ est l'ensemble des $a_\alpha$). \textbf{(10)} Déduire de tout ce qui précède que ni Alice ni Bob n'ont de stratégie gagnante au jeu $G(A)$. \textbf{(11)} Pourquoi ceci ne contredit pas les résultats vu en cours ? % % % \end{document}