diff options
| -rw-r--r-- | controle-20160421.tex | 171 |
1 files changed, 168 insertions, 3 deletions
diff --git a/controle-20160421.tex b/controle-20160421.tex index 9de25e4..a67231a 100644 --- a/controle-20160421.tex +++ b/controle-20160421.tex @@ -15,11 +15,15 @@ \usepackage{wasysym} \usepackage{url} % +\usepackage{xr-hyper} +% \usepackage{graphics} \usepackage[usenames,dvipsnames]{xcolor} \usepackage{tikz} \usetikzlibrary{matrix,calc} -%\usepackage{hyperref} +\usepackage{hyperref} +% +\externaldocument{notes-mitro206}[notes-mitro206.pdf] % \theoremstyle{definition} \newtheorem{comcnt}{Tout} @@ -69,9 +73,9 @@ % \begin{document} \ifcorrige -\title{MITRO206\\Contrôle de connaissance — Corrigé\\{\normalsize Théorie des jeux}} +\title{MITRO206\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des jeux}} \else -\title{MITRO206\\Contrôle de connaissance\\{\normalsize Théorie des jeux}} +\title{MITRO206\\Contrôle de connaissances\\{\normalsize Théorie des jeux}} \fi \author{} \date{21 avril 2016} @@ -112,6 +116,167 @@ Durée : 3h % % +\exercice + +Alice joue contre Bob un jeu dans lequel elle choisit une option parmi +deux possibles appelées U et V, et Bob choisit une option parmi deux +appelées X et Y (les modalités du choix varient selon les questions +ci-dessous) : les gains d'\emph{Alice} (c'est-à-dire, la fonction +qu'elle cherche à maximiser) sont donnés par le tableau ci-dessous, en +fonction de son choix (colonne de gauche) et de celui de Bob (ligne du +haut) : + +\begin{center} +\begin{tabular}{r|ccc} +$\downarrow$A, B$\rightarrow$&X&Y\\\hline +U&$3$&$1$\\ +V&$0$&$4$\\ +\end{tabular} +\end{center} + +\smallbreak + +(1) On suppose que Bob fait son choix \emph{après} Alice, et en +connaissant le choix d'Alice, et qu'il cherche à minimiser le gain +d'Alice (i.e., le gain de Bob est l'opposé de celui d'Alice). Comment +Alice a-t-elle intérêt à jouer et comment Bob répondra-t-il ? Quelle +est le gain d'Alice dans ce cas ? + +\begin{corrige} +Si Alice choisit U, Bob répondra par Y et le gain d'Alice sera $1$ ; +si Alice choisit V, Bob répondra par X et le gain d'Alice sera $0$. +Comme Alice veut maximiser son gain, elle a intérêt à choisir U, et +Bob répondra par Y, et le gain d'Alice sera $1$ dans ce cas. +\end{corrige} + +\smallbreak + +(2) On suppose maintenant que Bob fait son choix \emph{avant} Alice, +et qu'Alice connaîtra le choix de Bob ; on suppose toujours que Bob +cherche à minimiser le gain d'Alice. Que fera Bob et comment Alice +répondra-t-elle ? Quelle est le gain d'Alice dans ce cas ? + +\begin{corrige} +Si Bob choisit X, Alice répondra par U et le gain d'Alice sera $3$ ; +si Bob choisit Y, Alice répondra par V et le gain d'Alice sera $4$. +Comme Bob veut minimiser le gain d'Alice, il a intérêt à choisir X, et +Alice répondra par U, et le gain d'Alice sera $3$ dans ce cas. +\end{corrige} + +\smallbreak + +(3) On suppose qu'Alice et Bob font leur choix séparément, sans +connaître le choix de l'autre, et toujours que Bob cherche à minimiser +le gain d'Alice. Comment ont-ils intérêt à faire leurs choix ? Quel +est le gain (espéré) d'Alice dans ce cas ? + +\begin{corrige} +On a affaire à un jeu à somme nulle écrit en forme normale : +l'algorithme \ref{zero-sum-games-by-linear-programming-algorithm} nous +indique qu'on obtient la stratégie optimale d'Alice en résolvant le +problème de programmation linéaire suivant : +\[ +\left\{ +\begin{aligned} +\text{maximiser\ }v&\text{\ avec}\\ +p_U \geq 0\;, \;\; p_V \geq 0&\\ +p_U + p_V &= 1\\ +v - 3p_U - 1p_V &\leq 0\;\;\text{(X)}\\ +v - 0p_U - 4p_V &\leq 0\;\;\text{(Y)}\\ +\end{aligned} +\right. +\] +On peut l'écrire sous forme normale en réécrivant $v = v_+ - v_-$ avec +$v_+,v_- \geq 0$, mais on gagne un petit peu en remarquant que $v$ +sera forcément positif puisque tous les gains du tableau le sont, donc +on peut ajouter la contrainte $v \geq 0$. Une application de +l'algorithme du simplexe donne finalement l'optimum $v = 2$ atteint +pour $p_U = \frac{2}{3}$ et $p_V = \frac{1}{3}$, avec pour le dual +$q_X = \frac{1}{2}$ et $q_Y = \frac{1}{2}$ (les inégalités (X) et (Y) +sont toutes saturées). + +Autrement dit, Alice joue les options U et V avec probabilités +$\frac{1}{3}$ et $\frac{2}{3}$, Bob réplique avec les options X et Y +de façon équiprobable, et le gain espéré d'Alice est $2$, qui est la +valeur du jeu à somme nulle en forme normale considéré ici. +\end{corrige} + +\smallbreak + +(4) On suppose maintenant que Bob cherche à \emph{maximiser} le gain +d'Alice (i.e., il n'est plus son adversaire comme dans les questions +(1), (2) et (3), mais son allié). On cherche à déterminer quels sont +les équilibres de Nash possibles. On notera $(p_U,p_V, q_X,q_Y)$ un +profil de stratégies mixtes général, où $p_U,p_V$ (positifs de +somme $1$) sont les poids des trois options d'Alice (=probabilités +qu'elle les joue), et $q_X,q_Y$ (positifs, également de somme $1$) les +poids des trois options de Bob. On va discuter selon le support des +stratégies (i.e., selon les ensembles d'options qui ont un poids +strictement positif).\spaceout (a) Pour commencer, quels sont les +équilibres de Nash évidents en stratégies pures ? Expliquer pourquoi +ce sont bien les seuls équilibres de Nash où l'un des deux joueurs a +une stratégie pure.\spaceout (b) Calculer ce que doivent valoir $p_U$ +et $p_V$ dans un équilibre de Nash où $q_X > 0$ et $q_Y > 0$ (i.e., +les options X et Y de Bob sont dans le support), et ce que dovient +valoir $q_X$ et $q_Y$ dans un équilibre de Nash où $p_U > 0$ et $p_V > +0$ (i.e., les options U et V d'Alice sont dans le support). Ces +contraintes donnent-elles effectivement un équilibre de +Nash ?\spaceout (c) Conclure quant à l'ensemble des équilibres de Nash +du jeu considéré. + +\begin{corrige} +(a) Deux équilibres de Nash sont évidents : si Alice joue (purement) U + et Bob joue (purement) X, aucun n'a intérêt à changer puisque $3$ + est maximum sur la ligne et sur la colonne ; si Alice joue + (purement) V et Bob joue (purement) Y, aucun n'a intérêt à changer + puisque $4$ est maximum sur la ligne et sur la colonne. Les gains + d'Alice (et de Bob) dans chacun de ces trois cas sont donc $3$ + et $4$ respectivement. + +Il s'agit là de l'ensemble des équilibres de Nash où l'un des deux +joueurs a une stratégie pure : par exemple, si Alice joue purement U, +Bob ne peut que répondre par purement X puisque le gain $3$ est +strictement plus grand que tout autre gain sur la ligne (i.e., donner +un poids non nul à une autre option de Bob ne pourrait que diminuer le +gain). + +(b) Si $q_X > 0$ et $q_Y > 0$, les stratégies pures X et Y de Bob +donnent forcément le même gain, car si l'une d'elle donnait un gain +strictement supérieure à l'autre, Bob aurait intérêt à augmenter le +poids $q$ correspondant et améliorerait ainsi strictement sa réponse. +Autrement dit, l'espérance de gain contre la stratégie pure X, +c'est-à-dire $6 p_U$, est égale à l'espérance de gain contre la +stratégie pure Y, soit $p_U + 4 p_V$. On a donc $3 p_U = p_U + 4 +p_V$, et comme aussi $p_U + p_V = 1$ on trouve $(p_U, p_V) = +(\frac{1}{3}, \frac{2}{3})$ en résolvant le système (soit la même +stratégie mixte que trouvée en (3), ce qui n'est pas un hasard vu que +le signe des gains de Bob n'est pas du tout intervenu dans le +raisonnement). De même, si $p_U > 0$ et $p_V > 0$, on a $3 q_X + q_Y += 4 q_Y$, et comme aussi $q_X + q_Y = 1$ on trouve $(q_X, q_Y) = +(\frac{1}{2}, \frac{1}{2})$ en résolvant le système (même remarque). + +Bref, on a un équilibre de Nash \emph{potentiel} donné par $(p_U,p_V, +q_X,q_Y) = (\frac{2}{3}, \frac{1}{3}, \frac{1}{2}, \frac{1}{2})$, +c'est-à-dire exactement le même profil que dans la question (3) quand +les joueurs étaient adversaires. Pourtant, aucun des deux joueurs n'a +(strictement) intérêt à changer unilatéralement sa stratégie puisque +les deux options qui se présentent à lui sont indifférentes (elles ont +le même gain espéré) compte tenu du comportement de l'autre. On a +donc bien trouvé un troisième équilibre de Nash. + +(c) Pour résumer, on a trois équilibres de Nash récapitulés par le +tableau (triés par ordre de gain espéré décroissant) : +\begin{center} +\begin{tabular}{cc|cc|c} +$p_U$&$p_V$&$q_X$&$q_Y$&gain\\\hline +$0$&$1$&$0$&$1$&$4$\\ +$1$&$0$&$1$&$0$&$3$\\ +$\frac{2}{3}$&$\frac{1}{3}$&$\frac{1}{2}$&$\frac{1}{2}$&$2$\\ +\end{tabular} +\end{center} +et on a prouvé que c'étaient bien les seuls. +\end{corrige} + % |