diff options
| -rw-r--r-- | controle-20180411.tex | 329 |
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} |