Explain the concept of correlated equilibria.

1 files changed, 59 insertions, 4 deletions

diff --git a/notes-mitro206.tex b/notes-mitro206.tex
index 95a6024..4679aef 100644
--- a/notes-mitro206.tex
+++ b/notes-mitro206.tex
@@ -1130,7 +1130,8 @@ Naturellement, si chaque composante est une stratégie pure, on pourra
 parler de profil de stratégies pures.
 \end{defn}
 
-\thingy Il va de soi qu'un profil de stratégies mixtes, i.e., un
+\thingy\label{remark-mixed-stragy-profile-versus-correlated-profile}
+Il va de soi qu'un profil de stratégies mixtes, i.e., un
 élément de $S := S_1 \times \cdots \times S_N$, i.e., la donnée d'une
 distribution de probabilité sur chaque $A_i$, n'est pas la même chose
 qu'une distribution de probabilités sur $A := A_1 \times \cdots \times
@@ -1144,7 +1145,7 @@ $s(a_1,\ldots,a_N) = s_1(a_1)\cdots s_N(a_N)$ (produit des
 $s_i(a_i)$).  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 n'est pas un problème car $s_i$ se déduit
-de $s$ : précisément, $s_i(b) = \sum_{a: a_i = b} s(a)$ où la somme
+de $s$ : précisément, $s_i(b) = \sum_{a\,:\, a_i = b} s(a)$ où la somme
 est prise sur les $a \in A$ tels que $a_i = b$).
 
 \danger (Il faudra prendre garde au fait qu'on peut voir $S$ soit
@@ -1215,8 +1216,8 @@ que le joueur $i$, il existe une meilleure réponse pour le joueur $i$
 qui est une stratégie pure.  De plus, si $s_!$ (stratégie mixte) est
 une meilleure réponse contre $s_?$ si et seulement si \emph{chaque}
 stratégie pure appartenant au support de $s_!$ est une meilleure
-réponse possible contre $s_?$ (et elles apportent toutes le même
-gain).
+réponse possible contre $s_?$ ; et elles apportent toutes le même
+gain.
 
 En particulier, une meilleure réponse stricte est nécessairement une
 stratégie pure.
@@ -1359,6 +1360,60 @@ 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 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
+probabilités sur l'ensemble $A$ des profils de stratégies pures (le
+rapport avec l'ensemble des profils de stratégies mixtes est explicité
+en \ref{remark-mixed-stragy-profile-versus-correlated-profile}), on
+dit que $s$ est un \index{corrélé (équilibre)}\defin{équilibre
+  corrélé} lorsque pour tout $1 \leq i \leq N$ et pour tous $b,b' \in
+A_i$ on a
+\[
+\sum_{a\,:\, a_i = b} s(a)\,(u_i(a) - u_i(a_{?i},b'))\geq 0
+\]
+où la somme est prise sur les $a \in A$ tels que $a_i = b$ et où
+$u_i(a_{?i},b')$ désigne bien sûr la valeur de $u_i$ en l'élément de
+$A$ égal à $a$ sauf que la $i$-ième coordonnée (qui vaut $b$) a été
+remplacée par $b'$.
+
+De façon plus intuitive, il faut imaginer qu'un « corrélateur » tire
+au hasard un profil $a$ de stratégies pures selon la distribution $s$,
+et la condition d'équilibre indiquée ci-dessus signifie que si chaque
+joueur $i$ reçoit l'information ($b = a_i$) de l'option qui a été
+tirée pour lui, tant que les autres joueurs suivent les instructions
+($a_{?i}$) du corrélateur, il n'a pas intérêt à choisir une autre
+option ($b'$) que celle qui lui est proposée.
+
+Pour dire les choses autrement, faisons les définitions suivantes.
+Lorsque $s_{?}$ une distribution de probabilités sur $A_{?i} :=
+A_1\times \cdots \penalty500 \times A_{i-1} \penalty0 \times \penalty0
+A_{i+1} \times\cdots \penalty500 \times A_N$ et $b \in A_i$, notons
+$u_i(s_?, b) := \sum_{a_? \in A_{?i}} s_?(a_?)\,u_i(a_?, b)$ le gain
+espéré du joueur $i$ lorsque l'ensemble des autres joueurs joue un
+profil tiré selon $s_?$ et que $i$ joue $b$.  Lorsque $s$ est une
+distribution de probabilités sur $A$, appelons $s[b]$ (pour $b\in A_i$
+tel que $\sum_{a'\,:\, a'_i=b} s(a') > 0$) la distribution de
+probabilités $s$ conditionnée à $a_i = b$ et projetée à $A_{?i}$,
+c'est-à-dire concrètement la distribution qui à $a_? \in A_{?i}$
+associe $s(a_?, b)/\sum_{a'_? \in A_{?i}} s(a'_?, b)$.  La condition
+que $s$ soit un équilibre corrélé se réécrit alors en : $u_i(s[b], b)
+\geq u_i(s[b], b')$ pour tout $b\in A_i$ tel que $\sum_{a'\,:\,
+  a'_i=b} s(a') > 0$ et tout $b'\in A_i$.
+
+Dans le cas particulier où $s$ est une distribution aux marginales
+indépendantes, c'est-à-dire de la forme $s(a) = s_1(a_1) \cdots
+s_N(a_N)$
+(cf. \ref{remark-mixed-stragy-profile-versus-correlated-profile}), ce
+qu'on a noté $s[b]$ ci-dessus est précisément la fonction qui à $a_?
+\in A_{?i}$ associe le produit $s_{?i}$ des $s_j(a_j)$ pour $j\neq i$,
+et la condition qu'on vient de dire est donc $u_i(s_{?i}, b) \geq
+u_i(s_{?i}, b')$ pour tout $b$ dans le support de $s_i$ et tout $b'$.
+D'après \ref{stupid-remark-best-mixed-strategies}, c'est justement
+dire que $(s_1,\ldots,s_N)$ est un équilibre de Nash.  Autrement dit :
+\emph{un équilibre de Nash est la même chose qu'un équilibre corrélé
+  dans lequel les marginales se trouvent être indépendantes}.
+
 
 
 \subsection{Jeux à somme nulle : le théorème du minimax}\label{zero-sum-games}