From 5f1766502ce4ea3381c13b913f964632cad428e6 Mon Sep 17 00:00:00 2001 From: "David A. Madore" 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