Merge branch 'master' of git.madore.org:teach/mitro206

1 files changed, 329 insertions, 0 deletions

diff --git a/controle-20180411.tex b/controle-20180411.tex
new file mode 100644
index 0000000..08613de
--- /dev/null
+++ b/controle-20180411.tex
@@ -0,0 +1,329 @@
+%% 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}