6
$\begingroup$

This is a classic theorem in game theory, that is left as an excersice in my textbook. Can anybody proove it? I can not thing of anything excpet from the definition of the correlated equilibrium in first place. Here is the theorem and the definition as well.

$\mathbf{Theorem:}$ For every Nash equilibrium $\sigma^*$, the probability distribution $p_{\sigma^*}$ is a correlated equilibrium.

$\mathbf{Definition:}$ A probability distribution $p$ over the set of action vectors $S$ is called a correlated equilibrium if the strategy vector $\tau^*$ is a Nash equilibrium of the game $\Gamma^*(p)$. In other words, for every player $i ∈ N$:

\begin{equation}\Sigma_{s_{-i}\in S_{-i}}p(s_i,s_{-i})u_i(s_i,s_{-i})\geq \Sigma_{s_{-i}\in S_{-i}}p(s_i,s_{-i})u_i(s^{'}_i,s_{-i}),\quad\text{$\forall s_i,s^{'}_i\in S_i$}\end{equation}

Every strategy vector $\sigma$ induces a probability distribution $p_{\sigma^*}$ over the set of action vector $S$. \begin{equation}p_{\sigma^*}(s_1,...,s_n)=\sigma_1(s_1)\times\sigma_2(s_2)\times...\times\sigma_n(s_n)\end{equation}

$\textit{Hint:}$ When we relate to a Nash equilibrium $\sigma^*$ as a correlated equilibrium we mean the probability distribution $p_{\sigma^*}$ given by the aforementioned equation:

$\endgroup$
5
  • $\begingroup$ @HerrK. how to doublecheck it? $\endgroup$ Sep 7 at 14:42
  • $\begingroup$ Is there any typo? Where did you get the definition from? It seems inconsistent with the version given in the Fudenberg-Tirole textbook. $\endgroup$
    – Herr K.
    Sep 7 at 14:52
  • $\begingroup$ well it is from the Maschler, Solan and Zamir Game theory book, but from what I have seen until now, there are some typos in the book in general. However, I do not know abou the this one? @HerrK. can you write the Fundenberg - Tirole version as well to compare it? $\endgroup$ Sep 7 at 14:55
  • $\begingroup$ @HerrK. I think that this version is the same with the equivalent version of the definition $2.4B$ in page 57 of Fundenberg - Tirole textbook...please check it if you want! Thank you in advance! $\endgroup$ Sep 7 at 15:13
  • $\begingroup$ I now see where the difference is. Sorry for the confusion. $\endgroup$
    – Herr K.
    Sep 7 at 15:23
7
$\begingroup$

A strategy profile $\sigma^*=(\sigma_i^*,\sigma_{-i}^*)$ is a Nash equilibrium if for all player $i$, \begin{equation} u_i(s_i,\sigma_{-i}^*)\ge u_i(s_i',\sigma_{-i}^*), \quad \forall s_i\in\mathrm{supp}(\sigma_i^*), \forall s_i'\in S_i. \end{equation} Rewriting this condition explicitly in terms of the probabilities over pure strategies: \begin{align} \sum_{s_{-i}\in S_{-i}}\sigma_{-i}^*(s_{-i})u_i(s_i,s_{-i}) &\ge \sum_{s_{-i}\in S_{-i}}\sigma_{-i}^*(s_{-i})u_i(s_i',s_{-i}), \quad \forall s_i\in\mathrm{supp}(\sigma_i^*), \forall s_i'\in S_i. \tag{1} \end{align} Let $p_{\sigma^*}(s_i,s_{-i})=\sigma_i^*(s_i)\sigma_{-i}^*(s_{-i})$ be the joint distribution implied by the equilibrium strategies. Then condition $(1)$ can be rewritten as \begin{equation} \sum_{s_{-i}\in S_{-i}}\underbrace{\sigma_i^*(s_i)\sigma_{-i}^*(s_{-i})}_{p_{\sigma^*}(s_i,s_{-i})}u_i(s_i,s_{-i}) \ge \sum_{s_{-i}\in S_{-i}}\underbrace{\sigma_i^*(s_i)\sigma_{-i}^*(s_{-i})}_{p_{\sigma^*}(s_i,s_{-i})}u_i(s_i',s_{-i}), \quad\forall s_i,s_i'\in S_i. \end{equation} This is the definition of correlated equilibrium.

$\endgroup$
7
  • $\begingroup$ I am a bit confused...why we sum only with respect to $\sigma^*_{-i}(s_{-i})$ in the condition $(1)$ and then we chacnge this? I am missing something here.... $\endgroup$ Sep 7 at 15:28
  • 1
    $\begingroup$ Did you mean why $u_i(s_i,\sigma_i)=\sum_{s_{-i}\in S_{-i}} \sigma_{-i}(s_{-i})u_i(s_i,s_{-i})$? $\endgroup$
    – Herr K.
    Sep 7 at 15:32
  • $\begingroup$ Yes! Exactly this is what I mean $\endgroup$ Sep 7 at 15:33
  • $\begingroup$ Well, $u_i(s_i,\sigma_{-i})$ is $i$'s expected utility from playing pure strategy $s_i$ (i.e. with probability $\color{red}{1}$) against the mixed strategy profile $\sigma_{-i}$, so his payoff would be $(\color{red}{1})\sigma_{-i}(s_{-i})u_i(s_i,s_{-i})$. If $i$ were to play a mixed strategy $\sigma_i$, then his expected payoff would be $\color{red}{\sigma_i(s_i)}\sigma_{-i}(s_{-i})u_i(s_i,s_{-i})$ $\endgroup$
    – Herr K.
    Sep 7 at 15:38
  • $\begingroup$ Ok I understand now. One last thing. Is it $u_i(s_i,\sigma_i)=\sum_{s_{-i}\in S_{-i}}\sigma_{-i}(s_{-i})u_i(s_i,s_{-i})$ or $u_i(s_i,\sigma_{-i})=\sum_{s_{-i}\in S_{-i}}\sigma_{-i}(s_{-i})u_i(s_i,s_{-i})$? $\endgroup$ Sep 7 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.