Correlated Equilibria and Communication in Games

Definition of the Subject

The correlated equilibrium is a game theoretic solution concept. It was proposedby Aumann [1,2] in order to capture the strategic correlationopportunities that the players face when they take into account the extraneous environment inwhich they interact. The notion is illustrated in Sect. “Introduction”. A formal definition is given inSect. “ Correlated Equilibrium: Definition and BasicProperties”. The correlated equilibrium also appears as the appropriate solution concept if preplaycommunication is allowed between theplayers. As shown in Sect. “ Correlated Equilibriumand Communication”, this property can be given several precise statementsaccording to the constraints imposed on the players' communication, which can go from plainconversation to exchange of messages through noisy channels. Originally designed for staticgames with complete information, the correlated equilibrium applies to any strategic formgame. It is geometrically and computationally more tractable than the better known Nashequilibrium. The solution concept has been extended to dynamic games, possibly withincomplete information . As anillustration, we define in details the communicationequilibrium for Bayesian games inSect. “ Correlated Equilibrium in BayesianGames”.

Introduction

Example

Consider the two-person game known as “chicken”, in which each player i can take a “pacific” action (denoted as p ⁱ) or an “aggressive” action (denoted as a ⁱ):

$$ \begin{array}{ccc} & p^{2} & a^{2} \\ p^{1} & (8,8) & (3,10) \\ a^{1} & (10,3) & (0,0) \end{array} $$

The interpretation is that player 1 and player 2 simultaneously choose an action and then get a payoff, which is determined by the pair of chosen actions according to the previous matrix. If both players are pacific, they both get 8. If both are aggressive, they both get 0. If one player is aggressive and the other is pacific, the aggressive player gets 10 and the pacific one gets 3. This game has two pure Nash equilibria ${ (p^{1},a^{2}) }$, ${ (a^{1},p^{2}) }$ and one mixed Nash equilibrium in which both players choose the pacific action with probability ${ 3/5 }$, resulting in the expected payoff 6 for both players. A possible justification for the latter solution is that the players make their choices as a function of independent extraneous random signals. The assumption of independence is strong. Indeed, there may be no way to prevent the players' signals from being correlated.

Consider a random signal which has no effect on the players' payoffs and takes three possible values: low, medium or high, occurring each with probability ${ 1/3 }$. Assume that, before the beginning of the game, player 1 distinguishes whether the signal is high or not, while player 2 distinguishes whether the signal is low or not. The relevant interactive decision problem is then the extended game in which the players can base their action on the private information they get on the random signal, while the payoffs only depend on the players' actions. In this game, suppose that player 1 chooses the aggressive action when the signal is high and the pacific action otherwise. Similarly, suppose that player 2 chooses the aggressive action when the signal is low and the pacific action otherwise. We show that these strategies form an equilibrium in the extended game. Given player 2's strategy, assume that player 1 observes a high signal. Player 1 deduces that the signal cannot be low so that player 2 chooses the pacific action; hence player 1's best response is to play aggressively. Assume now that player 1 is informed that the signal is not high; he deduces that with probability ${ 1/2 }$, the signal is medium (i. e., not low) so that player 2 plays pacific and with probability ${ 1/2 }$, the signal is low so that player 2 plays aggressive. The expected payoff of player 1 is 5.5 if he plays pacific and 5 if he plays aggressive; hence, the pacific action is a best response. The equilibrium conditions for player 2 are symmetric. To sum up, the strategies based on the players' private information form a Nash equilibrium in the extended game in which an extraneous signal is first selected. We shall say that these strategies form a “correlated equilibrium”. The corresponding probability distribution over the players' actions is

$$ \begin{array}{ccc} & p^{2} & a^{2} \\[1mm] p^{1} & \frac{1}{3} & \frac{1}{3} \\[2mm] a^{1} & \frac{1}{3} & 0 \end{array} $$

(1)

and the expected payoff of every player is 7. This probability distribution can be used directly to make private recommendations to the players before the beginning of the game (see the canonical representation below).

Correlated Equilibrium: Definition and Basic Properties

Definition

A game in strategic form ${ G=(N,(\Sigma ^{i})_{i\in N},(u^{i})_{i\in N}) }$ consists of a set of players N together with, for every player ${ i\in N }$, a set of strategies (for instance, a set of actions) ${ \Sigma ^{i} }$ and a (von Neumann–Morgenstern) utility function ${ u^{i}\colon \Sigma \rightarrow \mathbb{R} }$, where ${ \Sigma =\prod_{j\in N}\Sigma ^{j} }$ is the set of all strategy profiles. We assume that the sets N and ${ \Sigma ^{i} }$, ${ i\in N }$, are finite.

A correlation device ${ d=(\Omega , \boldsymbol{q},(\mathcal{P}^{i})_{i\in N}) }$ is described by a finite set of signals Ω, a probability distribution q over ${ \Omega }$ and a partition ${ \mathcal{P}^{i} }$ of Ω for every player ${ i\in N }$. Since Ω is finite, the probability distribution q is just a real vector ${ \boldsymbol{q}=(\boldsymbol{q}(\omega))_{\omega \in \Omega} }$ such that ${ \boldsymbol{q}(\omega)\geq 0 }$ and ${ \sum_{\omega \in \Omega} \boldsymbol{q} (\omega)=1 }$.

From G and d, we define the extended game G _d as follows:

• ω is chosen in Ω according to q

• every player i is informed of the element ${ P^{i}(\omega ) }$ of ${ \mathcal{P}^{i} }$ which contains ω

• G is played: every player i chooses a strategy ${ \sigma ^{i} }$ in ${ \Sigma ^{i} }$ and gets the utility ${ u^{i}(\sigma ) }$, ${ \sigma =(\sigma ^{j})_{j\in N} }$.

A (pure) strategy for player i in G _d is a mapping ${ \alpha ^{i}\colon \Omega \rightarrow \Sigma ^{i} }$ which is ${ \mathcal{P}^{i} }$-measurable, namely, such that ${ \alpha ^{i}(\omega ^{\prime})=\alpha ^{i}(\omega ) }$ if ${ \omega ^{\prime} \in P^{i}(\omega ) }$. The interpretation is that, in G _d , every player i chooses his strategy ${ \sigma ^{i} }$ as a function of his private information on the random signal ω which is selected before the beginning of G.

According to Aumann [1], a correlated equilibrium of G is a pair ${ (d,\alpha ) }$, which consists of a correlation device ${ d=(\Omega ,\boldsymbol{q},(\mathcal{P}^{i})_{i\in N}) }$ and a Nash equilibrium ${ \alpha =(\alpha ^{i})_{i\in N} }$ of G _d . The equilibrium conditions of every player i, conditionally on his private information, can be written as:

$$ \sum\limits_{\omega ^{\prime} \in P^{i}(\omega)}q(\omega ^{\prime} |P^{i}(\omega))u^{i}(\alpha (\omega ^{\prime}))\\ \geq \sum\limits_{\omega ^{\prime} \in P^{i}(\omega)}q(\omega ^{\prime} |P^{i}(\omega))u^{i}(\tau ^{i},\alpha ^{-i}(\omega ^{\prime}))\:,\\ \forall i\in N,\,\forall \tau ^{i}\in \Sigma ^{i},\,\forall \omega \in \Omega \colon q(\omega) > 0\:, $$

(2)

where ${ \alpha ^{-i}=(\alpha ^{j})_{j\neq i} }$.

A mixed Nash equilibrium ${ \rho =(\rho ^{i})_{i\in N} }$ of G can be viewed as a correlated equilibrium of G. By definition, every ${ \rho ^{i} }$ is a probability distribution over ${ \Sigma ^{i} }$, the finite set of pure strategies of player i. Let us consider the correlation device ${ d=(\Omega ,\boldsymbol{q},(\mathcal{P}^{i})_{i\in N}) }$ in which ${ \Omega =\Sigma =\prod_{j\in N}\Sigma ^{j} }$, q is the product probability distribution induced by the mixed strategies (i. e., ${ \boldsymbol{q}((\sigma ^{j})_{j\in N})=\prod_{j\in N}\rho ^{j}(\sigma ^{j}) }$) and for each i, ${ \mathcal{P}^{i} }$ is the partition of Ω generated by ${ \Sigma ^{i} }$ (i. e., for ${ \omega ,\nu \in \Omega }$, ${ \nu \in P^{i}(\omega)\Leftrightarrow \nu ^{i}=\omega ^{i} }$). Let ${ \alpha ^{i}\colon \Sigma \rightarrow \Sigma ^{i} }$ be the projection over ${ \Sigma ^{i} }$ (i. e., ${ \alpha ^{i}(\sigma)=\sigma ^{i} }$). The correlation device d and the strategies ${ \alpha ^{i} }$ defined in this way form a correlated equilibrium. As we shall see below, this correlated equilibrium is “canonical” .

Canonical Representation

A canonical correlated equilibrium of G is a correlated equilibrium in which ${ \Omega =\Sigma =\prod_{j\in N}\Sigma ^{j} }$ while for every player i, the partition ${ \mathcal{P}^{i} }$ of Σ is generated by ${ \Sigma ^{i} }$ and ${ \alpha ^{i}\colon \Sigma \rightarrow \Sigma ^{i} }$ is the projection over ${ \Sigma ^{i} }$. A canonical correlated equilibrium is thus fully specified by a probability distribution q over Σ. A natural interpretation is that a mediator selects ${ \sigma =(\sigma ^{j})_{j\in N} }$ according to q and privately recommends ${ \sigma ^{i} }$ to player i, for every ${ i\in N }$. The players are not forced to obey the mediator, but σ is selected in such a way that player i cannot benefit from deviating unilaterally from the recommendation ${ \sigma ^{i} }$, i. e., ${ \tau ^{i}=\sigma ^{i} }$ maximizes the conditional expectation of player i's payoff ${ u^{i}(\tau ^{i},\sigma ^{-i} }$) given the recommendation ${ \sigma ^{i} }$. A probability distribution q over Σ thus defines a canonical correlated equilibrium if and only if it satisfies the following linear inequalities:

$$ \sum\limits_{\sigma ^{-i}\in \Sigma ^{-i}}\boldsymbol{q}(\sigma ^{-i}|\sigma ^{i})u^{i}(\sigma ^{i},\sigma ^{-i}) \\ \geq \sum\limits_{\sigma ^{-i}\in \Sigma ^{-i}}\boldsymbol{q}(\sigma ^{-i}|\sigma ^{i})u^{i}(\tau ^{i},\sigma ^{-i})\:,\\ \forall i\in N,\,\forall \sigma ^{i}\in \Sigma ^{i}\colon \boldsymbol{q}(\sigma ^{i}) > 0,\,\forall \tau ^{i}\in \Sigma ^{i} $$

or, equivalently,

$$ \sum\limits_{\sigma ^{-i}\in \Sigma ^{-i}}\boldsymbol{q}(\sigma ^{i},\sigma ^{-i})u^{i}(\sigma ^{i},\sigma ^{-i}) \\ \geq \sum\limits_{\sigma ^{-i}\in \Sigma ^{-i}}\boldsymbol{q}(\sigma ^{i},\sigma ^{-i})u^{i}(\tau ^{i},\sigma ^{-i})\:,\\ \forall i\in N,\,\forall \sigma ^{i},\,\tau ^{i}\in \Sigma ^{i} $$

(3)

The equilibrium conditions can also be formulated ex ante:

$$ \sum\limits_{\sigma \in \Sigma} \boldsymbol{q}(\sigma)u^{i}(\sigma)\geq \sum\limits_{\sigma \in \Sigma} \boldsymbol{q}(\sigma)u^{i}(\alpha ^{i}(\sigma ^{i}),\sigma ^{-i})\:, \\ \forall i\in N,\, \forall \alpha ^{i}\colon \Sigma ^{i}\rightarrow \Sigma ^{i} $$

The following result is an analog of the “revelation principle” in mechanism design (see, e. g., Myerson [41]): let ${ (\alpha ,d }$) be a correlated equilibrium associated with an arbitrary correlation device ${ d=(\Omega ,\boldsymbol{q},(\mathcal{P}^{i})_{i\in N} }$). The corresponding “correlated equilibrium distribution”, namely, the probability distribution induced over Σ by q and α, defines a canonical correlated equilibrium. For instance, in the introduction, (1) describes a canonical correlated equilibrium.

Duality and Existence

From the linearity of (3), duality theory can be used to study the properties of correlated equilibria, in particular to prove their existence without relying on Nash's [45] theorem and its fixed point argument (recall that every mixed Nash equilibrium is a correlated equilibrium). Hart and Schmeidler [30] establish the existence of a correlated equilibrium by constructing an auxiliary two person zero-sum game and applying the minimax theorem. Nau and McCardle [47] derive another elementary proof of existence from an extension of the “no arbitrage opportunities” axiom that underlies subjective probability theory. They introduce jointly coherent strategy profiles, which do not expose the players as a group to arbitrage from an outside observer. They show that a strategy profile is jointly coherent if and only if it occurs with positive probability in some correlated equilibrium. From a technical point of view, both proofs turn out to be similar. Myerson [44] makes further use of the linear structure of correlated equilibria by introducing dual reduction, a technique to replace a finite game with a game with fewer strategies, in such a way that any correlated equilibrium of the reduced game induces a correlated equilibrium of the original game.

Geometric Properties

As (3) is a system of linear inequalities, the set of all correlated equilibrium distributions is a convex polytope. Nau et al. [49] show that if it has “full” dimension (namely, dimension ${ |\Sigma |-1 }$), then all Nash equilibria lie on its relative boundary. Viossat [60] characterizes in addition the class of games whose correlated equilibrium polytope contains a Nash equilibrium in its relative interior. Interestingly, this class of games includes two person zero-sum games but is not defined by “strict competition” properties. In two person games, all extreme Nash equilibria are also extreme correlated equilibria [13,25]; this result does not hold with more than two players. Finally, Viossat [59] proves that having a unique correlated equilibrium is a robust property, in the sense that the set of n person games with a unique correlated equilibrium is open. The same is not true for Nash equilibrium (unless ${ n=2 }$).

Complexity

From (3), correlated equilibria can be computed by linear programming methods. Gilboa and Zemel [24] show more precisely that the complexity of standard computational problems is “NP-hard” for the Nash equilibrium and polynomial for the correlated equilibrium. Examples of such problems are: “Does the game G have a Nash (resp., correlated) equilibrium which yields a payoff greater than r to every player (for some given number r)?” and “Does the game G have a unique Nash (resp., correlated) equilibrium?”. Papadimitriou [50] develops a polynomial-time algorithm for finding correlated equilibria, which is based on a variant of the existence proof of Hart and Schmeidler [30].

Foundations

By re-interpreting the previous canonical representation, Aumann [2] proposes a decision theoretic foundation for the correlated equilibrium in games with complete information, in which ${ \Sigma ^{i} }$ for ${ i\in N }$, stands merely for a set of actions of player i. Let Ω be the space of all states of the world; an element ω of Ω thus specifies all the parameters which may be relevant to the players' choices. In particular, the action profile in the underlying game G is part of the state of the world. A partition ${ \mathcal{P}^{i} }$ describes player i's information on Ω. In addition, every player i has a prior belief, i. e., a probability distribution, q ⁱ over Ω. Formally, the framework is similar as above except that the players possibly hold different beliefs over Ω. Let ${ \alpha^{i}(\omega) }$ denote player i's action at ω; a natural assumption is that player i knows the action he chooses, namely that ${ \alpha ^{i} }$ is ${ \mathcal{P}^{i} }$ -measurable. According to Aumann [2], player i is Bayes-rational at ω if his action ${ \alpha ^{i}(\omega }$) maximizes his expected payoff (with respect to q ⁱ) given his information ${ P^{i}(\omega }$). Note that this is a separate rationality condition for every player, not an equilibrium condition. Aumann [2] proves the following result: Under the common prior assumption (namely, ${ \boldsymbol{q}^{i}=\boldsymbol{q} }$, ${ i\in N }$ ), if every player is Bayes-rational at every state of the world, the distribution of the corresponding action profile ${ \alpha }$ is a correlated equilibrium distribution. The key to this decision theoretic foundation of the correlated equilibrium is that, under the common prior assumption, Bayesian rationality amounts to (2).

If the common prior assumption is relaxed, the previous result still holds, with subjective prior probability distributions, for the subjective correlated equilibrium which was also introduced by Aumann [1]. The latter solution concept is defined in the same way as above, by considering a device ${ (\Omega ,(\boldsymbol{q}^{i})_{i\in N},(\mathcal{P}^{i})_{i\in N} }$), with a probability distribution q ⁱ for every player i, and by writing (2) in terms of q ⁱ instead of q. Brandenburger and Dekel [10] show that (a refinement of) the subjective correlated equilibrium is equivalent to (correlated) rationalizability, another well-established solution concept which captures players' minimal rationality. Rationalizable strategies reflect that the players commonly know that each of them makes an optimal choice given some belief. Nau and McCardle [48] reconcile objective and subjective correlated equilibrium by proposing the no arbitrage principle as a unified approach to individual and interactive decision problems. They argue that the objective correlated equilibrium concept applies to a game that is revealed by the players' choices, while the subjective correlated equilibrium concept applies to the “true game”; both lead to the same set of jointly coherent outcomes.

Correlated Equilibrium and Communication

As seen in the previous section, correlated equilibria can be achieved in practice with the help of a mediator and emerge in a Bayesianframework embedding the game in a full description of the world. Both approaches require to extend the game by taking into account information whichis not generated by the players themselves. Can the players reach a correlated equilibrium without relying on any extraneous correlation device, byjust communicating with each other before the beginning of the game?

Consider the game of “chicken” presented in the introduction. The probability distribution

$$ \begin{array}{ccc} & p^{2} & a^{2} \\[1mm] p^{1} & 0 & \frac{1}{2} \\[2mm] a^{1} & \frac{1}{2} & 0 \end{array} $$

(4)

describes a correlated equilibrium, which amounts to choosing one of the two pure Nash equilibria, with equal probability. Both players get an expected payoff of 6.5. Can they safely achieve this probability distribution if no mediator tosses a fair coin for them? The answer is positive, as shown by Aumann et al. [3]. Assume that before playing “chicken”, the players independently toss a coin and simultaneously reveal to each other whether heads or tails obtains. Player 1 tells player 2 “h ¹” or “t ¹” and, at the same time, player 2 tells player 1 “h ²” or “t ²”. If both players use a fair coin, reveal correctly the result of the toss and play ${ (p^{1},a^{2} }$) if both coins fell on the same side (i. e., if ${ (h^{1},h^{2} }$) or ${ (t^{1},t^{2} }$) is announced) and ${ (a^{1},p^{2} }$) otherwise (i. e., if ${ (h^{1},t^{2}) }$ or ${ (t^{1},h^{2}) }$ is announced), they get the same effect as a mediator using (4). Furthermore, none of them can gain by unilaterally deviating from the described strategies, even at the randomizing stage: the two relevant outcomes, ${ [(h^{1},h^{2}) }$ or ${ (t^{1},t^{2})] }$ and ${ [(h^{1},t^{2}) }$ or ${ (t^{1},h^{2})] }$, happen with probability ${ 1/2 }$ provided that one of the players reveals the toss of a fair coin. This procedure is known as a “jointly controlled lottery ” . An important feature of the previous example is that, in the correlated equilibrium described by (4), the players know each other's recommendation. Hence, they can easily reproduce (4) by exchanging messages that they have selected independently. In the correlated equilibrium described by the probability distribution (1), the private character of recommendations is crucial to guarantee that ${ (p^{1},p^{2}) }$ be played with positive probability. Hence one cannot hope that a simple procedure of direct preplay communication be sufficient to generate (1). However, the fact that direct communication is necessarily public is typical of two-person games.

Given the game ${G=(N,(\Sigma ^{i})_{i\in N},(u^{i})_{i\in N}) }$, letus define a (bounded) “cheap talk ” extension ext(G) ofG as a game in which T stages of costless, unmediated preplay communication are allowedbefore G is played. More precisely, let ${ M_{t}^{i} }$ be a finite set of messages forplayer i, ${ i\in N }$, at stage t,${ t=1,2, \dots T }$; at every stage tof ext(G), every player i selects a message in ${ M_{t}^{i} }$; these choices are made simultaneously before beingrevealed to a subset of players at the end of stage t. The rules of ${ ext(G) }$ thus determinea set of “senders” for every stage t(those players i for whom ${ M_{t}^{i} }$ contains more than one message) and a set of“receivers” for every stage t. The playersperfectly recall their past messages. After the communication phase, they choose theirstrategies (e. g., their actions) as in G; they arealso rewarded as in G, independently of the preplay phase,which is thus “cheap” . Communication has an indirect effect on the final outcomein G, since the players make their decisions asa function of the messages that they have exchanged. Specific additional assumptions areoften made on ext(G), as we will see below.

Let us fix a cheap talk extension ext(G) of G and a Nash equilibriumof ${ ext(G) }$. As a consequence ofthe previous definitions, the distribution induced by this Nash equilibrium over Σ defines a correlated equilibrium of G (this can be proved in the same way as the canonical representation of correlated equilibria stated inSect. “Correlated Equilibrium: Definition and Basic Properties”). The question raised in thissection is whether the reverse holds.

If the number of players is two, the Nash equilibrium distributions of cheap talk extensions of G forma subset of the correlated equilibrium distributions: the convex hull of Nash equilibrium distributions. Indeed, the players have both the sameinformation after any direct exchange of messages. Conversely, by performing repeated jointly controlled lotteries like in the example above, the playerscan achieve any convex combination (with rational weights) of Nash equilibria of G as a Nash equilibrium ofa cheap talk extension of G. The restriction on probability distributions whose components are rational numbers isonly needed as far as we focus on bounded cheap talk extensions.

Bárány [4] establishes that, if the number of players of G is at least four, every (rational) correlated equilibrium distribution of G can be realizedas a Nash equilibrium of a cheap talk extension ext(G), provided that ext(G) allows the players to publicly check the record of communication under some circumstances. The equilibria of ext(G) constructed by Bárány involve that a receiver gets the same message from two different senders; the message isnevertheless not public thanks to the assumption on the number of players. At every stage of ext(G), every player canask for the revelation of all past messages, which are assumed to be recorded. Typically, a receiver can claim that the two senders' messagesdiffer. In this case, the record of communication surely reveals that either one of the senders or the receiver himself has cheated; the deviator can bepunished (at his minmax level in G) by the other players.

The punishments in Bárány's [4] Nash equilibria of ext(G)need not be credible threats. Instead of using double senders in the communication protocols, Ben-Porath [5,6] proposes a procedure of random monitoring, which prescribesa given behavior to every player in such a way that unilateral deviations can be detected with probability arbitrarily close to 1. Thisprocedure applies if there are at least three players, which yields an analog of Bárány's result already in this case. If the number of players is exactlythree, Ben-Porath [6] needs to assumes, as Bárány [4], that public verification of the record of communication is possible in ext(G)(see Ben-Porath [7]). However, Ben-Porath concentrates on (rational) correlated equilibriumdistributions which allow for strict punishment on a Nash equilibrium of G; he constructs sequential equilibria which generate these distributions in ext(G), thus dispensing withincredible threats. At the price of raising the number of players to five or more, Gerardi [22]proves that every (rational) correlated equilibrium distribution of G can be realized as a sequential equilibriumof a cheap talk extension of G which does not require any message recording. For this, he builds protocols ofcommunication in which the players base their decisions on majority rule, so that no punishment is necessary.

We have concentrated on two extreme forms of communication: mediatedcommunication , in which a mediatorperforms lotteries and sends private messages to the players and cheap talk, in which theplayers just exchange messages. Many intermediate schemes of communication are obviouslyconceivable. For instance, Lehrer [36]introduces (possibly multistage) “mediated talk”: the players send privatemessages to a mediator, but the latter can only make deterministic publicannouncements. Mediated talk captures real-life communication procedures, like elections,especially if it lasts only for a few stages. Lehrer and Sorin [37] establish that whatever the number of players ofG, every (rational) correlated equilibrium distribution ofG can be realized as a Nash equilibrium ofa single stage mediated talk extension of G.Ben-Porath [5] proposes a variant ofcheap talk in which the players do not only exchange verbal messages but also“hard” devices such as urns containing balls. This extension is particularlyuseful in two-person games to circumvent the equivalence between the equilibria achieved bycheap talk and the convex hull of Nash equilibria. More precisely, the result ofBen-Porath [5] stated above holds fortwo-person games if the players first check together the content of different urns, and theneach player draws a ball from an urn that was chosen by the other player, so as toguarantee that one player only knows the outcome of a lottery while the other one onlyknows the probabilities of this lottery.

The various extensions of the basic game G considered up to now, with or without a mediator, implicitlyassume that the players are fully rational. In particular, they have unlimited computational abilities. By relaxing that assumption, Urbano andVila [55] and Dodis et al. [12] build onearlier results from cryptography so as to implement any (rational) correlated equilibrium distribution through unmediated communication, including intwo-person games.

As the previous paragraphs illustrate, the players can modify their intitial distribution of information by means of many different communicationprotocols. Gossner [26] proposes a general criterion to classify them: a protocol is“secure” if under all circumstances, the players cannot mislead each other nor spy on each other. For instance, given a cheap talkextension ext(G), a protocol P describes, for every player, a strategy inext(G) and a way to interpret his information after the communication phase of ext(G). P induces a correlation device d(P) (in the sense of Sect. “ Correlated Equilibrium: Definition and BasicProperties”). P is secure if, for every game G and every Nash equilibrium α of ${ G_{d(P)} }$, the following procedure is a Nash equilibrium of ext(G): communicateaccording to the strategies described by P in order to generate d(P) and make the final choice, in G, according to α. Gossner [26] gives a tractable characterization of secure protocols.

Correlated Equilibrium in Bayesian Games

A Bayesian game ${ \Gamma =(N,(T^{i})_{i\in N},p,(A^{i})_{i\in N},(v^{i})_{i\in N}) }$ consists of: a set of players N; for every player ${ i\in N }$, a set oftypes T ⁱ, a probability distribution p ⁱ over${ T = \prod_{j\in N}T^{j} }$, a set of actions A ⁱ anda (von Neumann–Morgenstern) utility function ${ v^{i}\colon T\times A\rightarrow\mathbb{R} }$, where ${ A=\prod_{j\in N}A^{j} }$. For simplicity, we make the common priorassumption : ${ p^{i}=p }$ for every ${ i\in N }$. All sets are assumed finite. The interpretation isthat a virtual move of nature chooses ${ t=(t^{j})_{j\in N} }$according to p; player i is only informed of his own type t ⁱ; theplayers then choose simultaneously an action. We will focus on two possible extensions ofAumann's [1] solution concept to Bayesiangames: the strategic form correlated equilibrium and the communication equilibrium. Withoutloss of generality, the definitions below are given in “canonical form” (seeSect. “ Correlated Equilibrium: Definition and BasicProperties”).

Strategic Form Correlated Equilibrium

A (pure) strategy of player i in Γ is a mapping $\sigma ^{i} \colon T^{i}\rightarrow A^{i}$, ${ i\in N }$. The strategic form of Γ is a game ${ G(\Gamma) }$, like the game G considered in Sect. “Correlated Equilibrium: Definition and Basic Properties”, with sets of pure strategies ${ \Sigma _{i}=A_{i}^{T_{i}} }$ and utility functions u ⁱ over $\Sigma = \prod_{j\in N}\Sigma^{j}$ computed as expectations with respect to $p \colon u^{i}(\sigma)=E[v^{i}(t,\sigma (t))]$, with $\sigma (t)=(\sigma ^{i}(t^{i}))_{i\in N}$. A strategic form correlated equilibrium, or simply, a correlated equilibrium, of a Bayesian game Γ is a correlated equilibrium, in the sense of Sect. “Correlated Equilibrium: Definition and Basic Properties”, of ${ G(\Gamma) }$. A canonical correlated equilibrium of Γ is thus described by a probability distribution Q over Σ, which selects an N‑tuple of pure strategies ${ (\sigma ^{i})_{i\in N} }$. This lottery can be thought of as being performed by a mediator who privately recommends ${ \sigma ^{i} }$ to player i, ${ i\in N }$, before the beginning of Γ, i. e., before (or in any case, independently of) the chance move choosing the N -tuple of types. The equilibrium conditions express that, once he knows his type t ⁱ, player i cannot gain in unilaterally deviating from ${ \sigma ^{i}(t^{i}) }$.

Communication Equilibrium

Myerson [41] transforms the Bayesian game Γ into a mechanism design problem by allowing the mediator to collect information from the players before making them recommendations. Following Forges [15] and Myerson [42], a canonical communication device for Γ consists of a system q of probability distributions ${ \boldsymbol{q} = (\boldsymbol{q}(.|t))_{t\in T} }$ over A. The interpretation is that a mediator invites every player i, ${ i\in N }$, to report his type t ⁱ, then selects an N‑tuple of actions a according to ${ \boldsymbol{q}(.|t) }$ and privately recommends a ⁱ to player i. The system q defines a communication equilibrium if none of the players can gain by unilaterally lying on his type or by deviating from the recommended action, namely if

$$ \sum_{t^{-i}\in T^{-i}}p(t^{-i}|t^{i}) \sum_{a\in A}q(a|t)v^{i}(t,a)\\ \geq \sum_{t^{-i}\in T^{-i}}p(t^{-i}|t^{i})\sum_{a\in A}q(a|s^{i},t^{-i})v^{i}(t,\alpha ^{i}(a^{i}),a^{-i})\:,\\ \forall i\in N,\,\forall t^{i},\,s^{i}\in T^{i},\,\forall \alpha ^{i}\colon A^{i}\rightarrow A^{i} $$

Correlated Equilibrium, Communication Equilibrium and Cheap Talk

Every correlated equilibrium of the Bayesian game Γ induces a communication equilibrium of Γ, but the converse is not true, as the following example shows.

Consider the two-person Bayesian game in which ${ T^{1}=\{s^{1},t^{1}\} }$, ${ T^{2}=\{t^{2}\} }$, ${ A^{1}=\{a^{1},b^{1}\} }$, ${ A^{2}=\{a^{2},b^{2}\} }$, ${ p(s^{1})=p(t^{1})=\frac{1}{2} }$ and payoffs are described by

$$ s^{1}\qquad \begin{array}{ccc} & a^{2} & b^{2} \\ a^{1} & (1,1) & (-1,-1) \\ b^{1} & (0,0) & (0,0) \end{array} $$

$$ t^{1}\qquad \begin{array}{ccc} & a^{2} & b^{2} \\ a^{1} & (0,0) & (0,0) \\ b^{1} & (-1,-1) & (1,1) \end{array} $$

In this game, the communication equilibrium $\boldsymbol{q}(a^{1}, a^{2}|s^{1})= \boldsymbol{q}(b^{1},b^{2}|t^{1}) = 1$ yields the expected payoff of 1 to both players. However the maximal expected payoff of every player in a correlated equilibrium is ${ 1/2 }$. In order to see this, one can derive the strategic form of the game (in which player 1 has four strategies and player 2 has two strategies). Let us turn to the game in which player 1 can cheaply talk to player 2 just after having learned his type. In this new game, the following strategies form a Nash equilibrium: player 1 truthfully reveals his type to player 2 and plays a ¹ if s ¹, b ¹ if t ¹; player 2 chooses a ² if s ¹, b ² if t ¹ . These strategies achieve the same expected payoffs as the communication equilibrium.

As in Sect. “Correlated Equilibrium and Communication”, one can define cheap talk extensions ${ \mathrm{ext}(\Gamma) }$ of ${ \Gamma }$. A wide definition of ${ \mathrm{ext}(\Gamma) }$ involves an ex ante preplay phase, before the players learn their types, and an interim preplay phase, after the players learn their types but before they choose their actions. Every Nash equilibrium of ${ \mathrm{ext}(\Gamma) }$ induces a communication equilibrium of Γ. In order to investigate the converse, namely whether cheap talk can simulate mediated communication in a Bayesian game, two approaches have been developed. The first one (Forges [17], Gerardi [21,22], Vida [58]) proceeds in two steps, by reducing communication equilibria to correlated equilibria before applying the results obtained for strategic form games (see Sect. “Correlated Equilibrium and Communication”). The second approach (Ben-Porath [6], Krishna [33]) directly addresses the question in a Bayesian game.

By developing a construction introduced for particular two person games (Forges [14]), Forges [17] shows that every communication equilibrium outcome of a Bayesian game Γ with at least four players can be achieved as a correlated equilibrium outcome of a two stage interim cheap talk extension ${ \mathrm{ext}_\mathrm{int}(\Gamma) }$ of Γ. No punishment is necessary in ${ \mathrm{ext}_\mathrm{int}(\Gamma) }$: at the second stage, every player gets a message from three senders and uses majority rule if the messages are not identical. Thanks to the underlying correlation device, each receiver is able to privately decode his message. Vida [58] extends Forges [17] to Bayesian games with three or even two players. In the proof, he constructs a correlated equilibrium of a long, but almost surely finite, interim cheap talk extension of Γ, whose length depends both on the signals selected by the correlation device and the messages exchanged by the players. No recording of messages is necessary to detect and punish a cheating player. If there are at least four players in Γ, once a communication equilibrium of Γ has been converted into a correlated equilibrium of ${ \mathrm{ext}_\mathrm{int}(\Gamma) }$, one can apply Bárány's [4] result to ${ \mathrm{ext}_\mathrm{int}(\Gamma) }$ in order to transform the correlated equilibrium into a Nash equilibrium of a further, ex ante, cheap talk preplay extension of Γ. Gerardi [21] modifies this ex ante preplay phase so as to postpone it at the interim stage. This result is especially useful if the initial move of nature in Γ is just a modelling convenience. Gerardi [22] also extends his result for at least five person games with complete information (see Sect. “Correlated Equilibrium and Communication”) to any Bayesian game with full support (i. e., in which all type profiles have positive probability: ${ p(t) > 0 }$ for every ${ t\in T }$) by proving that every (rational) communication equilibrium of Γ can be achieved as a sequential equilibrium of a cheap talk extension of Γ.

Ben-Porath [6] establishes that if Γ is a three (or more) person game with full support, every (rational) communication equilibrium of ${ \Gamma }$ which strictly dominates a Nash equilibrium of Γ for every type t ⁱ of every player i, ${ i\in N }$, can be implemented as a Nash equilibrium of an interim cheap talk extension of Γ in which public verification of past record is possible (see also Ben-Porath [7]). Krishna [33] extends Ben-Porath's [5] result on two person games (see Sect. “Correlated Equilibrium and Communication”) to the incomplete information framework. The other results mentioned at the end of Sect. “Correlated Equilibrium and Communication” have also been generalized to Bayesian games (see [26,37,56]).

Related Topics and Future Directions

In this brief article, we concentrated on two solution concepts: the strategic formcorrelated equilibrium, which is applicable to any game, and the communication equilibrium,which we defined for Bayesian games. Other extensions of Aumann's [1]solution concept have been proposed for Bayesian games,as the agent normal form correlated equilibrium and the (possibly beliefinvariant ) Bayesian solution (see Forges [18,19]for definitions and references). The Bayesian solution is intended to capture the players'rationality in games with incomplete information in the spirit ofAumann [2] (see Nau [46] and Forges [18]). Lehrer et al. [38] open a new perspective in the understanding ofthe Bayesian solution and other equilibrium concepts for Bayesian games by characterizing theclasses of equivalent information structures with respect to each of them. Comparison ofinformation structures, which goes back to Blackwell [8,9] forindividual decision problems, was introduced by Gossner [27] in the context of games, both with complete andincomplete information. In the latter model, information structures basically describe howextraneous signals are selected as a function of the players' types; two informationstructures are equivalent with respect to an equilibrium concept if, in every game, theygenerate the same equilibrium distributions over outcomes.

Correlated equilibria, communication equilibria and related solution concepts have beenstudied in many other classes of games, like multistage games (see, e. g.,[15,42]), repeated games with incomplete information (see, e. g.,[14,16]) and stochastic games (see, e. g.,[53,54]). The study of correlatedequilibrium in repeated games with imperfect monitoring , initiated byLehrer [34,35], proved to be particularly useful and is stillundergoing. Lehrer [34] showed that ifplayers are either fully informed of past actions or get no information (“standard-trivial” information structure), correlated equilibria are equivalent to Nashequilibria. In other words, all correlations can be generated internally, namely by the pasthistories, on which players have differential information. The schemes of internal correlationintroduced to establish this result are widely applicable and inspired those ofLehrer [36] (seeSect. “ Correlated Equilibrium andCommunication”). In general repeated games with imperfect monitoring,Renault and Tomala [52] characterizecommunication equilibria but the amount of correlation that the players can achieve ina Nash equilibrium is still an open problem (see, e. g., [28,57] for recent advances).

Throughout this article, we defined a correlated equilibrium as a Nash equilibrium of an extension of the game under consideration. Thesolution concept can be strengthened by imposing some refinement, i. e., furtherrationality conditions, to the Nash equilibrium in this definition (see, e. g., [11,43]). Refinements ofcommunication equilibria have also been proposed (see, e. g., [22,23,42]). Some authors (see, e. g., [39,40,51]) have also developed notions of coalition proof correlated equilibria,which resist not only to unilateral deviations, as in this article, but even to multilateralones. A recurrent difficulty is that, for many of these stronger solution concepts,a useful canonical representation (as derived in Sect. “Correlated Equilibrium: Definition and Basic Properties”)is not available.

Except for two or three references, we deliberately concentrated on the results published in the game theory and mathematical economics literature,while substantial achievements in computer science would fit in this survey. Both streams of research pursue similar goals but rely on differentformalisms and techniques. For instance, computer scientists often make use of cryptographic tools which are not familiar in gametheory. Halpern [29] gives an idea of recent developments at the interface of computer science andgame theory (see in particular the section “implementing mediators”) and contains a number of references.

Finally, the assumption of full rationality of the players can also berelaxed. Evolutionary game theory has developed models of learning in order to study the longterm behavior of players with bounded rationality . Many possible dynamics are conceivable to represent more orless myopic attitudes with respect to optimization. Under appropriate learning procedures,which express for instance that agents want to minimize the regret of their strategic choices,the empirical distribution of actions converge to correlated equilibrium distributions (see,e. g., [20,31,32] for a survey). However,standard procedures, as the “replicator dynamics ”, may even eliminate all the strategies which havepositive probability in a correlated equilibrium (see [61]).