Access provided by Autonomous University of Puebla. Download reference work entry PDF
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 i) or an “aggressive” action (denoted as a i):
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
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:
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:
or, equivalently,
The equilibrium conditions can also be formulated ex ante:
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 i 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 i) 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 i for every player i, and by writing (2) in terms of q i 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
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 1” or “t 1” and, at the same time, player 2 tells player 1 “h 2” or “t 2”. 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 i, a probability distribution p i over\( { T = \prod_{j\in N}T^{j} } \), a set of actions A i 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 i; 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 i 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 i, 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 i, then selects an N‑tuple of actions a according to \( { \boldsymbol{q}(.|t) } \) and privately recommends a i 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
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
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 1 if s 1, b 1 if t 1; player 2 chooses a 2 if s 1, b 2 if t 1 . 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 i 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]).
Abbreviations
- Bayesian game:
-
An interactive decision problem consisting of a set of n players, a set of types for every player, a probability distribution which accounts for the players' beliefs over each others' types, a set of actions for every player and a von Neumann–Morgenstern utility function defined over n‑tuples of types and actions for every player.
- Nash equilibrium :
-
In an n‑person strategic form game, a strategy n‑tuple from which unilateral deviations are not profitable.
- von Neumann–Morgenstern utility function:
-
A utility function which reflects the individual's preferences over lotteries. Such a utility function is defined over outcomes and can be extended to any lottery λ by taking expectation with respect to λ.
- Pure strategy (or simply strategy):
-
A mapping which, in an interactive decision problem, associates an action with the information of a player whenever this player can make a choice.
- Sequential equilibrium :
-
A refinement of the Nash equilibrium for n‑person multistage interactive decision problems, which can be loosely defined as a strategy n‑tuple together with beliefs over past information for every player, such that every player maximizes his expected utility given his beliefs and the others' strategies, with the additional condition that the beliefs satisfy (possibly sophisticated) Bayes updating given the strategies.
- Strategic (or normal) form game:
-
An interactive decision problem consisting of a set of n players, a set of strategies for every player and a (typically, von Neumann–Morgenstern) utility function defined over n‑tuples of strategies for every player.
- Utility function:
-
A real valued mapping over a set of outcomes which reflects the preferences of an individual by associating a utility level (a “payoff”) with every outcome.
Bibliography
Primary Literature
Aumann RJ (1974) Subjectivity and correlation in randomized strategies. J Math Econ 1:67–96
Aumann RJ (1987) Correlated equilibrium as an expression of Bayesian rationality. Econometrica 55:1–18
Aumann RJ, Maschler M, Stearns R (1968) Repeated games with incomplete information: an approach to the nonzero sum case. Reports to the US Arms Control and Disarmament Agency, ST-143, Chapter IV, 117–216 (reprinted In: Aumann RJ, Maschler M (1995) Repeated Games of Incomplete Information. M.I.T. Press, Cambridge)
Bárány I (1992) Fair distribution protocols or how players replace fortune. Math Oper Res 17:327–340
Ben-Porath E (1998) Correlation without mediation: expanding the set of equilibrium outcomes by cheap pre-play procedures. J Econ Theor 80:108–122
Ben-Porath E (2003) Cheap talk in games with incomplete information. J Econ Theor 108:45–71
Ben-Porath E (2006) A correction to “Cheap talk in games with incomplete information”. Mimeo, Hebrew University of Jerusalem, Jerusalem
Blackwell D (1951) Comparison of experiments. Proceedings of the Second Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, Berkeley and Los Angeles, pp 93–102
Blackwell D (1953) Equivalent comparison of experiments. Ann Math Stat 24:265–272
Brandenburger A, Dekel E (1987) Rationalizability and correlated equilibria. Econometrica 55:1391–1402
Dhillon A, Mertens JF (1996) Perfect correlated equilibria. J Econ Theor 68:279–302
Dodis Y, Halevi S, Rabin T (2000) A cryptographic solution to a game theoretic problem. CRYPTO 2000: 20th International Cryptology Conference. Springer, Berlin, pp 112–130
Evangelista F, Raghavan TES (1996) A note on correlated equilibrium. Int J Game Theory 25:35–41
Forges F (1985) Correlated equilibria in a class of repeated games with incomplete information. Int J Game Theory 14:129–150
Forges F (1986) An approach to communication equilibrium. Econometrica 54:1375–1385
Forges F (1988) Communication equilibria in repeated games with incomplete information. Math Oper Res 13:191–231
Forges F (1990) Universal mechanisms. Econometrica 58:1341–1364
Forges F (1993) Five legitimate definitions of correlated equilibrium in games with incomplete information. Theor Decis 35:277–310
Forges F (2006) Correlated equilibrium in games with incomplete information revisited. Theor Decis 61:329–344
Foster D, Vohra R (1997) Calibrated learning and correlated equilibrium. Game Econ Behav 21:40–55
Gerardi D (2000) Interim pre-play communication. Mimeo, Yale University, New Haven
Gerardi D (2004) Unmediated communication in games with complete and incomplete information. J Econ Theory 114:104–131
Gerardi D, Myerson R (2007) Sequential equilibria in Bayesian games with communication. Game Econ Behav 60:104–134
Gilboa I, Zemel E (1989) Nash and correlated equilibria: some complexity considerations. Game Econ Behav 1:80–93
Gomez-Canovas S, Hansen P, Jaumard B (1999) Nash Equilibria from the correlated equilibria viewpoint. Int Game Theor Rev 1:33–44
Gossner O (1998) Secure protocols or how communication generates correlation. J Econ Theory 83:69–89
Gossner O (2000) Comparison of information structures. Game Econ Behav 30:44–63
Gossner O, Tomala T (2007) Secret correlation in repeated games with signals. Math Oper Res 32:413–424
Halpern JY (2007) Computer science and game theory. In: Durlauf SN, Blume LE (eds) The New Palgrave dictionary of economics, 2nd edn. Palgrave Macmillan. The New Palgrave dictionary of economics online. http://www.dictionaryofeconomics.com/article?id=pde2008_C000566. Accessed 24 May 2008
Hart S, Schmeidler D (1989) Existence of correlated equilibria. Math Oper Res 14:18–25
Hart S, Mas-Colell A (2000) A simple adaptive procedure leading to correlated equilibrium. Econometrica 68:1127–1150
Hart S (2005) Adaptative heuristics. Econometrica 73:1401–1430
Krishna RV (2007) Communication in games of incomplete information: two players. J Econ Theory 132:584–592
Lehrer E (1991) Internal correlation in repeated games. Int J Game Theory 19:431–456
Lehrer E (1992) Correlated equilibria in two-player repeated games with non-observable actions. Math Oper Res 17:175–199
Lehrer E (1996) Mediated talk. Int J Game Theory 25:177–188
Lehrer E, Sorin S (1997) One-shot public mediated talk. Game Econ Behav 20:131–148
Lehrer E, Rosenberg D, Shmaya E (2006) Signaling and mediation in Bayesian games. Mimeo, Tel Aviv University, Tel Aviv
Milgrom P, Roberts J (1996) Coalition-proofness and correlation with arbitrary communication possibilities. Game Econ Behav 17:113–128
Moreno D, Wooders J (1996) Coalition-proof equilibrium. Games Econ Behav 17:80–112
Myerson R (1982) Optimal coordination mechanisms in generalized principal-agent problems. J Math Econ 10:67–81
Myerson R (1986a) Multistage games with communication. Econometrica 54:323–358
Myerson R (1986b) Acceptable and predominant correlated equilibria. Int J Game Theory 15:133–154
Myerson R (1997) Dual reduction and elementary games. Game Econ Behav 21:183–202
Nash J (1951) Non-cooperative games. Ann Math 54:286–295
Nau RF (1992) Joint coherence in games with incomplete information. Manage Sci 38:374–387
Nau RF, McCardle KF (1990) Coherent behavior in noncooperative games. J Econ Theory 50(2):424–444
Nau RF, McCardle KF (1991) Arbitrage, rationality and equilibrium. Theor Decis 31:199–240
Nau RF, Gomez-Canovas S, Hansen P (2004) On the geometry of Nash equilibria and correlated equilibria. Int J Game Theory 32:443–453
Papadimitriou CH (2005) Computing correlated equilibria in multiplayer games. Proceedings of the 37th ACM Symposium on Theory of Computing. STOC, Baltimore, pp 49–56
Ray I (1996) Coalition-proof correlated equilibrium: a definition. Game Econ Behav 17:56–79
Renault J, Tomala T (2004) Communication equilibrium payoffs in repeated games with imperfect monitoring. Game Econ Behav 49:313–344
Solan E (2001) Characterization of correlated equilibrium in stochastic games. Int J Game Theory 30:259–277
Solan E, Vieille N (2002) Correlated equilibrium in stochastic games. Game Econ Behav 38:362–399
Urbano A, Vila J (2002) Computational complexity and communication: coordination in two-player games. Econometrica 70:1893–1927
Urbano A, Vila J (2004a) Computationally restricted unmediated talk under incomplete information. J Econ Theory 23:283–320
Urbano A, Vila J (2004b) Unmediated communication in repeated games with imperfect monitoring. Game Econ Behav 46:143–173
Vida P (2007) From communication equilibria to correlated equilibria. Mimeo, University of Vienna, Vienna
Viossat Y (2005) Is having a unique equilibrium robust? to appear in J Math Econ
Viossat Y (2006) The geometry of Nash equilibria and correlated equilibria and a generalization of zero-sum games. Mimeo, S-WoPEc working paper 641, Stockholm School of Economics, Stockholm
Viossat Y (2007) The replicator dynamics does not lead to correlated equilibria. Game Econ Behav 59:397–407
Books and Reviews
Forges F (1994) Non-zero sum repeated games and information transmission. In: Megiddo N (ed) Essays in Game Theory in Honor of Michael Maschler. Springer, Berlin, pp 65–95
Mertens JF (1994) Correlated- and communication equilibria. In: Mertens JF, Sorin S (eds) Game Theoretic Methods in General Equilibrium Analysis. Kluwer, Dordrecht, pp 243–248
Myerson R (1985) Bayesian equilibrium and incentive compatibility. In: Hurwicz L, Schmeidler D, Sonnenschein H (eds) Social Goals and Social Organization. Cambridge University Press, Cambridge, pp 229–259
Myerson R (1994) Communication, correlated equilibria and incentive compatibility. In: Aumann R, Hart S (eds) Handbook of Game Theory, vol 2. Elsevier, Amsterdam, pp 827–847
Sorin S (1997) Communication, correlation and cooperation. In: Mas Colell A, Hart S (eds) Cooperation: Game Theoretic Approaches. Springer, Berlin, pp 198–218
Acknowledgment
The author wishes to thank Elchanan Ben-Porath, Frédéric Koessler, R. Vijay Krishna, EhudLehrer, Bob Nau, Indra Ray, Jérôme Renault, Eilon Solan, Sylvain Sorin, Bernhard von Stengel, Tristan Tomala, Amparo Urbano, Yannick Viossat and,especially, Olivier Gossner and Péter Vida, for useful comments and suggestions.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag
About this entry
Cite this entry
Forges, F. (2009). Correlated Equilibria and Communication in Games. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY. https://doi.org/10.1007/978-0-387-30440-3_103
Download citation
DOI: https://doi.org/10.1007/978-0-387-30440-3_103
Publisher Name: Springer, New York, NY
Print ISBN: 978-0-387-75888-6
Online ISBN: 978-0-387-30440-3
eBook Packages: Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics