From bbeb992ed925bce434c664d7afdb76a1622d8508 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sat, 7 Apr 2018 11:43:17 +0200
Subject: Start writing exam for 2018-04-11.

---
 controle-20180411.tex | 191 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 191 insertions(+)
 create mode 100644 controle-20180411.tex

(limited to 'controle-20180411.tex')

diff --git a/controle-20180411.tex b/controle-20180411.tex
new file mode 100644
index 0000000..ad422b0
--- /dev/null
+++ b/controle-20180411.tex
@@ -0,0 +1,191 @@
+%% 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
+
+%% {\footnotesize
+%% \immediate\write18{sh ./vc > vcline.tex}
+%% \begin{center}
+%% Git: \input{vcline.tex}
+%% \end{center}
+%% \immediate\write18{echo ' (stale)' >> vcline.tex}
+%% \par}
+
+\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
+
+\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 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 joueux, 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).
+
+
+
+%
+%
+%
+
+\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 pour cette question, qui sera compté
+  dans votre note, ou bien
+\item[(A)] obtenir $2$ points pour cette question, qui seront
+  mutualisés entre tous les participants.
+\end{itemize}
+
+
+
+%
+%
+%
+\end{document}
-- 
cgit v1.2.3


From a4604390708a78be76ff69530e6ca2995f968ad6 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sat, 7 Apr 2018 21:45:40 +0200
Subject: Two more exercises.

---
 controle-20180411.tex | 101 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 101 insertions(+)

(limited to 'controle-20180411.tex')

diff --git a/controle-20180411.tex b/controle-20180411.tex
index ad422b0..6272a14 100644
--- a/controle-20180411.tex
+++ b/controle-20180411.tex
@@ -165,6 +165,107 @@ considéré ci-dessus.
 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).
+
+(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).  Analyser le jeu en question
+et expliquer comment déterminer quel joueur a une stratégie gagnante.
+
+
+%
+%
+%
+
+\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$).
+
+
 
 %
 %
-- 
cgit v1.2.3


From e5720679609deb3bbacae8fb0d9ce1e2d73ff756 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sat, 7 Apr 2018 22:33:10 +0200
Subject: Another exercise, and various additional explanations.

---
 controle-20180411.tex | 46 ++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 42 insertions(+), 4 deletions(-)

(limited to 'controle-20180411.tex')

diff --git a/controle-20180411.tex b/controle-20180411.tex
index 6272a14..5c7c197 100644
--- a/controle-20180411.tex
+++ b/controle-20180411.tex
@@ -105,6 +105,10 @@ L'usage des appareils électroniques est interdit.
 
 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
@@ -120,6 +124,38 @@ Git: \input{vcline.tex}
 \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 »).
+
+
+
 %
 %
 %
@@ -217,6 +253,8 @@ 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).
 
+(Les questions (3), (4) et (5) sont indépendantes.)
+
 (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
@@ -278,10 +316,10 @@ demande pas de majorer le nombre de coups en fonction de $N$).
 Vous disposez de deux options : indiquez clairement sur votre copie si
 vous souhaitez
 \begin{itemize}
-\item[(E)] obtenir $1$ point pour cette question, qui sera compté
-  dans votre note, ou bien
-\item[(A)] obtenir $2$ points pour cette question, qui seront
-  mutualisés entre tous les participants.
+\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.
 \end{itemize}
 
 
-- 
cgit v1.2.3


From b578594f7b050e75325129a9c1e07fc2754f3de9 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sun, 8 Apr 2018 19:22:59 +0200
Subject: Various small clarifications.

---
 controle-20180411.tex | 31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)

(limited to 'controle-20180411.tex')

diff --git a/controle-20180411.tex b/controle-20180411.tex
index 5c7c197..08613de 100644
--- a/controle-20180411.tex
+++ b/controle-20180411.tex
@@ -75,14 +75,6 @@
 \date{11 avril 2018}
 \maketitle
 
-%% {\footnotesize
-%% \immediate\write18{sh ./vc > vcline.tex}
-%% \begin{center}
-%% Git: \input{vcline.tex}
-%% \end{center}
-%% \immediate\write18{echo ' (stale)' >> vcline.tex}
-%% \par}
-
 \pretolerance=8000
 \tolerance=50000
 
@@ -169,7 +161,7 @@ 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 joueux, y compris ceux qui ont
+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).
@@ -237,7 +229,7 @@ suivant les flèches.
 (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
+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.
@@ -253,19 +245,23 @@ 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
+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é).
+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).
+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
@@ -278,8 +274,10 @@ 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).  Analyser le jeu en question
-et expliquer comment déterminer quel joueur a une stratégie gagnante.
+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).
 
 
 %
@@ -319,7 +317,8 @@ vous souhaitez
 \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.
+  participants à l'épreuve, c'est-à-dire que $2/N$ points seront
+  ajoutés à la note de chacun des $N$ participants.
 \end{itemize}
 
 
-- 
cgit v1.2.3

