From 089afade67375b6631d038c481faceed70386e98 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Tue, 4 Apr 2017 15:15:59 +0200 Subject: Explain the concept of correlated equilibria. --- notes-mitro206.tex | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 59 insertions(+), 4 deletions(-) (limited to 'notes-mitro206.tex') 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} -- cgit v1.2.3