%% 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.}\par\nobreak} \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\relax\else\setbox0=\vbox\bgroup\fi% \smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}} {{\hbox{}\nobreak\hfill\checkmark}% \ifcorrige\par\smallbreak\else\egroup\par\fi} % % % \begin{document} \ifcorrige \title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théories des jeux}} \else \title{MITRO206\\Contrôle de connaissances\\{\normalsize Théories des jeux}} \fi \author{} \date{13 avril 2022} \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. La longueur du sujet ne doit pas effrayer : l'énoncé est long parce que des rappels ont été faits et que la rédaction des questions cherche à éviter toute ambiguïté. Les réponses attendues sont généralement beaucoup plus courtes que les questions elles-mêmes (notamment dans le dernier 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} : $8+6+6$. \ifcorrige Ce corrigé comporte 10 pages (page de garde incluse). \else Cet énoncé comporte 6 pages (page de garde incluse). \fi \vfill {\noindent\tiny \immediate\write18{sh ./vc > vcline.tex} Git: \input{vcline.tex} \immediate\write18{echo ' (stale)' >> vcline.tex} \par} \pagebreak % % % \exercice Le but de cet exercice est de tenter une classification des jeux en forme normale, à deux joueurs, \emph{symétriques} (c'est-à-dire que les deux joueurs ont les mêmes options et les mêmes gains sous l'effet de la permutation qui les échange) et avec deux options. On considère donc le jeu dont la matrice de gains est la suivante, où $u,v,x,y$ sont des réels sur lesquels on va discuter (les options sont étiquetées $C$ et $D$ ; le gain d'Alice est listé en premier, celui de Bob en second) : \begin{center} \begin{tabular}{r|c|c|} $\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline $C$&$u$, $u$&$v$, $x$\\\hline $D$&$x$, $v$&$y$, $y$\\\hline \end{tabular} \end{center} On se limitera à l'étude de $u>v$, ce qu'on supposera désormais. (1) Expliquer brièvement pourquoi il ne change rien à l'analyse du jeu (p.ex., le calcul des équilibres de Nash) de remplacer tous les gains $t$ d'un joueur donné par $at+b$ où $a>0$ et $b$ est quelconque. En déduire qu'on peut supposer, dans le jeu ci-dessus, que $u=1$ et $v=0$, ce qu'on fera désormais. \begin{center} \begin{tabular}{r|c|c|} $\downarrow$Alice, Bob$\rightarrow$&$C$&$D$\\\hline $C$&$1$, $1$&$0$, $x$\\\hline $D$&$x$, $0$&$y$, $y$\\\hline \end{tabular} \end{center} (2) À quelle condition $(C,C)$ (c'est-à-dire : Alice joue $C$ et Bob joue $C$) est-il un équilibre de Nash ? À quelle condition $(D,D)$ est-il un équilibre de Nash ? À quelle condition $(C,D)$ est-il un équilibre de Nash ? Qu'en est-il de $(D,C)$ ? (À chaque fois, on demande des conditions sous forme d'inégalités portant sur $x$ et $y$.) On suppose dans la suite (pour écarter des cas limites pénibles) que $x$ n'est pas exactement égal à $1$ et que $y$ n'est pas exactement égal à $0$. (3) Expliquer pourquoi il n'y a pas d'équilibre de Nash dans lequel un joueur joue une stratégie pure (i.e., soit $C$ soit $D$) et l'autre une stratégie strictement mixte (i.e., $pC + (1-p)D$ avec $0
0$ si et seulement si Blaise possède une stratégie gagnante à partir de la position $T$ (qui que soit le joueur qui commence), et $v(T) < 0$ lorsque c'est Roxane, et $v(T) = 0$ lorsque c'est le second joueur. \end{itemize} (2) Utiliser ces règles admises pour calculer la valeur de l'arbre tracé à gauche dans la figure ci-dessus (avant effacement). Pour éviter de se tromper, on recommande de reproduire l'arbre et d'indiquer à côté de chaque sommet la valeur du sous-arbre qui en descend, et à côté de chaque arête la valeur du sous-arbre avec l'arête en question. En déduire qui a une stratégie gagnante dans cette position. \smallbreak \centerline{* * *} Indépendamment de ce qui précède, on va considérer une opération sur les jeux partisans : si $G$ est un jeu combinatoire partisan, vu comme un graphe orienté (bien-fondé), on définit un jeu noté $1{:}G$ en ajoutant une unique position $0$ à $G$ comme on va l'expliquer. Pour chaque position $z$ de $G$ il y a une position notée $1{:}z$ de $1{:}G$, et il y a une unique autre position, notée $0$, dans $1{:}G$ ; pour chaque arête $z \to z'$ de $G$, il y a une arête $1{:}z\, \to \, 1{:}z'$ dans $1{:}G$, coloriée de la même manière que dans $G$, et il y a de plus une arête $1{:}z\, \to 0$ dans $1{:}G$ pour chaque $z$, coloriée en bleu (en revanche, $0$ est un puits, c'est-à-dire qu'aucune arête n'en part) ; la position initiale de $1{:}G$ est $1{:}z_0$ où $z_0$ est celle de $G$. De façon plus informelle, pour jouer au jeu $1{:}G$, chaque joueur peut faire un coup normal ($1{:}z\, \to \, 1{:}z'$) de $G$, mais par ailleurs, Blaise peut à tout moment appliquer un coup « destruction totale » $1{:}z\, \to 0$ qui fait terminer immédiatement le jeu (et il a alors gagné\footnote{Ce jeu considéré tout seul n'est donc pas très amusant puisque Blaise a toujours la possibilité de gagner instantanément.}). (3) Montrer que si $G \geq H$ on a $1{:}G \geq 1{:}H$. (On rappelle que $G \geq H$ signifie : « Blaise a une stratégie gagnante s'il joue en second au jeu $G - H$ défini comme la somme disjonctive du jeu $G$ et du jeu $-H$ obtenu en échangeant les deux joueurs au jeu $H$ ». Pour cela, on expliquera comment Blaise peut gagner à $(1{:}G) - (1{:}H)$ en jouant en second, en supposant qu'il sait gagner à $G - H$ en jouant en second.) En déduire que si $G \doteq H$ alors $1{:}G \doteq 1{:}H$. {\footnotesize\textit{Remarque.} Ceci justifie partiellement l'affirmation (c) des règles admises ci-dessus en ce sens que cela explique que $v(1{:}G)$ ne dépende que de $v(G)$ et pas du détail de $G$, et aussi que la fonction $\varphi_+$ est croissante.\par} % % % \end{document}