An exercise on normal form games.

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