summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2022-02-20 13:50:06 +0100
committerDavid A. Madore <david+git@madore.org>2022-02-20 13:50:06 +0100
commit60dc1417d6d1540fe7be47206a70aafac0b55476 (patch)
tree6ed142cc2e76b07050577da81a3299aceb7d37e4
parent6696dadf0f16c9943d38d5b3c0ecadaebe669741 (diff)
downloadmitro206-60dc1417d6d1540fe7be47206a70aafac0b55476.tar.gz
mitro206-60dc1417d6d1540fe7be47206a70aafac0b55476.tar.bz2
mitro206-60dc1417d6d1540fe7be47206a70aafac0b55476.zip
Rework the section on Nash equilibria (clarify a few things and add an extended example).
-rw-r--r--notes-mitro206.tex185
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