diff options
| -rw-r--r-- | notes-mitro206.tex | 185 |
1 files changed, 137 insertions, 48 deletions
diff --git a/notes-mitro206.tex b/notes-mitro206.tex index c125348..4df00fb 100644 --- a/notes-mitro206.tex +++ b/notes-mitro206.tex @@ -1117,22 +1117,24 @@ comme les éléments de $A$ sont dans $C$, ceci montre bien $\max\{u(s) \end{proof} \begin{prop}\label{affine-functions-take-no-strict-extrema-inside} -Reprenons le contexte de la proposition précédente ($A \subseteq +Reprenant le contexte de la proposition précédente ($A \subseteq \mathbb{R}^m$ un ensemble fini, $C$ son enveloppe convexe, et $u -\colon \mathbb{R}^m \to \mathbb{R}$ affine), et soit $M := \max_{a \in - A} u$ (dont on vient de voir que c'est aussi $\max_{s\in C} u$) : si +\colon \mathbb{R}^m \to \mathbb{R}$ affine), soit $M := \max_{a \in A} +u$ (dont on vient de voir que c'est aussi $\max_{s\in C} u$) : alors une combinaison convexe $s$ à coefficients \emph{strictement positifs} de points de $A$ (i.e., $s = \sum_{i=1}^n \lambda_i x_i$ avec $x_i \in A$ et $\lambda_i > 0$ vérifiant $\sum_{i=1}^n \lambda_i = 1$) vérifie -$u(s) = M$, alors chacun des points en question vérifie aussi cette -propriété (i.e., on a $u(x_i) = M$ pour tout $i$). +$u(s) = M$, si et seulement si chacun des points en question vérifie +aussi cette propriété (i.e., on a $u(x_i) = M$ pour tout $i$). \end{prop} \begin{proof} -Si on a $u(x_j) < M$ pour un certain $j$, alors on a $\lambda_j u(x_j) -< \lambda_j M$, donc en sommant avec les autres $\lambda_i u(x_i) \leq -\lambda_i M$ on trouve $u(s) = \sum_{i=1}^n \lambda_i u(x_i) < -\sum_{i=1}^n \lambda_i M = M$. +On vient de voir que $u(x_i) \leq M$ pour tout $i$ implique $u(s) \leq +M$. Si on a $u(x_j) < M$ pour un certain $j$, alors on a $\lambda_j +u(x_j) < \lambda_j M$, donc en sommant avec les autres $\lambda_i +u(x_i) \leq \lambda_i M$ on trouve $u(s) = \sum_{i=1}^n \lambda_i +u(x_i) < \sum_{i=1}^n \lambda_i M = M$. Réciproquement, si $u(x_i) = +M$ pour tout $i$, il est évident que $u(s) = M$. \end{proof} On peut aussi reformuler ce résultat en affirmant que la partie de $C$ @@ -1250,13 +1252,15 @@ de même, les pièces tirées par Alice et Bob sont des variables aléatoires indépendantes). Les distributions de probabilités $s$ sur $A$ définies par la formule ($*$) sont précisément celles dont composantes sont indépendantes, et qui sont alors complètement -déterminées par leurs -\emph{marginales}\footnote{\label{footnote-marginals}La $i$-ième - marginale d'une distribution de probabilités $s \colon A \to - \mathbb{R}$ est la distribution de probabilités $s_i \colon A_i \to - \mathbb{R}$ qui à $b\in A_i$ associe la somme des - $s(a_1,\ldots,a_N)$ prise sur tous les $N$-uplets $(a_1,\ldots,a_N)$ - tels que $a_i = b$.} $s_1,\ldots,s_N$. +déterminées par leurs \emph{distributions + marginales}\footnote{\label{footnote-marginals}La $i$-ième marginale + d'une variable aléatoire sur $A_1\times \cdots \times A_N$ est + simplement sa $i$-ième composante (= projection sur $A_i$). La + $i$-ième distribution marginale de la distribution de probabilités + $s \colon A \to \mathbb{R}$ est donc la distribution de probabilités + $s_i \colon A_i \to \mathbb{R}$ qui à $b\in A_i$ associe la somme + des $s(a_1,\ldots,a_N)$ prise sur tous les $N$-uplets + $(a_1,\ldots,a_N)$ tels que $a_i = b$.} $s_1,\ldots,s_N$. On identifiera parfois abusivement l'élément $(s_1,\ldots,s_N) \in S$ à la distribution $s\colon A\to\mathbb{R}$ qu'on vient de décrire (ce @@ -1329,6 +1333,15 @@ la stratégie $s_i$ pour le joueur $i$ est une meilleure réponse les autres joueurs obtenu en supprimant la composante $s_i$ de $s$. \end{defn} +Concrètement, donc, un équilibre de Nash est donc un profil de +stratégies mixtes de l'ensemble des joueurs dans lequel \emph{aucun + joueur n'a intérêt à changer unilatéralement sa stratégie} (au sens +où faire un tel changement lui apporterait une espérance de gain +strictement supérieure). Un équilibre de Nash \emph{strict} +correspond à la situation où tout changement unilatéral de stratégie +d'un joueur lui apporterait une espérance de gain strictement +inférieure. + \begin{prop}\label{stupid-remark-best-mixed-strategies} Donné un jeu en forme normale comme en \ref{definition-game-in-normal-form}, si $1 \leq i \leq N$ et si @@ -1344,28 +1357,43 @@ En particulier, une meilleure réponse stricte est nécessairement une stratégie pure. \end{prop} \begin{proof} -Tout ceci résulte du fait que le gain espéré $u_i(s_?,t)$ est une -fonction affine de $t \in S_i$ (et une fonction affine sur un simplexe -prend son maximum — ou son minimum — sur un des sommets de ce -simplexe, et ne peut le prendre à l'intérieur que si elle prend aussi -cette valeur sur les sommets). - -Plus précisément : $u_i(s_?,t)$ (pour $t \in S_i$) est combinaison -convexe avec pour coefficients $t(a)$ pour $a\in A_i$, des -$u_i(s_?,a)$. Si $v$ est le maximum des $u_i(s_?,a)$ (qui sont en -nombre fini donc ce maximum existe), alors $v$ est aussi le maximum de -toute combinaison convexe $u_i(s_?,t)$ des $u_i(s_?,a)$ : c'est-à-dire -que $t\in S_i$ est une meilleure réponse possible contre $s_?$ si et -seulement si $u_i(s_?,t) = v$. En particulier, tout $a \in A_i$ qui -réalise ce maximum $v$ est une meilleure réponse possible -(contre $s_?$) qui est une stratégie pure. D'autre part, une -combinaison convexe $u_i(s_?,t)$ de valeurs $\leq v$ ne peut être -égale à $v$ que si toutes les valeurs $u_i(s_?,a)$ entrant -effectivement (c'est-à-dire avec un coefficient $>0$) dans la -combinaison sont égales à $v$ (s'il y en avait une $<v$, elle -entraînerait forcément une moyenne pondérée $<v$), et réciproquement. +Tout ceci résulte essentiellement des propositions +\ref{affine-functions-take-no-strict-extrema-inside} +et \ref{affine-functions-take-extrema-at-boundary} : le gain espéré +$u_i(s_?,t)$ du joueur $i$ (une fois fixé le profi $s_?$ de tous les +autres joueurs) est une fonction affine de la stratégie $t \in S_i$ du +joueur $i$, et une fonction affine sur un simplexe prend son maximum +sur un sommet du simplexe, et ne peut la prendre à l'intérieure que si +elle la prend également en chaque sommet. + +Plus précisément, soit $v = \max_{t \in S_i} u_i(s_?,t)$, dont la +proposition \ref{affine-functions-take-no-strict-extrema-inside} +garantit l'existence ; une meilleure réponse possible contre $s_?$ est +précisément un $t$ réalisant $u_i(s_?,t) = v$ : il résulte de la +proposition citée que $v$ est aussi $\max_{a \in A_i} u_i(s_?,a)$, +c'est-à-dire qu'il existe une stratégie \emph{pure} $a \in A_i$ qui +est une meilleure réponse possible contre $s_?$. Par ailleurs, si +$s_!$ est une meilleure réponse, i.e., $u_i(s_?,s_!) = v$, alors la +proposition \ref{affine-functions-take-extrema-at-boundary} (appliquée +avec pour $x_1,\ldots,x_n$ les points du support de $s_!$) montre que +chaque stratégie pure $a$ appartenant au support de $s_!$ vérifie +aussi $u_i(s_?,a) = v$. + +Comme une meilleure réponse stricte est unique, elle est forcément +pure d'après ce qu'on vient de voir. \end{proof} +On vient de voir que \emph{lorsque les stratégies de tous les autres + joueurs sont fixées} (à $s_?$ dans la proposition ci-dessus), le +joueur $i$ a une meilleure réponse en stratégie pure : on pourrait +être tenté d'en conclure, mais ce serait une erreur, que les +stratégies mixtes n'apportent donc rien à l'histoire, et qu'un +équilibre de Nash existe forcément en stratégies pures : \emph{ce + n'est pas le cas}. Néanmoins, les équilibres de Nash existent bien +en stratégies mixtes, et c'est le résultat central du domaine (ayant +essentiellement valu à son auteur le prix d'économie de la banque de +Suède à la mémoire d'Alfred Nobel en 1994) : + \begin{thm}[John Nash, 1951]\label{theorem-nash-equilibria} Pour un jeu en forme normale comme en \ref{definition-game-in-normal-form}, il existe un équilibre de @@ -1461,18 +1489,18 @@ Pour $N=2$, une méthode qui peut fonctionner dans des cas suffisamment petits consiste à énumérer tous les supports (cf. \ref{definition-mixed-strategy-abst}) possibles des stratégies mixtes des joueurs dans un équilibre de Nash, c'est-à-dire toutes les -$(2^{\#A_1}-1)\penalty0\times\penalty0(2^{\#A_2}-1)$ -données de parties non vides de -$A_1$ et $A_2$, et, pour chacune, appliquer le raisonnement suivant : -si $s_i$ est une meilleure réponse possible pour le joueur $i$ (contre -la stratégie $s_{?i}$ de l'autre joueur) alors \emph{toutes les - options du support de $s_i$ ont la même espérance de gain} -(contre $s_{?i}$ ; cf. \ref{stupid-remark-best-mixed-strategies}), ce -qui fournit un jeu d'égalités linéaires sur les valeurs de $s_{?i}$. -En rassemblant ces inégalités (ainsi que celles qui affirment que la -somme des valeurs de $s_i$ et de $s_{?i}$ valent $1$), on arrive -« normalement » à trouver tous les équilibres de Nash possibles : voir -les exercices +$(2^{\#A_1}-1)\penalty0\times\penalty0(2^{\#A_2}-1)$ données de +parties non vides de $A_1$ et $A_2$, et, pour chacune, appliquer le +raisonnement suivant : si $s_i$ est une meilleure réponse possible +pour le joueur $i$ (contre la stratégie $s_{?i}$ de l'autre joueur) +alors \emph{toutes les options du support de $s_i$ ont la même + espérance de gain} (contre $s_{?i}$ ; +cf. \ref{stupid-remark-best-mixed-strategies}), ce qui fournit un jeu +d'égalités linéaires sur les valeurs de $s_{?i}$. En rassemblant ces +inégalités (ainsi que celles qui affirment que la somme des valeurs de +$s_i$ et de $s_{?i}$ valent $1$), on arrive « normalement » à trouver +tous les équilibres de Nash possibles : voir \ref{dove-or-hawk} +ci-dessous, ainsi que les exercices \ref{normal-form-game-exercise-two-by-two} et \ref{normal-form-game-exercise-three-by-three} (dernières questions) pour des exemples. @@ -1482,6 +1510,67 @@ algorithmiquement possible en théorie en vertu d'un théorème de Tarski et Seidenberg sur la décidabilité des systèmes d'équations algébriques réels, mais possiblement inextricable dans la pratique.) +\thingy\label{dove-or-hawk-redux} Pour donner un exemple, revenons sur +le \index{trouillard (jeu du)}jeu du trouillard défini +en \ref{dove-or-hawk} et dressons un tableau de l'espérance de gain +pour quelques stratégies mixtes ainsi que la stratégie mixte +« générique » : + +{\footnotesize +\begin{center} +\begin{tabular}{r|c|c|c|c|c|} +$\downarrow$Alice, Bob$\rightarrow$&Colombe&Faucon&$\frac{2}{3}C+\frac{1}{3}F$&$\frac{1}{2}C+\frac{1}{2}F$&$qC+(1-q)F$\\\hline +Colombe&$2,2$&\textcolor{blue}{$0,4$}&$\frac{4}{3},\frac{8}{3}$&$1,3$&{\tiny $2q, 4-2q$}\\\hline +Faucon&\textcolor{blue}{$4,0$}&$-4,-4$&$\frac{4}{3},-\frac{4}{3}$&$0,-2$&{\tiny $-4+8q, -4+4q$}\\\hline +$\frac{2}{3}C+\frac{1}{3}F$&$\frac{8}{3},\frac{4}{3}$&$-\frac{4}{3},\frac{4}{3}$&\textcolor{blue}{$\frac{4}{3},\frac{4}{3}$}&$\frac{2}{3},\frac{4}{3}$&{\tiny $-\frac{4}{3}+4q, \frac{4}{3}$}\\\hline +$\frac{1}{2}C+\frac{1}{2}F$&$3,1$&$-2,0$&$\frac{4}{3},\frac{2}{3}$&$\frac{1}{2},\frac{1}{2}$&$-2+5q,q$\\\hline +$pC+(1-p)F$&{\tiny $4-2p,2p$}&{\tiny $-4+2p,-4+8p$}&{\tiny $\frac{4}{3},-\frac{4}{3}+4p$}&{\tiny $p,-2+5p$}&$(\dagger)$\\\hline +\end{tabular} +\end{center} +\par\noindent +où $(\dagger) = (-4 + 4p + 8q - 6pq, - 4 + 8p + 4q - 6pq)$. +\par} + +\smallskip + +Les trois profils $(C,F)$ (i.e., Alice joue Colombe et Bob joue +Faucon), $(F,C)$ et $(\frac{2}{3}C+\frac{1}{3}F, +\frac{2}{3}C+\frac{1}{3}F)$ sont des équilibres de Nash : cela résulte +du fait que, quand on regarde la case correspondante du tableau, le +premier nombre est maximum sur la colonne (c'est-à-dire qu'Alice n'a +pas intérêt à changer unilatéralement sa stratégie) et le second est +maximum sur la ligne (c'est-à-dire que Bob n'a pas intérêt à changer +unilatéralement sa stratégie) : chacun de ces maxima peut se tester +simplement contre les stratégies pures de l'adversaire (i.e., les deux +premières lignes ou colonnes). Pour trouver ces équilibres et +vérifier qu'il n'y en a pas d'autre, on peut : +\begin{itemize} +\item commencer par rechercher les équilibres de Nash où chacun des + deux joueurs joue une stratégie pure (ceci revient à regarder + chacune des quatre cases du tableau initial et chercher si le + premier nombre est maximal sur la colonne et le second maximal sur + la ligne) ; +\item considérer la possibilité d'un équilibre de Nash où l'un des + joueurs joue une stratégie pure et l'autre une stratégie mixte + supportée par les deux options : si par exemple Alice joue + $pC+(1-p)F$ avec $p>0$ et Bob joue $a \in \{C,F\}$, + d'après \ref{stupid-remark-best-mixed-strategies}, le gain d'Alice + dans les cases $(C,a)$ et $(F,a)$ doit être le même, ce qui n'est + pas le cas, donc il n'y a pas de tel équilibre (pas plus que dans le + cas symétrique) ; +\item enfin, rechercher les équilibres de Nash où chacun des deux + joueurs joue une stratégie supportée par les deux options, soit ici + $pC+(1-p)F$ pour Alice et $qC+(1-q)F$ pour Bob avec $0<p<1$ et + $0<q<1$ : d'après \ref{stupid-remark-best-mixed-strategies} le gain + espéré d'Alice doit être le même contre $qC+(1-q)F$ indifféremment + qu'elle joue Colombe ou Faucon, ce qui implique $2q = -4+8q$ donc + $q=\frac{2}{3}$, et symétriquement, le gain espéré de Bob doit être + le même contre $pC+(1-p)F$ indifféremment qu'il joue Colombe ou + Faucon, ce qui implique $2p = -4+8p$ donc $p=\frac{2}{3}$, si bien + que le seul équilibre de Nash de cette nature est celui qu'on a + décrit (et il faut vérifier qu'il en est bien un). +\end{itemize} + \thingy Mentionnons en complément une notion plus générale que celle d'équilibre de Nash : si $s\colon A \to \mathbb{R}$ (où $A := A_1\times\cdots\times A_N$) est cette fois une distribution de |