diff options
| -rw-r--r-- | notes-mitro206.tex | 234 |
1 files changed, 144 insertions, 90 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index 4df00fb..237e5c9 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1283,12 +1283,12 @@ Néanmoins, ce double point de vue ne devrait pas causer de confusion. Ceci conduit à faire la définition suivante : -\begin{defn} +\begin{defn}\label{definition-mixed-strategy-gain} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $s := (s_1,\ldots,s_N) \in S_1 \times \cdots \times S_N$ est un profil de stratégies mixtes, on -appelle \defin[gain espéré]{gain [espéré]} du joueur $i$ selon ce profil la -quantité +appelle \defin[gain espéré]{gain [espéré]} du joueur $i$ selon ce +profil la quantité \[ u_i(s) := \sum_{a\in A} s_1(a_1)\cdots s_N(a_N)\,u_i(a) \] @@ -1629,107 +1629,161 @@ dire que $(s_1,\ldots,s_N)$ est un équilibre de Nash. Autrement dit : \subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games} +Plaçons nous maintenant dans le cadre d'un jeu à somme nulle, +c'est-à-dire qu'il y a $N=2$ joueurs, et qu'ils ont des gains +opposés : disons qu'on appelle $u = u_1$ le gain du joueur $1$ +(« Alice »), le gain du joueur $2$ (« Bob ») étant alors $u_2 = -u$ et +n'a pas besoin d'être écrit dans le tableau. Ainsi, Alice cherche à +\emph{maximiser} $u$ et Bob cherche à le \emph{minimiser} (puisque +maximiser $-u$ revient à minimiser $u$). + +En considérant le jeu du point de vue de sa matrice de gains (où, de +nouveau, on n'a écrit que le gain d'Alice), Alice cherche à choisir +une ligne qui maximiser la valeur écrite dans le tableau et Bob +cherche à choisir une colonne qui mimimise la valeur écrite. Mais en +général, si $u\colon A_1 \times A_2 \to \mathbb{R}$ est un tableau +fini de nombres réels, $\max_{a \in A_1} \min_{b\in A_2} u(a,b)$ ne +coïncide pas avec $\min_{b\in A_2} \max_{a \in A_1} u(a,b)$ (on a +seulement l'inégalité $\max_{a \in A_1} \min_{b\in A_2} u(a,b) \leq +\min_{b\in A_2} \max_{a \in A_1} u(a,b)$, qui sera démontrée ci-dessus +au début de la démonstration de \ref{theorem-minimax}). L'observation +cruciale est que, quand on passe des ensembles finis $A_i$ de +stratégies pures aux simplexes $S_i$ de stratégies mixtes, on a alors +une égalité : + \begin{thm}[« du minimax », J. 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 +Soient $A_1,A_2$ deux ensembles finis et $S_1,S_2$ les simplexes de +stratégies mixtes (cf. \ref{definition-mixed-strategy-abst}) +sur $A_1,A_2$ ; soit $u\colon A_1\times A_2 \to \mathbb{R}$ une +fonction quelconque, et on notera encore $u$ son unique extension +(explicitée en \ref{definition-mixed-strategy-gain}) en une fonction +$S_1\times S_2 \to \mathbb{R}$ affine en chaque variable. On a +alors : \[ -\max_{x\in C} \min_{y\in C'} u(x,y) = -\min_{y\in C'} \max_{x\in C} u(x,y) +\max_{x\in S_1} \min_{y\in S_2} u(x,y) = +\min_{y\in S_2} \max_{x\in S_1} u(x,y) \] + +Plus généralement, si $S_1$ et $S_2$ sont deux convexes compacts dans +des espaces affines réels de dimension finie, et $u\colon S_1\times +S_2 \to \mathbb{R}$ une application affine en chaque variable +séparément, alors on a l'égalité ci-dessus. \end{thm} \begin{proof} -Tout d'abord, l'inégalité dans un sens est évidente : on a +Plaçons-nous d'abord dans le cas (qui intéresse la théorie des jeux) +où $A_1,A_2$ sont deux ensembles finis et $S_1,S_2$ les simplexes de +stratégies mixtes. + +Tout d'abord, l'inégalité dans le sens $\max\min \leq \min\max$ est +facile : 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) +\max_{x\in S_1} \min_{y\in S_2} u(x,y) += \min_{y\in S_2} u(x_*,y) +\leq u(x_*,y_*) \leq \max_{x\in S_1} u(x,y_*) = +\min_{y\in S_2} \max_{x\in S_1} 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 -d'après \ref{brouwer-fixed-point-theorem} 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 +où $x_* \in S_1$ est un point où $\max_{x\in S_1} \min_{y\in S_2} +u(x,y)$ est atteint et $y_* \in S_2$ un point où $\min_{y\in S_2} +\max_{x\in S_1} u(x,y)$ l'est (ces extrema existent car on a affaire à +une fonction continue sur un compact, ou bien +d'après \ref{affine-functions-take-extrema-at-boundary} car on a +affaire à une fonction affine sur l'enveloppe convexe d'un nombre fini +de points) : la première relation est la définition de $x_*$, la +seconde est la définition du $\min$, la troisième la définition du +$\max$, et la quatrième est la définition de $y_*$. (Notons que tout +ceci vaut dans n'importe quel contexte où les $\min$ et $\max$ +existent, notamment ceci prouve $\max_{a \in A_1} \min_{b\in A_2} +u(a,b) \leq \min_{b\in A_2} \max_{a \in A_1} u(a,b)$ affirmé +ci-dessus.) + +Il s'agit maintenant de prouver l'inégalité de sens contraire. + +Considérons $(x_0,y_0)$ un équilibre de Nash du jeu à somme nulle dont +la matrice de gains est donnée par $u$ pour le joueur $1$ (et $-u$ +pour le joueur $2$) : on sait qu'un tel équilibre existe +d'après \ref{theorem-nash-equilibria}. On a alors \[ -\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) +\max_{x\in S_1} \min_{y\in S_2} u(x,y) +\geq \min_{y\in S_2} u(x_0,y) = u(x_0,y_0) += \max_{x\in S_1} u(x,y_0) \geq +\min_{y\in S_2} \max_{x\in S_1} 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. +Ici, la première relation est la définition du $\max$, la seconde +traduit le fait que (dans la définition de l'équilibre de Nash) Bob +fait une meilleure réponse possible à $x_0$, la troisième traduit le +fait qu'Alice fait une meilleure réponse possible à $y_0$, et la +quatrième est la définition du $\min$. + +Ceci achève de montrer $\max_{x\in S_1} \min_{y\in S_2} u(x,y) = +\min_{y\in S_2} \max_{x\in S_1} u(x,y)$ lorsque $S_1$ et $S_2$ sont +deux simplexes dans $\mathbb{R}^n$, et $u\colon S_1\times S_2 \to +\mathbb{R}$ une application affine en chaque variable séparément. Si +maintenant $S_1$ et $S_2$ sont deux polytopes, c'est-à-dire chacun +l'enveloppe d'un nombre fini de points $A_1$ et $A_2$ +dans $\mathbb{R}^n$, mais plus forcément des simplexes (c'est-à-dire +qu'on ne suppose plus les points de $A_i$ affinement indépendants), la +même conclusion vaut encore : en effet, si on appelle $S'_i$ le +simplexe construit abstraitement sur $A_i$ (i.e., l'ensemble des +fonctions $s\colon A_i \to \mathbb{R}$ positives de somme $1$), et +$\varpi_i \colon S'_i \to S_i$ la fonction (affine et surjective) +envoyant $s\colon A_i \to \mathbb{R}$ positive de somme $1$ sur la +somme des $s(a)\cdot a$ (dans le $\mathbb{R}^n$ où vivent $A_i$ +et $S_i$), alors la fonction $u\colon S_1\times S_2 \to \mathbb{R}$ +donnée définit une fonction $u'\colon S'_1\times S'_2 \to \mathbb{R}$, +elle aussi affine en chaque variable, par $u'(x,y) = u(\varpi_1(x), +\varpi_2(y))$, et il est évident que les extrema de $u'$ sur $S'_1 +\times S'_2$ coïncident avec ceux de $u$ sur $S_1 \times S_2$, donc la +conclusion qui précède, appliquée à $u'$, donne la conclusion désirée +sur $u$. + +Enfin, si $S_1$ et $S_2$ sont seulement supposés être des convexes +compacts dans $\mathbb{R}^n$, on observe que pour tout $\varepsilon>0$ +il existe $\Sigma_1$ et $\Sigma_2$ des polytopes contenus dans $S_1$ +et $S_2$ respectivement et tels que pour tout $x\in S_1$ on ait +$\min_{y\in S_2} u(x,y) > \min_{y\in\Sigma_2} u(x,y)-\varepsilon$ et +$\max_{x\in S_1} u(x,y) < \max_{x\in\Sigma_1} u(x,y)+\varepsilon$ +(explication : il est trivial que pour chaque $x$ il existe un +$\Sigma_2$ vérifiant la condition demandée, le point intéressant est +qu'un unique $\Sigma_2$ peut convenir pour tous les $x$ ; mais pour +chaque $\Sigma_2$ donné, l'ensemble des $x$ pour lesquels il convient +est un ouvert de $S_1$, qui est compact, donc un nombre fini de ces +ouverts recouvrent $S_1$, et on prend l'enveloppe convexe de la +réunion des $\Sigma_2$ en question ; on procède de même pour +$\Sigma_1$). On a alors $\max_{x\in S_1} \min_{y\in S_2} u(x,y) > +\max_{x\in \Sigma_1} \min_{y\in \Sigma_2} 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} +Le corollaire suivant explicite la situation particulière où, en +outre, le jeu est symétrique entre les deux joueurs (c'est-à-dire que +sa matrice de gains écrite pour un seul joueur est, elle, +\emph{anti}symétrique) : + \begin{cor}\label{symmetric-zero-sum-game} -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$). +Soient $A$ un ensemble fini et $S$ le simplexe de stratégies mixtes +sur $A$ ; soit $u\colon A^2 \to \mathbb{R}$ une application +antisymétrique (i.e., $u(b,a) = -u(a,b)$), et on notera encore $u$ son +unique extension affine en chaque variable en une fonction $S^2 \to +\mathbb{R}$ affine en chaque variable. Alors la valeur commune des +deux membres de l'égalité du théorème \ref{theorem-minimax} est $0$ : +il existe $x\in S$ tel que pour tout $y\in S$ on ait $u(x,y)\geq 0$. + +Plus généralement, si $S$ est un convexe compact dans un espace affine +réel de dimension finie, et $u\colon S^2 \to \mathbb{R}$ une +application antisymétrique (i.e., $u(y,x) = -u(x,y)$) et affine en +chaque variable séparément, la même conclusion vaut. \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} -\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) = +On applique le théorème : il donne $\max_{x\in S}\penalty0 \min_{y\in + S} u(x,y) = \min_{y\in S}\penalty0 \max_{x\in S} u(x,y)$. Mais +puisque $u$ est antisymétrique ceci s'écrit encore $\min_{y\in S} +\max_{x\in S} (-u(y,x))$, soit, en renommant les variables liées, +$\min_{x\in S}\penalty0 \max_{y\in S} (-u(x,y)) = -\max_{x\in + S}\penalty0 \min_{y\in S} u(x,y)$. Par conséquent, $\max_{x\in + S}\penalty0 \min_{y\in S} u(x,y) = 0$ (il est son propre opposé), et +en prenant un $x$ qui réalise ce maximum, on a $\min_{y\in S} u(x,y) = 0$, ce qu'on voulait prouver. \end{proof} |