summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-04-04 13:15:59 (GMT)
committerDavid A. Madore <david+git@madore.org>2017-04-04 13:15:59 (GMT)
commit089afade67375b6631d038c481faceed70386e98 (patch)
tree7f964e3e67761751fc26d3caa0827158dde3dabe
parentb6d32def9abe12c902161e308cf5a18e99099e68 (diff)
downloadmitro206-089afade67375b6631d038c481faceed70386e98.zip
mitro206-089afade67375b6631d038c481faceed70386e98.tar.gz
mitro206-089afade67375b6631d038c481faceed70386e98.tar.bz2
Explain the concept of correlated equilibria.
-rw-r--r--notes-mitro206.tex63
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}