%% 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}