An exercise on games in normal form.

1 files changed, 154 insertions, 2 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 43545a1..dfc3ad0 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1259,7 +1259,7 @@ tout $b$, et on a expliqué que ceci signifie que $s$ est un équilibre
 de Nash.
 \end{proof}
 
-\textcolor{red}{Dire quelque chose sur l'algorithme de Lemke-Howson ?}
+%% \textcolor{red}{Dire quelque chose sur l'algorithme de Lemke-Howson ?}
 
 
 
@@ -1430,7 +1430,7 @@ $x \mapsto u(x,b)$ est affine) : \emph{en moyennant deux stratégies
 qui n'est pas le cas en général pour des jeux qui ne sont pas à somme
 nulle.
 
-\begin{algo}
+\begin{algo}\label{zero-sum-games-by-linear-programming-algorithm}
 Donnée une fonction $u\colon A_1 \times A_2 \to \mathbb{R}$ (avec
 $A_1,A_2$ deux ensembles finis) définissant la matrice de gains pour
 le joueur $1$ d'un jeu à somme nulle.  On peut calculer une stratégie
@@ -5215,6 +5215,158 @@ où Roxane commence (exactement analogue : Roxane choisit $(x_0,x_1)
 
 \subsection{Jeux en forme normale}
 
+\exercice
+
+Alice joue contre Bob un jeu dans lequel elle choisit une option parmi
+trois possibles appelées U, V et W, et Bob choisit une option parmi
+trois appelée X, Y et Z (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&Z\\\hline
+U&$6$&$0$&$4$\\
+V&$0$&$6$&$4$\\
+W&$2$&$2$&$7$\\
+\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 $0$ ;
+si Alice choisit V, Bob répondra par X et le gain d'Alice sera $0$ ;
+si Alice choisit W, Bob répondra par X ou Y indifféremment et le gain
+d'Alice sera $2$.  Comme Alice veut maximiser son gain, elle a intérêt
+à choisir W, et Bob répondra par X ou Y indifféremment, et le gain
+d'Alice sera $2$ 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 $6$ ;
+si Bob choisit Y, Alice répondra par V et le gain d'Alice sera $6$ ;
+si Bob choisit Z, Alice répondra par U ou V indifféremment et le gain
+d'Alice sera $4$.  Comme Bob veut minimiser le gain d'Alice, il a
+intérêt à choisir Z, et Alice répondra par W, et le gain d'Alice
+sera $4$ dans ce cas.
+\end{corrige}
+
+\smallbreak
+
+(3) On suppose que Bob joue \emph{aléatoirement}, en choisissant de
+façon équiprobable (i.e., avec probabilité $\frac{1}{3}$) chacune des
+trois options (X, Y et Z) qui s'offrent à lui.  Alice a connaissance
+de ce fait mais ne connaît pas le résultat du tirage : comment
+a-t-elle intérêt à jouer ?  Quelle est le gain (espéré) d'Alice dans
+ce cas ?
+
+\begin{corrige}
+Le choix de Bob étant purement aléatoire, le gain espéré d'Alice est
+donné par la combinaison convexe correspondante des colonnes du
+graphe : si elle choisit U, son gain espéré est $\frac{1}{3}\times 6 +
+\frac{1}{3}\times 0 + \frac{1}{3}\times 4 = \frac{10}{3} = 3 +
+\frac{1}{3}$, si elle choisit V, son gain espéré est
+$\frac{1}{3}\times 0 + \frac{1}{3}\times 6 + \frac{1}{3}\times 4 =
+\frac{10}{3} = 3 + \frac{1}{3}$, et si elle choisit W, son gain espéré
+est $\frac{1}{3}\times 2 + \frac{1}{3}\times 2 + \frac{1}{3}\times 7 =
+\frac{11}{3} = 3 + \frac{2}{3}$.  Alice a donc intérêt à choisir W,
+pour un gain espéré de $3 + \frac{2}{3}$.
+\end{corrige}
+
+\smallbreak
+
+(4) 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}\\
+x_U \geq 0\;, \;\; x_V \geq 0\;, \;\; x_W \geq 0&\\
+x_U + x_V + x_W &= 1\\
+v - 6x_U - 0x_V - 2x_W &\leq 0\;\;\text{(X)}\\
+v - 0x_U - 6x_V - 2x_W &\leq 0\;\;\text{(Y)}\\
+v - 4x_U - 4x_V - 7x_W &\leq 0\;\;\text{(Z)}\\
+\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 = 3$ atteint
+pour $x_U = \frac{1}{2}$ et $x_V = \frac{1}{2}$ et $x_W = 0$, avec
+pour le dual $y_X = \frac{1}{2}$ et $y_Y = \frac{1}{2}$ et $y_Z = 0$
+(les inégalités (X) et (Y) sont saturées et (Z) ne l'est pas).
+
+Autrement dit, Alice joue les options U et V de façon équiprobable,
+Bob réplique avec les options X et Y de façon équiprobable, et le gain
+espéré d'Alice est $3$, qui est la valeur du jeu à somme nulle en
+forme normale considéré ici.
+\end{corrige}
+
+\smallbreak
+
+(5) 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 (4), mais son allié).  Quels sont les équilibres de Nash
+possibles (on commencera par en chercher en stratégies pures, puis on
+discutera selon les supports possibles des stratégies) ?  Quel est le
+gain (espéré) d'Alice dans chacun ?
+
+\begin{corrige}
+Trois équilibres de Nash sont évidents : si Alice joue (purement) U et
+Bob joue (purement) X, aucun n'a intérêt à changer puisque $6$ 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 $6$ est
+maximum sur la ligne et sur la colonne ; et si Alice joue (purement) W
+et Bob joue (purement) Z, aucun n'a intérêt à changer puisque $7$ est
+maximum sur la ligne et sur la colonne.  Les gains d'Alice (et de Bob)
+dans chacun de ces trois cas sont donc $6$, $6$ et $7$ respectivement.
+
+Cherchons maintenant d'autres équilibre de Nash.  Supposons qu'Alice
+joue une combinaison convexe de U, V et W, disons avec poids
+(=probabilités) $p_U, p_V, p_W$ respectivement, et de même Bob une
+combinaison de X, Y et Z avec poids $q_X, q_Y, q_Z$ respectivement.
+Si la stratégie $x$ d'Alice est pure (i.e., un des $p_i$ est
+strictement positif, les autres valent $0$), celle de Bob l'est aussi
+car il est évident que chaque option d'Alice admet une unique
+meilleure réponse de Bob (un nombre est strictement le plus grand dans
+chaque ligne) ; et de même, si la stratégie de Bob est pure, celle
+d'Alice l'est aussi.  Si $q_X$ et $q_Y$ sont tous les deux strictement
+positifs, c'est forcément que les réponses X et Y de Bob donnent le
+même gain espéré (car si l'une était strictement meilleure que
+l'autre, Bob choisirait purement celle-là) : c'est-à-dire $6 p_U + 2
+p_W = 6 p_V + 2 p_W$ ; de même, si $q_X$ et $q_Z$ sont tous les deux
+strictement positifs, on a $6 p_U + 2 p_W = 4 p_U + 4 p_V + 2 p_W$, et
+ainsi de suite.
+
+\textcolor{red}{(À finir)}
+\end{corrige}
+
 \subsection{Jeux de Gale-Stewart et détermination}
 
 \exercice