%% 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<i$.  Par
exemple, à partir de la position $(0,3,2)$ on peut notamment jouer
vers $(42,1000,1)$ ou bien vers $(0,2,2)$.

Comme d'habitude, le joueur qui ne peut pas jouer a perdu,
c'est-à-dire que celui qui prend le dernier jeton a gagné.

\textbf{(1)} Montrer que le jeu qu'on vient de définir termine
forcément en temps fini, quelle que soit la position initiale.  (On
justifiera soigneusement.)

Appelons « position totalement paire » une position dans laquelle le
nombre $n_i$ de jetons de chaque pile est pair.

\textbf{(2)} Montrer que tout coup joué depuis une position totalement
paire conduit nécessairement à une position qui n'est pas totalement
paire.

\textbf{(3)} Montrer que depuis toute position qui n'est pas
totalement paire il existe au moins un coup conduisant à une position
totalement paire.

\textbf{(4)} En déduire quelles sont les positions du jeu dans
lesquelles le premier joueur a une stratégie gagnante, et quelles sont
celles dans lesquelles le second joueur en a une.  (On justifiera très
soigneusement.)

\textbf{(5)} Calculer, en fonction de $n$, la valeur de Grundy de la
position $(n)$ (c'est-à-dire s'il n'y a que la pile numérotée $0$, et
qu'elle comporte $n$ jetons).

\textbf{(6)} En déduire la valeur de Grundy des posititions $(0,1)$ et
$(1,1)$, puis plus généralement de $(n,1)$ en fonction de $n$.

\textbf{(7)} En déduire la valeur de Grundy des positions $(0,2)$ et
$(1,2)$, plus plus généralement de $(n_0,n_1)$ en fonction
de $n_0,n_1$.

\textbf{(8)} En déduire la valeur de Grundy de la position $(0,0,1)$.

\textbf{(9)} Conjecturer une formule générale pour la valeur de Grundy
d'une position $(n_0,n_1,\ldots,n_{k-1})$ quelconque.

\textbf{(10)} Démontrer cette formule.


%
%
%

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