summaryrefslogtreecommitdiffstats
path: root/notes-mitro206.tex
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2016-02-29 11:20:17 (GMT)
committerDavid A. Madore <david+git@madore.org>2016-02-29 11:20:17 (GMT)
commit5f1766502ce4ea3381c13b913f964632cad428e6 (patch)
tree7ab16a35eff43090376730bd7943a805209b7462 /notes-mitro206.tex
parent270cb59d67df7ff08863e0f3b434763762ad6e8d (diff)
downloadmitro206-5f1766502ce4ea3381c13b913f964632cad428e6.zip
mitro206-5f1766502ce4ea3381c13b913f964632cad428e6.tar.gz
mitro206-5f1766502ce4ea3381c13b913f964632cad428e6.tar.bz2
Minor changes noted during lecture.
Diffstat (limited to 'notes-mitro206.tex')
-rw-r--r--notes-mitro206.tex37
1 files changed, 24 insertions, 13 deletions
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.