Bayes correlated equilibrium
Bayes correlated equilibrium
In game-theory, a Bayes correlated equilibrium is a solution-concept for static games of incomplete information. It is both a generalization of the correlated-equilibrium perfect-information solution concept to bayesian games, and also a broader solution concept than the usual Bayesian Nash equilibrium thereof. Additionally, it can be seen as a generalized multi-player solution of the bayesian-persuasion information design problem.
Intuitively, a Bayes correlated equilibrium allows for players to correlate their actions in such a way that no player has an incentive to deviate for every possible type they may have. It was first proposed by Dirk Bergemann and Stephen Morris.
Formal definition ### Preliminaries Let <math>I</math> be a set of players, and <math>\Theta</math> a set of possible states of the world. A game is defined as a tuple <math>G = \langle (A_i, u_i)_{i \in I}, \Theta, \psi \rangle</math>, where <math>A_i</math> is the set of possible actions (with <math>A = \prod_{i \in I} A_i</math>) and <math>u_i : A\times \Theta \rightarrow \mathbb{R}</math> is the utility function for each player, and <math> \psi \in \Delta_{++} (\Theta)</math> is a full support common prior over the states of the world.
An information structure is defined as a tuple <math>S = \langle (T_i)_{i \in I}, \pi \rangle</math>, where <math>T_i</math> is a set of possible signals (or types) each player can receive (with <math>T = \prod_{i \in I} T_i</math>), and <math>\pi : \Theta \rightarrow \Delta (T)</math> is a signal distribution function, informing the probability <math>\pi (t | \theta)</math> of observing the joint signal <math>t \in T</math> when the state of the world is <math>\theta \in \Theta</math>.
By joining those two definitions, one can define <math>\Gamma = (G, S)</math> as an incomplete information game. A decision rule for the incomplete information game <math>\Gamma = (G, S)</math> is a mapping <math>\sigma: T \times \Theta \rightarrow \Delta (A)</math>. Intuitively, the value of decision rule <math>\sigma (a | t, \theta)</math> can be thought of as a joint recommendation for players to play the joint mixed strategy <math>\sigma (\cdot \mid t, \theta) \in \Delta(A)</math> when the joint signal received is <math>t \in T</math> and the state of the world is <math>\theta \in \Theta</math>.
Definition A Bayes correlated equilibrium (BCE) is defined to be a decision rule <math>\sigma</math> which is obedient: that is, one where no player has an incentive to unilaterally deviate from the recommended joint strategy, for any possible type they may be. Formally, decision rule <math>\sigma</math> is obedient (and a Bayes correlated equilibrium) for game <math> \Gamma = (G, S)</math> if, for every player <math>i \in I</math>, every signal <math>t_i \in T_i</math> and every action <math>a_i \in A_i</math>, we have
:<math>\sum_{a_{-i}, t_{-i}, \theta} \psi (\theta) \pi (t_i, t_{-i} | \theta) \sigma (a_i, a_{-i} | t_i, t_{-i} ,\theta) u_i(a_i, a_{-i}, \theta) </math>
:<math> \geq \sum_{a_{-i}, t_{-i}, \theta} \psi (\theta) \pi (t_i, t_{-i} | \theta) \sigma (a_i, a_{-i} | t_i, t_{-i} ,\theta) u_i(a'_i, a_{-i}, \theta) </math>
for all <math>a'_i \in A_i</math>.
That is, every player obtains a higher expected payoff by following the recommendation from the decision rule than by deviating to any other possible action.
Relation to other concepts ### Bayesian Nash equilibrium Every Bayesian Nash equilibrium (BNE) of an incomplete information game can be thought of a as BCE, where the recommended joint strategy is simply the equilibrium joint strategy.
Formally, let <math>\Gamma = (G, S)</math> be an incomplete information game, and let <math>s : T \rightarrow \Delta(A)</math> be an equilibrium joint strategy, with each player <math>i </math> playing <math>s_i (a_i | t_i) \in \Delta (A_i) </math>. Therefore, the definition of BNE implies that, for every <math>i \in I</math>, <math>t_i \in T_i</math> and <math>a_i \in A_i</math> such that <math>s_i (a_i | t_i) > 0</math>, we have
:<math>\sum_{a_{-i}, t_{-i}, \theta} \psi (\theta) \pi (t_i, t_{-i} | \theta) \left(\prod_{j \neq i} s_j (a_j | t_j) \right) u_i(a_i, a_{-i}, \theta) </math>
:<math> \geq \sum_{a_{-i}, t_{-i}, \theta} \psi (\theta) \pi (t_i, t_{-i} | \theta) \left(\prod_{j \neq i} s_j (a_j | t_j) \right) u_i(a'_i, a_{-i}, \theta) </math>
for every <math>a'_i \in A_i</math>.
If we define the decision rule <math>\sigma</math> on <math>\Gamma</math> as <math>\sigma (a | t, \theta) = s(a | t) = \prod_{i} s_i (a_i | t_i)</math> for all <math>t \in T</math> and <math>\theta \in \Theta</math>, we directly get a BCE.
Correlated equilibrium If there is no uncertainty about the state of the world (e.g., if <math>\Theta</math> is a singleton), then the definition collapses to Aumann's correlated-equilibrium solution. In this case, <math>\sigma \in \Delta (A)</math> is a BCE if, for every <math>i \in I</math>, we have
:<math>\sum_{a_{-i} \in A{-i}} \sigma (a_i, a_{-i}) u_i(a_i, a_{-i}) \geq \sum_{a_{-i} \in A{-i}} \sigma (a_i, a_{-i}) u_i(a'_i, a_{-i}) </math>
for every <math>a'_i \in A_i</math>, which is equivalent to the definition of a correlated equilibrium for such a setting.
Bayesian persuasion Additionally, the problem of designing a BCE can be thought of as a multi-player generalization of the bayesian-persuasion problem from Emir Kamenica and Matthew Gentzkow. More specifically, let <math>v : A \times \Theta \rightarrow \mathbb R</math> be the information designer's objective function. Then her ex-ante expected utility from a BCE decision rule <math>\sigma</math> is given by:
:<math>V(\sigma) = \sum_{a, t, \theta} \psi (\theta) \pi(t | \theta) \sigma (a | t, \theta) v(a, \theta) </math>
If the set of players <math>I</math> is a singleton, then choosing an information structure to maximize <math>V(\sigma)</math> is equivalent to a Bayesian persuasion problem, where the information designer is called a Sender and the player is called a Receiver.