From 5f1766502ce4ea3381c13b913f964632cad428e6 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Mon, 29 Feb 2016 12:20:17 +0100
Subject: Minor changes noted during lecture.

---
 notes-mitro206.tex | 37 ++++++++++++++++++++++++-------------
 1 file changed, 24 insertions(+), 13 deletions(-)

(limited to 'notes-mitro206.tex')

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 1bcf911..8c4bfc4 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1092,6 +1092,9 @@ combinaison convexe est majorée par la plus grande des valeurs
 combinée (ici, des $u_i(s_?,a)$), il est clair que le maximum des
 $u_i(s_?,t)$ existe et est égal au maximum des $u_i(s_?,a)$ ; les
 autres affirmations sont tout aussi faciles.
+
+(Si on préfère : une fonction affine sur un simplexe prend son maximum
+— ou son minimum — sur un des sommets de ce simplexe.)
 \end{proof}
 
 \begin{thm}[John Nash, 1951]\label{theorem-nash-equilibria}
@@ -1134,7 +1137,7 @@ sur $S$.
 Définissons maintenant $T\colon S\to S$ de la façon suivante : si $s
 \in S$, on pose $T(s) = s^\sharp$, où $s^\sharp =
 (s^\sharp_1,\ldots,s^\sharp_N)$ avec $s^\sharp_i$ le barycentre de
-$s_i$ avec coefficient $1$ et des $a_i$ avec les coefficients
+$s_i$ avec coefficient $1$ et des $a \in A_i$ avec les coefficients
 $\varphi_{i,a}(s)$, autrement dit :
 \[
 \begin{aligned}
@@ -1272,7 +1275,7 @@ théorème \ref{theorem-minimax} est $0$).
 \begin{proof}
 On applique le théorème : il donne $\max_{x\in C}\penalty0 \min_{y\in
   C} u(x,y) = \min_{y\in C}\penalty0 \max_{x\in C} u(x,y)$.  Mais
-puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in C}y
+puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in C}
 \max_{x\in C} (-u(y,x))$, soit, en renommant les variables liées,
 $\min_{x\in C}\penalty0 \max_{y\in C} (-u(x,y)) = -\max_{x\in
   C}\penalty0 \min_{y\in C} u(x,y)$.  Par conséquent, $\max_{x\in
@@ -1281,10 +1284,6 @@ en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in C} u(x,y) =
 0$, ce qu'on voulait prouver.
 \end{proof}
 
-Avec les hypothèses et notations du corollaire, l'ensemble des $x$
-tels que $u(x,y)\geq 0$ pour tout $y\in C$ est un convexe
-compact $C_0 \neq \varnothing$ inclus dans $C$.
-
 \thingy\label{minimax-for-games} Le théorème \ref{theorem-minimax}
 s'applique à la théorie des jeux de la manière suivante : si on
 considère un jeu à deux joueurs à somme nulle, en notant $S_1$ et
@@ -1320,20 +1319,32 @@ signifie que $u$ est antisymétrique), alors la valeur du jeu est
 nulle.
 
 \thingy Dans le contexte ci-dessus, on peut légèrement reformuler le
-minimax : si on se rappelle qu'\emph{une fonction affine sur un
-  simplexe prend son maximum (ou son minimum) sur un des sommets} du
+minimax : si on se rappelle (cf. \ref{stupid-remark-best-mixed-strategies})
+qu'une fonction affine sur un
+  simplexe prend son maximum (ou son minimum) sur un des sommets du
 simplexe, cela signifie que, quel que soit $x\in S_1$ fixé, le minimum
 $\min_{y\in S_2} u(x,y)$ est en fait atteint sur une stratégie
-\emph{pure}, $\min_{y\in S_2} u(x,y) = \min_{y\in A_2} u(x,y)$ (avec
+\emph{pure}, $\min_{y\in S_2} u(x,y) = \min_{b\in A_2} u(x,b)$ (avec
 $A_2$ l'ensemble des sommets de $S_2$, i.e., l'ensemble des stratégies
-pures du joueur $2$), et de même $\max_{x\in S_1} u(x,y) = \max_{x\in
-  A_1} u(x,y)$ quel que soit $y \in S_2$.  \emph{Ceci ne signifie pas}
+pures du joueur $2$), et de même $\max_{x\in S_1} u(x,y) = \max_{a\in
+  A_1} u(a,y)$ quel que soit $y \in S_2$.  \emph{Ceci ne signifie pas}
 qu'il existe un équilibre de Nash en stratégies pures (penser à
 pierre-papier-ciseaux).  Néanmoins, cela signifie que pour calculer la
 pire valeur possible $\min_{y\in S_2} u(x,y)$ d'une stratégie $x$ du
 joueur $1$, celui-ci peut ne considérer que les réponses en stratégies
 pures du joueur $2$.
 
+Si on appelle $v$ la valeur du jeu, l'ensemble des $x$ tels que
+$u(x,y) \geq v$ pour tout $y\in S_2$, c'est-à-dire l'ensemble des
+stratégies optimales pour le joueur $1$, coïncide donc avec l'ensemble
+des $x$ tels que $u(x,b) \geq v$ pour tout $b\in A_2$.  En
+particulier, c'est un convexe compact dans $S_1$ (puisque chaque
+inégalité $u(x,b) \geq v$ définit un convexe compact dans $S_1$ vu que
+$x \mapsto u(x,b)$ est affine) : \emph{en moyennant deux stratégies
+  optimales pour un joueur on obtient encore une telle stratégie}, ce
+qui n'est pas le cas en général pour des jeux qui ne sont pas à somme
+nulle.
+
 \begin{algo}
 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
@@ -1364,8 +1375,8 @@ Le problème dual (minimiser ${^{\mathrm{t}}\textbf{q}} y$ sous les
 contraintes ${^{\mathrm{t}}\textbf{M}} y \geq {^\mathrm{t}\textbf{q}}$
 et $y\geq 0$) est alors de minimiser $w_+ - w_-$ sous les contraintes
 \[w_+\geq 0,\; w_- \geq 0,\;\; (\forall b\in A_2)\;y_b \geq 0\]
-\[\sum_{b\in A_2} y_b \leq 1\]
-\[-\sum_{b\in A_2} y_b \leq -1\]
+\[\sum_{b\in A_2} y_b \geq 1\]
+\[-\sum_{b\in A_2} y_b \geq -1\]
 \[(\forall a\in A_1)\;w_+ - w_- - \sum_{b \in A_2} u(a,b)\, y_b \geq 0\]
 Il s'agit donc exactement du même problème, mais pour l'autre joueur.
 
-- 
cgit v1.2.3

