From 60dc1417d6d1540fe7be47206a70aafac0b55476 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Sun, 20 Feb 2022 13:50:06 +0100 Subject: Rework the section on Nash equilibria (clarify a few things and add an extended example). --- notes-mitro206.tex | 185 +++++++++++++++++++++++++++++++++++++++-------------- 1 file 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 $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