path: root/controle-20180411.tex

%% 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]
%
\theoremstyle{definition}
\newtheorem{comcnt}{Tout}
\newcommand\thingy{%
\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
\newcommand\exercice{%
\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
\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{\fuzzy}{\mathrel{\|}}
%
\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\par\smallbreak\else\setbox0=\vbox\bgroup\fi%
\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
{{\hbox{}\nobreak\hfill\checkmark}%
\ifcorrige\relax\else\egroup\fi\par}
%
%
%
\begin{document}
\ifcorrige
\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des jeux}}
\else
\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théorie des jeux}}
\fi
\author{}
\date{11 avril 2018}
\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

Barème \emph{indicatif} : exercice 1 : $3$ points ; exercice 2 :
$4$ points ; exercice 3 : $10$ points ; exercice 4 : $3$ points ;
points bonus : comme indiqué.

\emph{Avertissement :} Les exercices ne sont pas tous une application
immédiate du cours ; il est parfois nécessaire de s'inspirer des
techniques ou raisonnements vus en cours pour raisonner dans des
cadres légèrement différents.

\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 à deux joueurs dans lequel les joueurs choisissent
indépendamment chacun une option parmi les quatre possibilités
« Terre », « Eau », « Air » et « Feu », et reçoivent des gains donnés
par le tableau suivant :

\begin{center}
\begin{tabular}{r|cccc}
$\downarrow$Alice, Bob$\rightarrow$&Terre&Eau&Air&Feu\\\hline
Terre&$0,0$&$-1,+1$&$+2,-2$&$+1,-1$\\
Eau&$+1,-1$&$0,0$&$-1,+1$&$+2,-2$\\
Air&$-2,+2$&$+1,-1$&$0,0$&$-1,+1$\\
Feu&$-1,+1$&$-2,+2$&$+1,-1$&$0,0$\\
\end{tabular}
\end{center}

(Le choix d'Alice détermine la ligne du tableau, celui de Bob
détermine la colonne ; la case correspondante indique d'abord le gain
d'Alice, puis celui de Bob.)

Montrer (c'est-à-dire, vérifier) que la stratégie optimale à ce jeu
consiste à jouer « Eau » avec probabilité $\frac{1}{2}$, et chacun de
« Terre » et « Air » avec probabilité $\frac{1}{4}$ (et ne jamais
jouer « Feu »).



%
%
%

\exercice

On considère le jeu suivant entre $N$ joueurs (où $N\geq 3$ est
fixé) : chaque joueur choisit, indépendamment des autres, une des deux
options $E$ (« égoïste ») ou $A$ (« altruiste »).  Le but de chaque
joueur est de maximiser son gain, indépendamment des autres.  Le choix
$E$ apporte un gain de $1$ point au joueur qui le fait (en plus des
gains liés aux choix $A$ des autres comme expliqué dans la phrase
suivante).  Le choix $A$ apporte un gain de $2$ points, mais ces gains
sont mutualisés entre \emph{tous} les joueurs, y compris ceux qui ont
choisi $E$.  Autrement dit, si $k$ joueurs choisissent l'option $A$,
chaque joueur gagne $\frac{2k}{N}$ à cause de ces choix (les $N-k$
joueurs qui ont choisi $E$ gagnent donc $1 + \frac{2k}{N}$ au total).

(0) Quel est le gain maximal d'un joueur dans ce jeu ?  Quel est le
gain minimal ?

(1) En supposant fixés les choix effectués par les $N-1$ autres
joueurs, exprimer le gain d'un joueur s'il choisit $E$ d'une part,
$A$ d'autre part ; calculer la différence entre ces deux gains.  Quel
est le signe de cette différence ?

(2) Expliciter tous les équilibres de Nash dans ce jeu (on indiquera
les stratégies pures ou mixtes intervenant dans l'équilibre, et le
gain espéré pour chaque joueur).

\medskip

On appelle maintenant \emph{stratégie rationnelle commune} une
stratégie mixte $s$ qui, si elle est suivie par tous les joueurs,
maximise le gain espéré de chaque joueur (il est le même pour chaque
joueur puisqu'on fait justement ici l'hypothèse qu'ils jouent tous
selon la même stratégie $s$).

(3) Expliciter la ou les stratégie(s) rationnelle(s) commune(s) au jeu
considéré ci-dessus.

(4) Commenter brièvement quant à la différence entre les réponses aux
questions (2) et (3).


%
%
%

\exercice

Considérons le graphe suivant :

\begin{center}
\begin{tikzpicture}[>=stealth,thick,text width=5bp,text height=5bp,text depth=0bp]
\node (a) at (0bp,0bp) [draw,circle] {$a$};
\node (b) at (-40bp,0bp) [draw,circle] {$b$};
\node (c) at (-80bp,0bp) [draw,circle] {$c$};
\node (d) at (-20bp,-30bp) [draw,circle] {$d$};
\node (e) at (-60bp,-30bp) [draw,circle] {$e$};
\node (f) at (-100bp,-30bp) [draw,circle] {$f$};
\node (g) at (-40bp,-60bp) [draw,circle] {$g$};
\node (h) at (-80bp,-60bp) [draw,circle] {$h$};
\draw [->] (a) -- (b);  \draw [->] (b) -- (c);
\draw [->] (a) -- (d);  \draw [->] (b) -- (d);
\draw [->] (b) -- (e);  \draw [->] (c) -- (e);
\draw [->] (c) -- (f);  \draw [->] (f) -- (e);  \draw [->] (d) -- (e);
\draw [->] (d) -- (g);  \draw [->] (e) -- (g);
\draw [->] (e) -- (h);  \draw [->] (f) -- (h);
\end{tikzpicture}
\end{center}

Les questions qui suivent étudient toutes différentes variantes d'un
jeu consistant à déplacer un ou plusieurs pions sur ce graphe en
suivant les flèches.

\medskip

(1) Dans un premier temps, on considère le jeu suivant : deux joueurs
déplacent un pion (commun) sur ce graphe ; chacun, tour à tour,
déplace le pion d'un sommet du graphe vers un sommet adjacent en
suivant une flèche (i.e., vers un voisin sortant).  Suivant la
convention habituelle, celui qui ne peut pas jouer a perdu.  Indiquer,
en fonction de la position initiale du pion ($a$ à $h$), quel joueur a
une stratégie gagnante.

(2) On modifie maintenant le jeu de la manière suivante : il y a
\emph{plusieurs} pions ; chaque joueur, à son tour, peut et doit
déplacer l'un quelconque des pions, mais un seul, selon les mêmes
règles que précédemment ; plusieurs pions peuvent se trouver sur la
même case, ils n'interagissent pas.  Comme précédemment, le joueur qui
ne peut pas jouer (c'est-à-dire, si tous les pions sont bloqués dans
des puits) a perdu.  Analyser le jeu en question et expliquer comment
déterminer quel joueur a une stratégie gagnante.  Traiter l'exemple de
la situation initiale où un pion est placé en chacun des sommets
$a,b,d,e$ (soit quatre pions au total).

\smallskip

(Les questions (3), (4) et (5) sont indépendantes.)

\smallskip

(3) On modifie maintenant encore un peu le jeu : comme dans la
question (2), il y a plusieurs pions sur le graphe, mais maintenant,
au lieu de déplacer un pion, un joueur peut aussi choisir d'en retirer
un (autrement dit, il y a deux coups possibles : soit déplacer un pion
quelconque suivant une flèche, soit retirer un pion quelconque) ; les
pions n'interagissent pas.  Analyser le jeu en question et expliquer
comment déterminer quel joueur a une stratégie gagnante.  On pourra
commencer par chercher la valeur de Grundy du jeu où il n'y a qu'un
seul pion et la comparer à la valeur de Grundy du jeu non modifié.
Traiter l'exemple de la situation initiale où un pion est placé en
chacun des sommets $a,b,d,e$, soit quatre pions au total.

(4) Les joueurs s'appellent ici Gandalf et Harry (Potter).  On revient
au jeu considéré en (1) (on déplace un seul pion, commun, et on ne
peut pas le retirer), mais cette fois, si le pion arrive au sommet $g$
le joueur Gandalf gagne (indépendamment de qui l'y a amené), tandis
que si le pion arrive en $h$, c'est Harry qui gagne.  Indiquer, en
fonction de la position initiale du pion ($a$ à $h$), quel joueur a
une stratégie gagnante.

(5) On considère enfin le jeu où deux joueurs, disons Xavier et
Yvonne, ont chacun un pion : chacun, quand vient son tour, déplace son
pion indépendamment de l'autre (les deux pions peuvent se trouver sur
la même case, ils n'interagissent pas).  Comme en (1), le joueur qui
ne peut pas bouger (quand vient son tour) a perdu.  Analyser le jeu en
question et expliquer comment déterminer quel joueur a une stratégie
gagnante (en fonction des positions initiales des deux pions).


%
%
%

\exercice

On considère le jeu de solitaire (c'est-à-dire, à un seul joueur)
suivant : on joue sur une rangée de cases qui pourront être numérotées
de $0$ à $N$, et qui peuvent chacune contenir un nombre quelconque de
pierres.  Initialement, on place une seule pierre sur la case $N$.  À
chaque coup, le joueur choisit une pierre sur la case $i$, il la
retire et, si $i>0$ ajoute $k$ pierres sur la case $i-1$, où $k$ est
le numéro du coup (compté à partir de $1$ : autrement dit, le premier
coup remplace une pierre par une pierre, le second remplace une pierre
par deux pierres, le troisième remplace une pierre par trois pierres
et ainsi de suite).

Le jeu se termine quand toutes les pierres ont été retirées.
Démontrer que cela se produit effectivement en temps fini (on ne
demande pas de majorer le nombre de coups en fonction de $N$).



%
%
%

\refstepcounter{comcnt}\bigskip\noindent\textbf{Points bonus.}

(Ceci n'est pas un exercice à résoudre mais un choix à faire.)

Vous disposez de deux options : indiquez clairement sur votre copie si
vous souhaitez
\begin{itemize}
\item[(E)] obtenir $1$ point supplémentaire, qui sera ajouté à votre
  note, ou bien
\item[(A)] obtenir $2$ points, qui seront mutualisés entre tous les
  participants à l'épreuve, c'est-à-dire que $2/N$ points seront
  ajoutés à la note de chacun des $N$ participants.
\end{itemize}



%
%
%
\end{document}