%% 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 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}
