5
$\begingroup$

What is the difference between the correlated equilibrium with the mixed strategy Nash equilibrium? Even further, how is this related to the Bayesian correlated equilibrium with complete or incomplete information?

I have seen the formal definition here, but can anyone provide some example and give th intuition behind this?

$\endgroup$
0
9
$\begingroup$

Correlated equilibrium concepts are often related to communication, most easily implemented via a mediator. Communication can archive two things. It helps with coordination and it can transmit private information. In games of complete information, there is no private information and only the first part matters.

Let's start with the case of complete information:

Ann and Bob play a simultaneous move game. They can choose their actions at random. If their random action choices are mutually best responses, they are playing a mixed strategy Nash equilibrium.

Now, Ann and Bob hire a mediator, Claire, to help them coordinate. Claire randomly selects what both Ann and Bob should do, tells Ann what she should do, and tells Bob what he should do. If Ann and Bob are always willing to follow Claire's recommendations, we have a correlated equilibrium. Since Claire could mimic individual randomizations, every mixed strategy Nash equilibrium can be implemented by Claire and is, therefore, a correlated equilibrium.

Let's add incomplete information:

Ann and Bob have now private information, but Claire does not know anything Ann or Bob does not. Now Claire asks Ann and Bob for their private information and only then makes a recommendation as before. If both Anna and Bob are always willing to tell Claire their private information and are also willing to follow her recommendation, we have a communication equilibrium.

Ann and Bob have now private information and so does Claire. In particular, Claire can make recommendations that use private information neither Ann nor Bob have. Now Claire asks Ann and Bob for their private information and only then makes a recommendation as before. If both Anna and Bob are always willing to tell Claire their private information and are also willing to follow her recommendation, we have a Bayes correlated equilibrium.

Apart from Bayes correlated equilibria, you can find a nice discussion of these concepts in Myerson's graduate game theory textbook "Game Theory: Analysis of Conflict" in Chapter 6.

$\endgroup$
5
  • 1
    $\begingroup$ "If their [independent] random action choices are" $\endgroup$
    – Giskard
    Aug 17 at 9:16
  • 1
    $\begingroup$ How would you choose correlated random action choices? $\endgroup$ Aug 17 at 9:32
  • 1
    $\begingroup$ Via a human mediator, computer or a physical randomization device such as playing cards. I think your point, that these are not present, should be stated explicitly in this case, to highlight the difference. $\endgroup$
    – Giskard
    Aug 17 at 9:47
  • 1
    $\begingroup$ Ok, one question I have in mind has to do with the following. How can the mediator, nameley Claire, be sure about the facth that Ann and Bob will always reveal their true private information to her? In such case, has anyone tried to solve this problem? $\endgroup$
    – Nav89
    Aug 17 at 10:30
  • 1
    $\begingroup$ @Nav89 It is an explicit requirement that it is optimal for Ann to reveal her info to Claire and follow her recommendation afterward, assuming Bob does too. The same holds with the roles of Ann and Bob reversed. $\endgroup$ Aug 17 at 11:47
9
$\begingroup$

An example to highlight the difference between correlated and uncorrelated random strategies in games of perfect information. Consider a game of Chicken with the payoff matrix

Straight Chicken
Straight $0,0$ $7,2$
Chicken $2,7$ $6,6$

Now assume the players decide what to do by drawing a card from a deck. The deck has only three cards, one of which is a king, the other two are not. Upon drawing the king a player will keep going Straight, otherwise they will Swerve/Chicken out.

If the draws are independent, i.e. there are two separate decks to draw from (or a player replaces their card after drawing), then each player will go Straight with a probability of $1/3$, and they will Swerve/Chicken out with a probability of $2/3$. The strategies are "uncorrelated", the random events are independent of each other.

However if the draws are not independent, there is only one deck and the players do not replace their cards after drawing, they are playing correlated strategies. The probabilies of each strategy profile are:

Straight Chicken
Straight $0$ $1/3$
Chicken $1/3$ $1/3$

It can also be verified that with the payoffs above the independent draw yields the mixed strategy Nash-equilibrium, while the not independent draw defines a correlated equilibrium. The expected payoff of each player is bigger in the second case, showing how coordination via a mechanism (or mediator) can be beneficial.


I imagine one could construct similar examples for games of imperfect information, where each player could influence the number of cards in the deck. However I do not know of an elegant example for this case.

$\endgroup$
2
  • $\begingroup$ @Michael Greinecker, If you check this paper in page 49, it shows an example close to the chicken game, however I can not tell If I am able to solve this and present this. If you have some time to check it would be helpful. Thank you in advance! gossner.me/wp-content/uploads/2017/01/… $\endgroup$
    – Nav89
    Aug 17 at 11:55
  • $\begingroup$ Please post new questions as questions, not comments. $\endgroup$
    – Giskard
    Aug 17 at 12:59

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.