%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
\documentclass[12pt,a4paper]{article}
\usepackage[a4paper,margin=2.5cm]{geometry}
\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]
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\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}}}
%
\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
\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\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}}
\else
\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}}
\fi
\author{}
\date{17 avril 2023}
\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.

La longueur du sujet ne doit pas effrayer : l'énoncé est long parce
que des rappels ont été faits et que la rédaction des questions
cherche à éviter toute ambiguïté.  De plus, il ne sera pas nécessaire
de traiter la totalité pour avoir la note maximale.

\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

Barème \emph{indicatif} : $5+5+5+7$ (sur $20$)

\ifcorrige
Ce corrigé comporte 8 pages (page de garde incluse).
\else
Cet énoncé comporte 4 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


%
%
%

\exercice

On considère le jeu de nim éventuellement transfini.  (On rappelle
qu'il est défini de la manière suivante : une position du jeu est un
tuple $(\alpha_1,\ldots,\alpha_r)$ d'ordinaux, on dit qu'il y a
« $\alpha_i$ bâtonnets sur la ligne $i$ », et un coup consiste à
décroître strictement \emph{un et un seul} des $\alpha_i$, autrement
dit il existe un coup de $(\alpha_1,\ldots,\alpha_r)$ vers
$(\alpha_1,\ldots,\beta,\ldots,\alpha_r)$ où $\beta<\alpha_i$ est mis
à la place de $\alpha_i$.)

Pour chacune des positions suivantes, dire si c'est une position P
(c'est-à-dire gagnante pour le joueur qui vient de jouer) ou N
(c'est-à-dire gagnante pour le joueur qui doit jouer), et, dans ce
dernier cas, donner un coup gagnant possible pour le joueur en
question.

(a) $(1,2,3)$ (autrement dit, une ligne avec $1$ bâtonnet, une ligne
avec $2$, et une ligne avec $3$)

\begin{corrige}
On a $1 = 2^0$ et $2 = 2^1$ et $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ si
bien que $1 \oplus 2 \oplus 3 = 0$ : la valeur de Grundy de la
position est $0$, et c'est donc une position P.
\end{corrige}

(b) $(3,6,9)$

\begin{corrige}
On a $3 = 2^1 + 2^0 = 2^1 \oplus 2^0$ et $6 = 2^2 + 2^1 = 2^2 \oplus
2^1$ et $9 = 2^3 + 2^0 = 2^3 \oplus 2^0$ si bien que $3 \oplus 6
\oplus 9 = 2^3 \oplus 2^2 = 2^3 + 2^2 = 12$ : la valeur de Grundy de
la position est $12$, et c'est donc une position N.

Pour trouver un coup gagnant, c'est-à-dire un coup vers une
position P, on cherche à annuler la valeur de Grundy : autrement dit,
on cherche à remplacer le nombre $n$ de bâtonnets d'une ligne par $n
\oplus 12$, et il s'agit donc de trouver une ligne telle que $n \oplus
12 < n$.  On vérifie facilement que la seule possibilité est de
réduire la ligne ayant $9$ bâtonnets à $9 \oplus 12 = 2^2 + 2^0 = 5$
bâtonnets.  Bref, le seul coup gagnant est $(3,6,9) \to (3,6,5)$.
\end{corrige}

(c) $(\omega,\omega2,\omega3)$

\begin{corrige}
En se rappelant que $\omega = 2^{\omega}$, on a $\omega2 =
2^{\omega+1}$ et $\omega3 = 2^{\omega+1} + 2^{\omega}$ en binaire : on
a donc $\omega \oplus (\omega2) \oplus (\omega3) = 0$ : la valeur de
Grundy de la position est $0$, et c'est donc une position P.
\end{corrige}

(d) $(\omega,\omega^2,\omega^3)$

\begin{corrige}
En se rappelant de nouveau que $\omega = 2^{\omega}$, on a $\omega^2 =
2^{\omega2}$ et $\omega^3 = 2^{\omega3}$ en binaire : on a donc
$\omega \oplus \omega^2 \oplus \omega^3 = 2^{\omega3} + 2^{\omega2} +
2^\omega = \omega^3 + \omega^2 + \omega =: \gamma$ : la valeur de
Grundy de la position est $\gamma \neq 0$, et c'est cdonc une
position N.

Comme dans la question (b), on cherche à annuler la valeur de Grundy,
autrement dit remplacer le nombre $\alpha$ de bâtonnets d'une ligne
par $\alpha \oplus \gamma$ (où $\gamma = \omega^3 + \omega^2 +
\omega$, qu'il vaut mieux penser comme $2^{\omega3} \oplus 2^{\omega2}
\oplus 2^\omega$) d'une manière à ce que le résultat soit plus petit.
On vérifie facilement que la seule possibilité est de réduire la ligne
ayant $\omega^3$ bâtonnets à $\omega^3 \oplus \gamma = \omega^2 +
\omega$ bâtonnets.  Bref, le seul coup gagnant est
$(\omega,\omega^2,\omega^3) \to (\omega,\omega^2,\omega^2+\omega)$.
\end{corrige}

(e) $(\omega,\omega^\omega,\omega^{\omega^\omega})$

\begin{corrige}
En se rappelant une fois de plus que $\omega = 2^{\omega}$, on a
$\omega^\omega = (2^\omega)^\omega = 2^{\omega\times\omega} =
2^{\omega^2}$, et $\omega^{\omega^\omega} = (2^\omega)^{\omega^\omega}
= 2^{\omega\times \omega^{\omega}} = 2^{\omega^{1+\omega}} =
2^{\omega^\omega}$.  Le raisonnement est alors exactement analogue à
la question (d) (car la seule chose qui importe dans cette question
ait qu'on ait affaire à trois puissances de $2$ distinctes) : la
valeur de Grundy de la position est $\gamma := 2^{\omega^\omega} +
2^{\omega^2} + 2^\omega = \omega^{\omega^\omega} + \omega^\omega +
\omega \neq 0$ donc c'est une position N, et le seul coup gagnant est
$(\omega,\omega^\omega,\omega^{\omega^\omega}) \to
(\omega,\omega^\omega,\omega^\omega + \omega)$.
\end{corrige}

(f) $(\varepsilon_1, \varepsilon_2, \varepsilon_3)$ où $\varepsilon_0
< \varepsilon_1 < \varepsilon_2 < \varepsilon_3$ sont les quatre
premiers ordinaux\footnote{On peut définir $\varepsilon_{n+1}$ comme
  la limite, c'est-à-dire la borne supérieure, de la suite
  $(u_k)_{k<\omega}$ strictement croissante définie par $u_0 =
  (\varepsilon_n) + 1$ et $u_{k+1} = \omega^{u_k}$, c'est-à-dire $u_1
  = \omega^{(\varepsilon_n) + 1}$ et $u_2 =
  \omega^{\omega^{(\varepsilon_n) + 1}}$, etc., mais on n'aura pas
  besoin de ce fait.}  vérifiant $\varepsilon = \omega^\varepsilon$.

\begin{corrige}
Pour $i \in \{1,2,3\}$ (ou n'importe quel ordinal, en fait), on a
$\varepsilon_i = \omega^{\varepsilon_i} = (2^\omega)^{\varepsilon_i} =
2^{\omega\cdot\varepsilon_i} = 2^{\omega\cdot\omega^{\varepsilon_i}} =
2^{\omega^{1+\varepsilon_i}} = 2^{\omega^{\varepsilon_i}} =
2^{\varepsilon_i}$ (en utilisant au passage le fait, facilement
vérifié, que $1 + \rho = \rho$ quel que soit l'ordinal infini $\rho$).
Le raisonnement est alors exactement analogue aux questions (d) et (e)
(car la seule chose qui importe dans ces questions ait qu'on ait
affaire à trois puissances de $2$ distinctes) : la valeur de Grundy de
la position est $\gamma := 2^{\varepsilon_3} + 2^{\varepsilon_2} +
2^{\varepsilon_1} = \varepsilon_3 + \varepsilon_2 + \varepsilon_1 \neq
0$ donc c'est une position N, et le seul coup gagnant est
$(\varepsilon_1, \varepsilon_2, \varepsilon_3) \to (\varepsilon_1,
\varepsilon_2, \varepsilon_2 + \varepsilon_1)$.
\end{corrige}

(g) Donner un exemple de position N du jeu de nim (de préférence fini)
avec un nombre distinct de bâtonnets sur chaque ligne (i.e., les
$\alpha_i$ sont deux à deux distincts), où il existe strictement plus
qu'un coup gagnant pour le joueur qui doit jouer.  (Pour indication,
ceci est possible à partir de trois lignes de bâtonnets.)

\begin{corrige}
On cherche donc une position $(n_1,n_2,n_3)$ avec trois lignes de
bâtonnets, de valeur de Grundy $g := n_1 \oplus n_2 \oplus n_3$, telle
qu'au moins deux des trois quantités $n_i \oplus g$ soit strictement
inférieure au $n_i$ correspondant (le raisonnement étant expliqué à la
question (b)), en prenant note du fait que $n_1 \oplus g = n_2 \oplus
n_3$ et de façon analogue pour les trois autres.  On cherche donc, par
exemple, à avoir $n_1 \oplus n_3 < n_2$ et $n_1 \oplus n_2 < n_3$.
Ceci n'est pas difficile en prenant par exemple pour $n_1$ une
puissance de $2$ qui existe dans l'écriture binaire de $n_2$ et
de $n_3$ mais telle qu'en l'enlevant on obtienne des nombres
strictement plus petits.  Par exemple, la position $(2,6,7)$ (de
valeur de Grundy $2\oplus 6\oplus 7 = 3 =: g$) admet des coups
gagnants vers $(2,5,7)$ ou $(2,6,4)$ ou même $(1,6,7)$.
\end{corrige}


%
%
%

\exercice

Si $G$ est un graphe orienté bien-fondé (qu'on peut considérer comme
l'ensemble des positions d'un jeu combinatoire auquel il ne manque que
l'information, sans pertinence ici, de la position initiale), on
rappelle qu'on a défini la fonction rang
\[
\rk(x) := \sup\nolimits^+\{\rk(y) : y\in\outnb(x)\} = \sup\,\{\rk(y)+1 :
y\in\outnb(x)\}
\]
(en notant $\sup^+ S$ le plus petit ordinal strictement supérieur à
tous les ordinaux de $S$ et $\sup S$ le plus petit ordinal supérieur
ou égal à tous les ordinaux de $S$, et $\outnb(x)$ l'ensemble des
voisins sortants de $x$), et la fonction de Grundy
\[
\gr(x) := \mex\,\{\gr(y) : y\in\outnb(x)\}
\]
(où $\mex S$ désigne le plus petit ordinal qui n'est pas dans $S$),
— ces définitions ayant bien un sens par induction bien-fondée.  La
première mesure en quelque sorte la durée du jeu si les deux joueurs
coopèrent pour le faire durer aussi longtemps que possible, et la
seconde nous donne notamment l'information de quel joueur a une
stratégie gagnante.

On va maintenant définir une fonction qui mesure en quelque sorte la
durée du jeu si le joueur perdant cherche à perdre aussi lentement que
possible tandis que le joueur gagnant cherche à gagner aussi vite que
possible.  Précisément, on pose
\[
\left\{
\begin{array}{ll}
\dur(x) := \sup\,\{\dur(y)+1 : y\in\outnb(x)\}
&\;\;\text{si $\gr(x) = 0$}\\
\dur(x) := \min\,\{\dur(y)+1 : y\in\outnb(x)\text{~et~}\gr(y)=0\}
&\;\;\text{si $\gr(x) \neq 0$}\\
\end{array}
\right.
\]
(où $\min S$ désigne le plus petit ordinal de $S$, si $S$ est un
ensemble non-vide d'ordinaux).

(1) Expliquer pourquoi cette définition a bien un sens (on
prendra garde au fait que $\min\varnothing$ n'est pas défini).

\begin{corrige}
Lorsque $\gr(x) \neq 0$, il existe au moins un voisin sortant $y \in
\outnb(x)$ tel que $\gr(y) = 0$ (car le $\mex$ est la plus petite
valeur exclue: si un tel $y$ n'existait pas, le $\mex$ serait $0$) :
ceci assure que le $\min$ dans la deuxième ligne de la définition
porte toujours sur un ensemble non-vide.

En-dehors de ce fait, la définition ne pose pas de problème : le
$\sup$ d'un ensemble d'ordinaux existe toujours, et la récursivité de
la définition est légitime par induction bien-fondée, c'est-à-dire que
$\dur(x)$ peut faire appel aux valeurs de $\dur(y)$ pour des voisins
sortants $y$ de $x$.  (Le fait de faire appel à $\gr(y)$ n'est pas un
problème car on sait que $\gr$ est bien défini, et la distinction en
cas est légitime de toute manière.)
\end{corrige}

(2) Expliquer rapidement et informellement pourquoi $\dur(x)$
correspond bien à l'explication intuitive qu'on a donnée.

\begin{corrige}
Quand $x$ est une position avec $\gr(x) = 0$, c'est-à-dire une
position P, le joueur qui doit jouer est le joueur perdant (n'ayant
pas de stratégie gagnante) : il joue donc vers une position $y$ le
faisant perdre le plus lentement possible, c'est-à-dire avec $\dur(y)$
aussi grand que possible, d'où la définition $\dur(x) =
\sup\,\{\dur(y)+1 : y\in\outnb(x)\}$ dans ce cas (le $+1$ sert à
compter le coup joué par ce joueur).

Au contraire, lorsque $\gr(x) \neq 0$, c'est-à-dire que $x$ est une
position N, le joueur qui doit jouer est le joueur gagnant : il joue
donc vers une position $y$ le faisant gagner le plus rapidement
possible, c'est-à-dire avec $\dur(y)$ aussi petit que possible parmi
les coups $x\to y$ gagnants, autrement dit ceux pour lesquels $\gr(y)
= 0$, d'où la définition $\dur(x) = \min\,\{\dur(y)+1 :
y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\}$ dans ce cas (le $+1$ sert à
compter le coup joué par ce joueur).
\end{corrige}

(3) Sur le graphe $G$ représenté ci-dessous, calculer chacune des
fonctions $\rk$, $\gr$ et $\dur$ (les lettres servent simplement à
étiqueter les sommets) :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,circle] {A};
\node (nB) at (0bp,-40bp) [draw,circle] {B};
\node (nC) at (40bp,0bp) [draw,circle] {C};
\node (nD) at (40bp,-40bp) [draw,circle] {D};
\node (nE) at (80bp,0bp) [draw,circle] {E};
\node (nF) at (80bp,-40bp) [draw,circle] {F};
\node (nG) at (120bp,-40bp) [draw,circle] {G};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip
Si on joue à partir du sommet A comme position initiale et que, comme
suggéré dans la définition de $\dur$, le joueur perdant cherche à
perdre aussi lentement que possible tandis que le joueur gagnant
cherche à gagner aussi vite que possible, quelle sera le déroulement
du jeu ?

\begin{corrige}
Les sommets ont été fort sympathiquement étiquetés dans un ordre
compatible avec le rang (tri topologique), c'est-à-dire que chaque
arête pointe vers un sommet situé strictement après dans l'ordre
alphabétique.  On effectue donc les calculs dans l'ordre alphabétique
inversé.  On trouve, pour le rang :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,circle] {$4$};
\node (nB) at (0bp,-40bp) [draw,circle] {$3$};
\node (nC) at (40bp,0bp) [draw,circle] {$3$};
\node (nD) at (40bp,-40bp) [draw,circle] {$2$};
\node (nE) at (80bp,0bp) [draw,circle] {$2$};
\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip

Pour la valeur de Grundy :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,circle] {$0$};
\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
\node (nC) at (40bp,0bp) [draw,circle] {$1$};
\node (nD) at (40bp,-40bp) [draw,circle] {$0$};
\node (nE) at (80bp,0bp) [draw,circle] {$2$};
\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
\node (nG) at (120bp,-40bp) [draw,circle] {$0$};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip

Et pour la fonction $\dur$ (afin de rendre le calcul plus facile à
suivre, on a entouré en double les sommets de valeur de Grundy $0$) :

\begin{center}\footnotesize
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (nA) at (0bp,0bp) [draw,double,circle] {$4$};
\node (nB) at (0bp,-40bp) [draw,circle] {$1$};
\node (nC) at (40bp,0bp) [draw,circle] {$3$};
\node (nD) at (40bp,-40bp) [draw,double,circle] {$2$};
\node (nE) at (80bp,0bp) [draw,circle] {$1$};
\node (nF) at (80bp,-40bp) [draw,circle] {$1$};
\node (nG) at (120bp,-40bp) [draw,double,circle] {$0$};
\draw[->] (nA) -- (nB);
\draw[->] (nA) -- (nC);
\draw[->] (nB) -- (nD);
\draw[->] (nB) to[out=315,in=225] (nG);
\draw[->] (nC) -- (nD);
\draw[->] (nC) -- (nE);
\draw[->] (nD) -- (nF);
\draw[->] (nE) -- (nF);
\draw[->] (nF) -- (nG);
\draw[->] (nE) to[out=0,in=90] (nG);
\end{tikzpicture}
\end{center}
\vskip-\baselineskip

Si on joue à partir de la position A, le premier joueur, appelons-la
Alice, est en position perdante car la valeur de Grundy est nulle, et
va jouer vers C car c'est ce qui maximise la fonction $\dur$ ; son
adversaire, appelons-le Bob, joue alors vers D car c'est le seul coup
gagnant, après quoi Alice joue vers F (seul coup possible) et Bob joue
vers G.
\end{corrige}

(4) Montrer que, dans n'importe quel graphe $G$ bien-fondé, et pour
n'importe quel sommet $x$ de $G$, on a $\dur(x) \leq \rk(x)$.

\begin{corrige}
On montre par induction bien-fondée que $\dur(x) \leq \rk(x)$.  On
peut donc faire l'hypothèse qu'on sait que $\dur(y) \leq \rk(y)$ pour
tout voisin sortant $y \in \outnb(x)$ (hypothèse d'induction).  Dans
le cas où $\gr(x) = 0$, on a $\dur(x) = \sup\,\{\dur(y)+1 :
y\in\outnb(x)\}$, qui est $\leq \sup\,\{\rk(y)+1 : y\in\outnb(x)\}$
par hypothèse d'induction (il est clair qu'augmenter au sens large
tous les éléments d'un ensemble d'ordinaux augmente son $\sup$ au sens
large), et ceci vaut $\rk(x)$ par définition.  Dans le cas où $\gr(x)
\neq 0$, on a $\dur(x) = \min\,\{\dur(y)+1 :
y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 :
y\in\outnb(x)\;\text{~et~}\;\gr(y)=0\} \leq \sup\,\{\dur(y)+1 :
y\in\outnb(x)\}$ de façon évidente ($\min S \leq \sup S$ est clair),
et pour la même raison que précédemment, ceci est $\leq
\sup\,\{\rk(y)+1 : y\in\outnb(x)\} = \rk(x)$.
\end{corrige}


%
%
%

\exercice

Soit $G$ un graphe orienté dont l'ensemble des sommets est (au plus)
dénombrable, et soit $x_0$ un sommet de $G$.  (Il n'y a pas d'autre
hypothèse sur $G$, par exemple on ne suppose pas que $G$ est
bien-fondé.)

On considère le jeu suivant.  Deux joueurs s'affrontent, qu'on
appellera \emph{le Fugueur} et \emph{le Borneur}.  Le Fugueur
commence, après quoi ils jouent tour à tour.  En partant de $x_0$,
chaque joueur, quand vient son tour, choisit un voisin sortant de la
position actuelle $x$ \emph{ou bien} choisit de conserver $x$ ;
autrement dit, il choisit un élément de $\outnb(x) \cup \{x\}$.  (Pour
être parfaitement clair : au premier tour, le Fugueur choisit $x_1 \in
\outnb(x_0) \cup \{x_0\}$, puis le Borneur choisit $x_2 \in
\outnb(x_1) \cup \{x_1\}$, et ainsi de suite.)  Le jeu dure infiniment
longtemps (manifestement, les règles permettent toujours à chaque
joueur de faire un coup).  Au bout d'un nombre infini de coups, on
considère la suite $(x_n)_{n\in\mathbb{N}}$ de toutes les positions
traversées :
\begin{itemize}
\item si cette suite est d'image finie (c'est-à-dire que l'ensemble
  $\{x_n : n\in\mathbb{N}\}$ de toutes les positions traversées est
  fini), alors le Borneur a gagné ;
\item sinon, le Fugueur a gagné.
\end{itemize}

(1) Montrer, en appliquant un des résultats du cours, que l'un des
joueurs a nécessairement une stratégie gagnante (on ne demande pas de
préciser lequel).  On pourra préalablement montrer que pour toute
partie $F \subseteq G$, la partie $F^{\mathbb{N}} \subseteq
G^{\mathbb{N}}$ est \emph{fermée} (pour la topologie sur
$G^{\mathbb{N}}$ produit de la topologie
discrète\footnote{C'est-à-dire celle qui a été étudiée en cours.}), et
en déduire une propriété de l'ensemble
$\bigcup_{F\text{~fini~}\subseteq G} F^{\mathbb{N}}$ réunion des
$F^{\mathbb{N}}$ où $F$ parcourt toutes les parties \emph{finies}
de $G$.

\begin{corrige}
Pour commencer, montrons que si $F$ est une partie de $G$ alors
$F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée.  Ceci revient à
montrer que son complémentaire est ouvert, autrement dit, que si
$\dblunderline{x} \in G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$,
alors il existe un voisinage fondamental de $\dblunderline{x}$ qui ne
rencontre pas $F^{\mathbb{N}}$.  Or si $\dblunderline{x} \in
G^{\mathbb{N}}$ n'est pas dans $F^{\mathbb{N}}$, c'est qu'elle a une
valeur $x_\ell$ qui n'est pas dans $F$, et toute suite commençant par
$x_0,\ldots,x_\ell$ n'est pas dans $F^{\mathbb{N}}$, c'est-à-dire que
le voisinage fondamental $V_{\ell+1}(\dblunderline{x})$ est inclus
dans le complémentaire de $F^{\mathbb{N}}$.  Ceci achève de montrer
que $F^{\mathbb{N}} \subseteq G^{\mathbb{N}}$ est fermée.

Maintenant, l'ensemble $\mathscr{F}$ des parties finies d'un ensemble
(au plus) dénombrable, en l'occurrence, $G$, est (au plus)
dénombrable.  Ce fait peut être tenu pour acquis, mais rappelons
pourquoi il est vrai : en effet, si $G = \{g_i : i\in\mathbb{N}\}$,
alors on peut par exemple énumérer $\mathscr{F}$ à travers les
écritures binaires, ou plus précisément, $\mathscr{F} = \{F_n :
n\in\mathbb{N}\}$ où $F_n$ désigne la partie finie
$\{g_{i_0},\ldots,g_{i_r}\}$ lorsque $n = 2^{i_0} + \cdots + 2^{i_r}$
avec $i_0,\ldots,i_r$ entiers naturels distincts (autrement dit, $F_0
= \varnothing$, $F_1 = \{g_0\}$, $F_2 = \{g_1\}$, $F_3 = \{g_0,g_1\}$,
etc.).  Peu importe le fait qu'il y ait des répétitions dans
l'énumération $F_n$ (un ensemble surjecté par $\mathbb{N}$ est encore
dénombrable).

Ceci nous permet de dire que $\bigcup_{F\text{~fini~}\subseteq G}
F^{\mathbb{N}}$, autrement dit $\bigcup_{F \in \mathscr{F}}
F^{\mathbb{N}}$, est une réunion dénombrable de fermés
dans $G^{\mathbb{N}}$.  Comme un fermé est borélien, c'est une réunion
dénombrable de boréliens, donc c'est encore un borélien.

Enfin, remarquons que dire que l'ensemble $\{x_n : n\in\mathbb{N}\}$
est fini revient à dire qu'il est inclus un ensemble fini $F$,
autrement dit, que la suite $\dblunderline{x} = (x_n)$ appartient à
$F^{\mathbb{N}}$ pour un certain ensemble fini $F$, ou, ce qui revient
au même, qu'elle appartient à $\bigcup_{F \in \mathscr{F}}
F^{\mathbb{N}}$.

On a donc affaire à un jeu de Gale-Stewart défini par l'ensemble de
suites $B := \bigcup_{F \in \mathscr{F}} F^{\mathbb{N}}$ borélien (ou
par son complémentaire $A := G^{\mathbb{N}} \setminus B$ si on prend
le point de vue du Fugueur).  Le théorème de détermination borélienne
de Martin assure que l'un des joueurs a forcément une stratégie
gagnante.
\end{corrige}

(2) Indépendamment de la question précédente, donner un exemple de
couple $(G,x_0)$ pour lequel le Borneur possède une stratégie gagnante
à ce jeu.  Donner un exemple pour lequel le Fugueur en possède une.
(On cherchera à donner des exemples aussi simples que possibles.)

\begin{corrige}
Si $G$ est le graphe formé du seul sommet $x_0$, alors le Borneur
gagne trivialement (la suite sera la suite constante).

Si $G$ est le graphe formé des entiers naturels avec une arête $i \to
j$ lorsque $i<j$ (autrement dit des petits entiers naturels vers les
grands), ou même seulement $i \to i+1$, alors le Fugueur a une
stratégie gagnante consistant à jouer de $i$ vers $i+1$, ce qui assure
que la suite $(x_{2i+1})$ des positions choisies par le Fugueur est
strictement croissante quoi que fasse le Borneur (il ne peut pas
revenir en arrière), et notamment, elle n'est pas d'image finie.
\end{corrige}


%
%
%

\exercice

On considère une variante \emph{à somme (possiblement) non-nulle} de
Pierre-Papier-Ciseaux, à savoir le jeu en forme normale défini par la
matrice de gain suivante :
\begin{center}
\begin{tabular}{r|ccc}
$\downarrow$Alice, Bob$\rightarrow$&$U$&$V$&$W$\\\hline
$U$&$x,x$&$-1,+1$&$+1,-1$\\
$V$&$+1,-1$&$x,x$&$-1,+1$\\
$W$&$-1,+1$&$+1,-1$&$x,x$\\
\end{tabular}
\end{center}
où $x$ est un réel et, pour plus de commodité, on a écrit $U$ pour
« Pierre », $V$ pour « Papier » et $W$ pour « Ciseaux ».  (La ligne
correspond à l'option choisie par Alice, la colonne à l'option de Bob,
et chaque case indique le gain d'Alice suivi du gain de Bob.)

Le but de l'exercice est d'étudier les équilibres de Nash de ce jeu.

(On prendra bien note, pour simplifier les raisonnements en cas, du
fait que les options ont une symétrie cyclique\footnote{C'est-à-dire
  que remplacer $U$ par $V$ et $V$ par $W$ et $W$ par $U$ ne change
  rien au jeu.}, et que les joueurs ont eux aussi des rôles
symétriques.)

(1) Considérons le profil de stratégies mixtes dans lequel les deux
joueurs choisissent chacun chaque option avec probabilité
$\frac{1}{3}$ (c'est-à-dire la stratégie qui est optimale dans le cas
à somme nulle).  Pour quelle(s) valeur(s) de $x$ ce profil est-il un
équilibre de Nash ?

\begin{corrige}
Pour des raisons de symétrie, si l'un des joueurs joue cette stratégie
mixte $\frac{1}{3}U + \frac{1}{3}V + \frac{1}{3}W$, le gain espéré de
chacun des deux joueurs est le même quelle que soit la stratégie pure,
donc aussi mixte, de l'autre joueur.  Cette valeur se calcule
d'ailleurs aisément (comme somme des trois colonnes, ou des trois
lignes, de la matrice de gains, affectées des
coefficients $\frac{1}{3}$) : c'est $\frac{1}{3}x$ ; mais la seule
chose qui importe est que l'adversaire ait le même gain espéré quelle
que soit la stratégie pure, donc aussi mixte, qu'il choisit : il n'a
donc pas intérêt à changer unilatéralement sa stratégie.  Il s'agit
donc \emph{toujours} d'un équilibre de Nash, quelle que soit la valeur
de $x$.
\end{corrige}

\emph{On suppose dorénavant que $x<-1$.}

(2) Existe-t-il un équilibre de Nash dans lequel Alice joue purement
$U$ ?  (On raisonnera les options pouvant être dans le support de la
stratégie de Bob en réponse.)  En déduire tous les équilibres de Nash
dans lesquels au moins un joueur joue une stratégie pure.

\begin{corrige}
Si Alice joue purement $U$, les gains de Bob pour les différentes
stratégies pures de sa réponse sont $x$ pour $U$, $+1$ pour $V$ et
$-1$ pour $W$ d'après la matrice de gains.  Comme $+1 > -1 > x$, la
seule option qui peut faire partie du support d'une meilleure réponse
de Bob est $V$, autrement dit, si Alice joue purement $U$ dans un
équilibre de Nash, Bob répond forcément purement $V$.  Mais par le
même raisonnement (compte tenu de la symétrie cyclique des options et
de la symétrie des joueurs), si Bob joue purement $V$, Alice joue $W$
(et pas $U$ comme supposé).  Il ne peut donc pas y avoir d'équilibre
de Nash dans lequel Alice joue purement $U$.  Et de nouveau par
symétrie cyclique des options et symétrie des joueurs, il ne peut y
avoir aucun équilibre de Nash dans lequel un joueur jouerait une
stratégie pure.
\end{corrige}

(3) Dans cette question et la suivante, envisageons un équilibre de
Nash dans lequel Alice joue la stratégie mixte $pU + (1-p)V$ avec
$0<p<1$.  Supposons dans cette question que Bob réponde avec un une
stratégie mixte ayant elle aussi $\{U,V\}$ comme support.  Montrer que
$p = \frac{x+1}{2x}$ et que le gain de Bob est $\frac{x^2+1}{2x}$.  En
utilisant le fait que $\frac{x^2+1}{2x} < -\frac{1}{x}$ lorsque $x<-1$
(qu'on admettra pour ne pas perdre son temps en calculs inutiles), en
déduire qu'un tel équilibre de Nash n'existe pas.

\begin{corrige}
Si Alice joue $pU + (1-p)V$, les gains espérés de Bob pour les
différences stratégies pures de sa réponse sont $px-(1-p) =
-1+(x+1)p$ pour $U$, $p + (1-p)x = x-(x-1)p$ pour $V$ et $-p + (1-p) =
1-2p$ pour $W$.  Si une meilleure réponse de Bob a $\{U,V\}$ comme
support, ces deux options doivent apporter le même gain espéré,
c'est-à-dire qu'on doit avoir $-1+(x+1)p = x-(x-1)p$, ce qui équivaut
à $p = \frac{x+1}{2x}$, et le gain en question est $\frac{x^2+1}{2x}$,
tandis que le gain espéré pour $W$ est alors $1-2p = -\frac{1}{x}$.
D'après l'inégalité $\frac{x^2+1}{2x} < -\frac{1}{x}$, l'option $W$
fournit un meilleur gain espéré pour Bob, donc $\{U,V\}$ ne peut pas
être le support d'une meilleure réponse de Bob à $pU + (1-p)V$
d'Alice.
\end{corrige}

(4) On considère toujours un équilibre de Nash dans lequel Alice joue
la stratégie mixte $pU + (1-p)V$ avec $0<p<1$.  Supposons maintenant
que Bob réponde avec une stratégie mixte ayant (au moins) $U$ et $W$
dans son support support.  Montrer que $p = \frac{2}{x+3}$ (et
que $x\neq -3$) ; en utilisant le fait que $\frac{2}{x+3} > 1$ lorsque
$-3<x<-1$ et que $\frac{2}{x+3} < 0$ lorsque $x < -3$ (de nouveau, on
admettra ces faits pour ne pas perdre de temps en calculs), en déduire
qu'un tel équilibre de Nash n'existe pas.

\begin{corrige}
On a dit dans la question (3) que si Alice joue $pU + (1-p)V$, les
gains espérés de Bob pour les différences stratégies pures de sa
réponse sont $px-(1-p) = -1+(x+1)p$ pour $U$, $p + (1-p)x =
x-(x-1)p$ pour $V$ et $-p + (1-p) = 1-2p$ pour $W$.  Si une meilleure
réponse de Bob a $U$ et $W$ dans son support, ces deux options doivent
apporter le même gain espéré, c'est-à-dire qu'on doit avoir $-1+(x+1)p
= 1-2p$, ce qui équivaut à $(x+3)p = 3$, donc $x\neq 3$ et $p =
\frac{2}{x+3}$.  D'après les inégalités admises, $p$, qui devrait être
entre $0$ et $1$, ne l'est jamais si $x<-1$, donc un tel équilibre de
Nash n'existe pas.
\end{corrige}

(5) Expliquer soigneusement pourquoi les questions (2) à (4) montrent
que dans tout équilibre de Nash du jeu considéré, les deux joueurs
jouent une stratégie mixte ayant $\{U,V,W\}$ comme support (i.e.,
aucun ensemble strictement plus petit n'est possible).

\begin{corrige}
On a vu en (2) qu'il n'existe aucun équilibre de Nash dans lequel un
joueur joue une stratégie pure.  Supposons maintenant un équilibre de
Nash dans lequel un joueur a deux options dans son support.  Par
symétrie, sans perte de généralité, on peut supposer que c'est Alice
et que ces deux options sont $U$ et $V$.  Comme les stratégies pures
sont exclues, les supports possibles de la réponse de Bob sont :
$\{U,V\}$, $\{U,W\}$, $\{V,W\}$ et $\{U,V,W\}$.  Dans la question (3)
on a exclu $\{U,V\}$ ; dans la question (4), on a exclu $\{U,W\}$ et
$\{U,V,W\}$.  Reste le cas où le support de la stratégie de Bob est
$\{V,W\}$ (tandis que celui d'Alice est, on le rappelle, $\{U,V\}$).
Mais quitte à effectuer une symétrie cyclique des options ($U\to W\to
V\to U$) et échanger les joueurs, cela revient au cas où le support de
la stratégie d'Alice est $\{U,V\}$ et celui de Bob est $\{U,W\}$ : or
on a déjà exclu ce cas.  Il ne reste donc aucune possibilité.
\end{corrige}

(6) Envisageons maintenant un équilibre de Nash dans lequel Alice joue
une stratégie mixte $pU + p'V + (1-p-p')W$ avec $p>0$, $p'>0$ et
$1-p-p'>0$ et Bob répond par une stratégie ayant elle aussi
$\{U,V,W\}$ comme support.  Écrire un système de deux équations
linéaires vérifié par $p,p'$, justifier que ce système est
non-dégénéré et conclure.  Quels sont tous les équilibres de Nash du
jeu ?

\begin{corrige}
Si Alice joue $pU + p'V + (1-p-p')W$, les gains espérés de Bob pour
les différences stratégies pures de sa réponse sont $px - p' +
(1-p-p') = 1 + (x-1)p - 2p'$ pour $U$, $p + p' x - (1-p-p') = -1 + 2p
+ (x+1)p'$ pour $V$ et $-p + p' + (1-p-p')x = x -(x+1)p -
(x-1)p'$ pour $W$.  Si une meilleure réponse de Bob a $\{U,V,W\}$
comme support, ces trois options doivent apporter le même gain espéré,
c'est-à-dire que $1 + (x-1)p - 2p' = -1 + 2p + (x+1)p' = x -(x+1)p -
(x-1)p'$, ou (en soustrayant, disons, le premier membre aux deux
autres) :
\[
\begin{aligned}
-(x-3)p + (x+3)p' &= 2\\
- 2xp - (x-3)p' &= -(x-1)
\end{aligned}
\]
Le déterminant de ce système est $(x-3)^2 + 2x(x+3) = 3(x^2+3)$ qui
est non nul quel que soit $x$, donc le système est non-dégénéré : la
solution $p=p'=\frac{1}{3}$ trouvée en (1) est donc la seule solution.

Bref, on a montré que le seul équilibre de Nash dans lequel les
supports des stratégies d'Alice et Bob sont $\{U,V,W\}$ est celui
décrit en (1) ; comme on a vu en (5) que ceci est la seule possibilité
de support, il s'agit du seul équilibre de Nash du jeu.
\end{corrige}





%
%
%
\end{document}