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, 2021 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, 2021 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, 2021 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, 2021 at 15:13
  • $\begingroup$ I now see where the difference is. Sorry for the confusion. $\endgroup$
    – Herr K.
    Sep 7, 2021 at 15:23

1 Answer 1

9
$\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, 2021 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, 2021 at 15:32
  • $\begingroup$ Yes! Exactly this is what I mean $\endgroup$ Sep 7, 2021 at 15:33
  • 1
    $\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, 2021 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, 2021 at 15:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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