diff options
| -rw-r--r-- | notes-mitro206.tex | 153 |
1 files changed, 137 insertions, 16 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 132c476..183307a 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -568,23 +568,23 @@ Nash. Pour démontrer le théorème en question, on utilise (et on admet) le théorème du point fixe de Brouwer, qui affirme que si $K$ est un -convexe compact de $\mathbb{R}^m$, et que $f \colon K \to K$ est -continue, alors il existe $x\in K$ tel que $f(x) = x$ (un \emph{point - fixe} de $f$, donc). +convexe compact de $\mathbb{R}^m$, et que $T \colon K \to K$ est +continue, alors il existe $x\in K$ tel que $T(x) = x$ (un \emph{point + fixe} de $T$, donc). L'idée intuitive de la démonstration suivante est : partant d'un profil $s$ de stratégies, on peut définir continûment un nouveau -profil $s'$ en donnant plus de poids aux options qui donnent un -meilleur gain au joueur correspondant — si bien que $s'$ sera -différent de $s$ dès que $s'$ n'est pas un équilibre de Nash. Comme -la fonction $f \colon s \to s'$ doit avoir un point fixe, ce point +profil $s^\sharp$ en donnant plus de poids aux options qui donnent un +meilleur gain au joueur correspondant — si bien que $s^\sharp$ sera +différent de $s$ dès que $s^\sharp$ n'est pas un équilibre de Nash. Comme +la fonction $T \colon s \to s^\sharp$ doit avoir un point fixe, ce point fixe sera un équilibre de Nash. \begin{proof}[Démonstration de \ref{theorem-nash-equilibria}] Si $s \in S$ et $1\leq i\leq N$, convenons de noter $s_{?i}$ l'effacement de la composante $s_i$ (c'est-à-dire le profil pour les joueurs autres que $i$). Si de plus $b \in A_i$, notons -$\varphi_{i,b}(s) = \max\{0, u_i(s_{?i},b) - u_i(s)\}$ l'augmentation +$\varphi_{i,b}(s) = \max(0,\; u_i(s_{?i},b) - u_i(s))$ l'augmentation du gain du joueur $i$ si on remplace sa stratégie $s_i$ par la stratégie pure $b$ en laissant le profil $s_{?i}$ des autres joueurs inchangé (ou bien $0$ s'il n'y a pas d'augmentation). On remarquera @@ -594,15 +594,18 @@ A_i$ (faire appel à la proposition précédente pour le « si »). On remarquera aussi que chaque $\varphi_{i,b}$ est une fonction continue sur $S$. -Définissons maintenant $f\colon S\to S$ de la façon suivante : si $s -\in S$, on pose $f(s) = s'$, où $s' = (s'_1,\ldots,s'_N)$ avec +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 +$\varphi_{i,a}(s)$, autrement dit : \[ \begin{aligned} -s'_i(a) &= \frac{s_i(a) + \varphi_{i,a}(s)}{\sum_{b\in A_i}(s_i(b) + \varphi_{i,b}(s))}\\ +s^\sharp_i(a) &= \frac{s_i(a) + \varphi_{i,a}(s)}{\sum_{b\in A_i}(s_i(b) + \varphi_{i,b}(s))}\\ &= \frac{s_i(a) + \varphi_{i,a}(s)}{1 + \sum_{b\in A_i}\varphi_{i,b}(s)} \end{aligned} \] -(L'important est que $s'_i$ augmente strictement le poids des options +(L'important est que $s^\sharp_i$ augmente strictement le poids des options $a\in A_i$ telles que $u_i(s_{?i},a) > u_i(s)$ ; en fait, on pourrait composer $\varphi$ à gauche par n'importe quelle fonction $\mathbb{R} \to \mathbb{R}$ croissante, continue, nulle sur les négatifs et @@ -611,8 +614,8 @@ l'identité ci-dessus pour rendre l'expression plus simple à écrire, mais elle peut donner l'impression qu'on commet une « erreur d'homogénéité » en ajoutant un gain à une probabilité.) -D'après la première expression donnée, il est clair qu'on a bien $s'_i -\in S_i$, et qu'on a donc bien défini une fonction $f\colon S\to S$. +D'après la première expression donnée, il est clair qu'on a bien $s^\sharp_i +\in S_i$, et qu'on a donc bien défini une fonction $T\colon S\to S$. Cette fonction est continue, donc admet un point fixe $s$. On va montrer que $s$ est un équilibre de Nash. @@ -621,15 +624,133 @@ u_i(s)$ (car, comme dans la preuve de \ref{stupid-remark-best-mixed-strategies}, $u_i(s)$ est combinaison convexe des $u_i(s_{?i},a)$ dont est supérieur au plus petit d'entre eux) : c'est-à-dire $\varphi_{i,a}(s) = 0$. Pour un tel $a$, la -seconde expression $s'_i(a) = s_i(a) / \big(1 + \sum_{b\in +seconde expression $s^\sharp_i(a) = s_i(a) / \big(1 + \sum_{b\in A_i}\varphi_{i,b}(s)\big)$ montre, en tenant compte du fait que -$s'_i = s_i$ puisque $s$ est un point fixe, que $\sum_{b\in A_i} +$s^\sharp_i = s_i$ puisque $s$ est un point fixe, que $\sum_{b\in A_i} \varphi_{i,b}(s) = 0$, donc $\varphi_{i,b}(s) = 0$ pour tout $b$. On vient de voir que les $\varphi_{i,b}(s)$ sont nuls pour tout $i$ et 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 ?} + + +% +% +% + +\section{Jeux à somme nulle en forme normale} + +\subsection{Le théorème du minimax} + +\begin{thm}[« du minimax », von Neumann, 1928]\label{theorem-minimax} +Soient $C$ et $C'$ deux convexes compacts dans des espaces affines +réels de dimension finie, et $u\colon C\times C' \to \mathbb{R}$ +une application bi-affine (c'est-à-dire, affine en chaque variable +séparément). Alors +\[ +\max_{x\in C} \min_{y\in C'} u(x,y) = +\min_{y\in C'} \max_{x\in C} u(x,y) +\] +\end{thm} +\begin{proof} +Tout d'abord, l'inégalité dans un sens est évidente : on a +\[ +\max_{x\in C} \min_{y\in C'} u(x,y) += \min_{y\in C'} u(x_*,y) +\leq u(x_*,y_*) \leq \max_{x\in C} u(x,y_*) = +\min_{y\in C'} \max_{x\in C} u(x,y) +\] +où $x_* \in C$ est un point où $\max_{x\in C} \min_{y\in C'} +u(x,y)$ est atteint et $y_* \in C'$ un point où $\min_{y\in C'} +\max_{x\in C} u(x,y)$ l'est. Il s'agit donc de prouver +l'inégalité de sens contraire. + +Commençons par supposer que $C$ est l'enveloppe convexe d'un nombre +fini de points $(x_i)_{i\in I}$ et $C'$ de $(y_j)_{j\in J}$, et on +expliquera plus loin comment se ramener à ce cas (même si c'est le +seul qui servira dans le cadre de la théorie des jeux). Lorsque cette +hypothèse est vérifiée, on va définir une fonction $T\colon C\times C' +\to C\times C'$ de la façon suivante. Donnons-nous $(x,y) \in C\times +C'$. Pour chaque $i\in I$, on définit $\varphi_i(x,y) = \max (0,\; +u(x_i,y)-u(x,y))$, et de même on pose $\psi_j(x,y) = \max (0,\; +u(x,y)-u(x,y_j))$. Posons enfin $T(x,y) = (x^\sharp,y^\sharp)$ où +$x^\sharp$ et $y^\sharp$ (qui dépendent tous les deux de $x$ et $y$ à +la fois, malgré la notation) sont définis comme suit. On appelle +$x^\sharp$ le barycentre de $x$ affecté du coefficient $1$ et des +$x_i$ (pour $i\in I$) affectés des coefficients respectifs +$\varphi_i(x,y)$, c'est-à-dire $x^\sharp = \frac{x + \sum_{i\in I} + \varphi_i(x,y)\,x_i}{1 + \sum_{i\in I} \varphi_i(x,y)}$ ; et soit de +même $y^\sharp$ le barycentre de $y$ avec coefficient $1$ et des $y_i$ +avec les coefficients $\psi_i(x,y)$. Clairement, $x^\sharp$ et +$y^\sharp$ sont dans $C$ et $C'$ respectivement (il s'agit de +barycentres à coefficients positifs, c'est-à-dire de combinaisons +convexes). La fonction $T\colon C\times C' \to C\times C'$ définie +par $T(x,y) = (x^\sharp,y^\sharp)$ est continue. Par ailleurs, on a +$x^\sharp = x$ si et seulement si $x$ réalise $\max_{\tilde x\in C} +u(\tilde x,y)$ (un sens est évident, et pour l'autre il suffit de se +convaincre que s'il existe $\tilde x$ tel que $u(\tilde x,y) > u(x,y)$ +alors il y a un $i$ tel que ceci soit vrai en remplaçant $\tilde x$ +par $x_i$, et on a alors $\varphi_i(x,y)>0$ donc $u(x^\sharp,y) > +u(x,y)$) ; et on a un résultat analogue pour $y$. La fonction $T$ +continue du compact convexe $C\times C'$ vers lui-même y admet un +point fixe $(x_0,y_0)$, vérifiant donc $(x_0^\sharp, y_0^\sharp) = +(x_0,y_0)$, c'est-à-dire que $u (x_0,y_0) = \max_{x\in C} u(x,y_0) = +\min_{y\in C'} u(x_0, y)$. On a donc maintenant +\[ +\max_{x\in C} \min_{y\in C'} u(x,y) +\geq \min_{y\in C'} u(x_0,y) = u(x_0,y_0) += \max_{x\in C} u(x,y_0) \geq +\min_{y\in C'} \max_{x\in C} u(x,y) +\] +ce qu'on voulait. + +Pour se ramener au cas où $C$ et $C'$ sont enveloppes convexes d'un +nombre fini de points, on observe que pour tout $\varepsilon>0$ il +existe $\Sigma$ et $\Sigma'$ des enveloppes convexes d'un nombre fini +de points (= polytopes) contenues dans $C$ et $C'$ respectivement et +telles que pour tout $x\in C$ on ait $\min_{y\in C'} u(x,y) > +\min_{y\in\Sigma'} u(x,y)-\varepsilon$ et $\max_{x\in C} u(x,y) < +\max_{x\in\Sigma} u(x,y)+\varepsilon$ (explication : il est trivial +que pour chaque $x$ il existe un $\Sigma'$ vérifiant la condition +demandée, le point intéressant est qu'un unique $\Sigma'$ peut +convenir pour tous les $x$ ; mais pour chaque $\Sigma'$ donné, +l'ensemble des $x$ pour lesquels il convient est un ouvert de $C$, qui +est compact, donc un nombre fini de ces ouverts recouvrent $C$, et on +prend l'enveloppe convexe de la réunion des $\Sigma'$ en question ; on +procède de même pour $\Sigma$). On a alors $\max_{x\in C} \min_{y\in + C'} u(x,y) > \max_{x\in \Sigma} \min_{y\in \Sigma'} u(x,y) - +\varepsilon$ et une inégalité analogue pour l'autre membre : on en +déduit l'inégalité recherchée à $2\varepsilon$ près, mais comme on +peut prendre $\varepsilon$ arbitrairement petit, on a ce qu'on +voulait. +\end{proof} + +\begin{cor} +Soit $C$ un convexe compact dans un espace affine réel de dimension +finie, et $u\colon C^2 \to \mathbb{R}$ une application bi-affine +antisymétrique (i.e., $u(y,x) = -u(x,y)$). Alors il +existe $x\in C$ tel que pour tout $y\in C$ on ait $u(x,y)\geq 0$ +(et la valeur commune des deux membres de l'égalité du +théorème \ref{theorem-minimax} est $0$). +\end{cor} +\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 +\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 + C}\penalty0 \min_{y\in C} u(x,y) = 0$ (il est son propre opposé), et +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$. + % % % |