diff options
Diffstat (limited to 'notes-mitro206.tex')
| -rw-r--r-- | notes-mitro206.tex | 156 |
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 |