%% 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]
%
\newenvironment{qcm}{\relax}{\relax}
\newenvironment{qvar}{\relax}{\relax}
\newcounter{quescnt}
\newenvironment{question}%
{\stepcounter{quescnt}\bigskip\noindent\textbf{Question~\arabic{quescnt}.}\par\nobreak}
{\relax}
\newcounter{answcnt}[quescnt]
\newcommand\answer{%
\stepcounter{answcnt}\smallskip\textbf{(\Alph{answcnt})}~}
\let\rightanswer=\answer
%
\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}
%
\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\\Échantillon de questions — Corrigé\\{\normalsize Théories des jeux}}
\else
\title{MITRO206\\Échantillon de questions\\{\normalsize Théories des jeux}}
\fi
\author{}
\date{26 juin 2020}
\maketitle

\pretolerance=8000
\tolerance=50000

\vskip1truein\relax

\noindent\textbf{Consignes.}

Ce contrôle de connaissances est un QCM (questionnaire à choix
multiples).  Chaque question admet une unique réponse correcte.  Les
questions sont totalement indépendantes les unes des autres (mais
certaines peuvent se ressembler).  La sélection des questions et
l'ordre ont été tirés aléatoirement et n'obéissent donc à aucune
logique particulière.

La réponse est attendue sous forme d'une liste de numéros de question
suivie de la réponse proposée : par exemple, « \verb=1A 2B 4D= » pour
signifier que la réponse proposée à la question 1 est (A), la réponse
proposée à la question 2 est (B), et la réponse proposée à la
question 4 est (D).

Une réponse incorrecte sera (possiblement jusqu'à deux fois) plus
fortement pénalisée qu'une absence de réponse : il est donc préférable
de ne pas répondre à une question que de répondre aléatoirement.

\medbreak

Durée : 1h de 17h30 à 18h30

\vfill

%% \noindent
%% Sujet généré pour : \texttt{\seedval}

\medskip

{\tiny\noindent
\immediate\write18{sh ./vc > vcline.tex}
Git: \input{vcline.tex}
\immediate\write18{echo ' (stale)' >> vcline.tex}
\par}

\pagebreak

\begin{qcm}

\begin{question}

Auquel ordinaux suivants est égal $2^{\omega^2}$ (lire : $2$ puissance
$\omega^2$) ?

\answer
$\omega^{\omega^\omega}$

\rightanswer
$\omega^\omega$

\answer
$\omega^{\omega^2}$

\answer
$\omega^2$

\answer
$\omega$

\end{question}

\begin{corrige}
On a $2^{\omega^2} = 2^{\omega\times\omega} = (2^\omega)^\omega =
\omega^\omega$, donc réponse \textbf{(B)}.
\end{corrige}


%
%
%

\begin{question}

Considérons le jeu à somme nulle, symétrique, entre Alice et Bob, dont
la matrice des gains est donnée par le tableau suivant (Alice choisit
la ligne, Bob choisit la colonne, le tableau donne le gain d'Alice et
le gain de Bob est l'opposé de la valeur indiquée) :

\begin{center}
\begin{tabular}{r|rrrrr}
$\downarrow$Alice, Bob$\rightarrow$&U&V&W&X&Y\\\hline
U&$0$&$+2$&$0$&$-2$&$+1$\\
V&$-2$&$0$&$+1$&$+1$&$+2$\\
W&$0$&$-1$&$0$&$+1$&$+1$\\
X&$+2$&$-1$&$-1$&$0$&$+2$\\
Y&$-1$&$-2$&$-1$&$-2$&$0$\\
%% m = Matrix(QQ, 5, 5, [[0, 2, 0, -2, 1], [-2, 0, 1, 1, 2], [0, -1, 0, 1, 1], [2, -1, -1, 0, 2], [-1, -2, -1, -2, 0]])
\end{tabular}
\end{center}

Laquelle des réponses suivantes est une stratégie optimale à ce jeu ?
(Chaque réponse proposée est la liste des probabilités de jouer les
options U,V,W,X,Y dans cet ordre.)

\answer
$(\frac{1}{3}, \frac{1}{3}, 0, \frac{1}{3}, 0)$

\answer
$(0, \frac{1}{2}, 0, \frac{1}{2}, 0)$

\answer
$(0, 0, 0, 0, 1)$

\rightanswer
$(\frac{1}{5}, \frac{2}{5}, 0, \frac{2}{5}, 0)$

\end{question}

\begin{corrige}
Dans un jeu à somme nulle, les équilibres de Nash sont exactement les
paires de stratégies optimales.  Ici le jeu est symétrique, donc les
stratégies optimales seront les mêmes pour les deux joueurs et la
valeur $v$ du jeu sera $0$.  Pour vérifier qu'une stratégie est
optimale, il s'agit donc de vérifier que si les deux joueurs la joue,
aucun ne peut faire mieux en jouant une stratégie pure différente.  On
calcule donc les combinaisons des lignes du tableau dont les
coefficients sont donnés par les probabilités dans les différentes
réponses, et la seule dont toutes les valeurs sont $\geq v$ est
$(\frac{1}{5}, \frac{2}{5}, 0, \frac{2}{5}, 0)$.
Réponse \textbf{(D)}.
\end{corrige}


%
%
%

\begin{question}

On considère le jeu combinatoire (impartial, à information parfaite)
associé au graphe orienté acyclique représenté ci-dessous, la position
de départ étant notée $s$ :

\begin{center}
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (n00) at (0bp,0bp) [draw,circle] {};
\node (n01) at (40bp,0bp) [draw,circle] {};
\node (n02) at (80bp,0bp) [draw,circle] {};
\node (n10) at (0bp,-40bp) [draw,circle] {};
\node (n11) at (40bp,-40bp) [draw,circle] {};
\node (n12) at (80bp,-40bp) [draw,circle] {};
\node (n20) at (0bp,-80bp) [draw,circle] {};
\node (n21) at (40bp,-80bp) [draw,circle] {};
\node (n22) at (80bp,-80bp) [draw,circle] {$s$};
\draw[->] (n01) -- (n00);  \draw[->] (n02) -- (n01);
\draw[->] (n11) -- (n10);  \draw[->] (n12) -- (n11);
\draw[->] (n21) -- (n20);  \draw[->] (n22) -- (n21);
\draw[->] (n10) -- (n00);  \draw[->] (n20) -- (n10);
\draw[->] (n11) -- (n01);  \draw[->] (n21) -- (n11);
\draw[->] (n12) -- (n02);  \draw[->] (n22) -- (n12);
\end{tikzpicture}
\end{center}

Quelle est la valeur de Grundy du jeu (i.e., celle de la
position $s$) ?

\answer
$4$

\answer
$2$

\rightanswer
$0$

\answer
$1$

\answer
$3$

\end{question}

\begin{corrige}
On calcule les valeurs de Grundy de proche en proche (c'est-à-dire par
induction bien-fondée), la valeur de Grundy d'une position étant le
mex (= plus petite valeur exclue) des valeurs de Grundy de ses voisins
sortants.  On trouve

\begin{center}
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (n00) at (0bp,0bp) [draw,circle] {$0$};
\node (n01) at (40bp,0bp) [draw,circle] {$1$};
\node (n02) at (80bp,0bp) [draw,circle] {$0$};
\node (n10) at (0bp,-40bp) [draw,circle] {$1$};
\node (n11) at (40bp,-40bp) [draw,circle] {$0$};
\node (n12) at (80bp,-40bp) [draw,circle] {$1$};
\node (n20) at (0bp,-80bp) [draw,circle] {$0$};
\node (n21) at (40bp,-80bp) [draw,circle] {$1$};
\node (n22) at (80bp,-80bp) [draw,circle] {$0$};
\draw[->] (n01) -- (n00);  \draw[->] (n02) -- (n01);
\draw[->] (n11) -- (n10);  \draw[->] (n12) -- (n11);
\draw[->] (n21) -- (n20);  \draw[->] (n22) -- (n21);
\draw[->] (n10) -- (n00);  \draw[->] (n20) -- (n10);
\draw[->] (n11) -- (n01);  \draw[->] (n21) -- (n11);
\draw[->] (n12) -- (n02);  \draw[->] (n22) -- (n12);
\end{tikzpicture}
\end{center}

La réponse correcte est donc \textbf{(C)}.
\end{corrige}


%
%
%

\begin{question}

Alice et Bob jouent au jeu de type Gale-Stewart suivant : chacun à son
tour choisit un chiffre binaire (soit $0$ soit $1$ : Alice choisit
$a_1$ puis Bob choisit $a_2$ puis Alice choisit $a_3$ et ainsi de
suite).  Au bout d'un nombre infini de tours, on considère le nombre
réel $x$ entre $0$ et $1$ dont l'écriture binaire fractionnaire est
formée de ces chiffres (c'est-à-dire $x = \sum_{i=1}^{+\infty}
a_i\,2^{-i}$, ou $0{.}a_1a_2a_3\ldots$ en écriture binaire) : si $x <
\frac{1}{3}$, Alice gagne, tandis que si $x \geq \frac{1}{3}$, Bob
gagne.  (À toutes fins utiles, on rappelle que $\frac{1}{3}$ s'écrit
$0{.}01010101\ldots$ en binaire.)  Que pensez-vous de ce jeu ?

\answer
un joueur a une stratégie gagnante, mais il est impossible de savoir
lequel

\rightanswer
Bob a une stratégie gagnante

\answer
Alice a une stratégie gagnante

\answer
aucun joueur n'a de stratégie gagnante

\end{question}

\begin{corrige}
On peut faire remarquer que $[\frac{1}{3};1]$ est fermé (ou plus
correctement, que l'ensemble des représentations binaires des réels
de $[\frac{1}{3};1]$ est fermé pour la topologie produit) pour se
convaincre qu'il existe forcément une stratégie gagnante pour au moins
un joueur, mais en fait peu importe : Alice va manifestement jouer $0$
à tous les coups et Bob jouer $1$ à tous les coups (on peut tracer le
début de l'arbre binaire infini des possibilités pour y voir plus
clair), si bien qu'on va tomber sur $\frac{1}{3}$ et Bob a une
stratégie gagnante.  Réponse \textbf{(B)}.
\end{corrige}


%
%
%

\end{qcm}

%
%
%
\end{document}