An Evolutionary Analysis of Pre-Play
Communication and Efficiency in Games
Kenichi Amaya∗
Kobe University
November 17, 2004

Abstract
This paper studies the effects of pre-play communication on equilibrium selection in 2 × 2 symmetric coordination games. The players
repeatedly play a coordination game preceded by an opportunity to
exchange payoff irrelevant messages and gradually adjust their behavior. In short run, the players’ access to the actions of the coordination
game may be restricted. While the players can revise the set of accessible actions only occasionally, they frequently adjust their behavior
in the cheap-talk game, taking the set of currently available actions asgiven. We obtain an efficient-equilibrium-selection result if the underlying coordination game satisfies the self-signalling condition. On theother hand, if the game is not self-signalling, both the efficient andthe inefficient equilibrium outcomes are stable.

JEL Classification Number: C72
Key Words: coordination games; communication; evolution; efficiency;
cheap talk.

∗Research Institute for Economics and Business Administration, Kobe University. 2-1
Rokkodai-cho Nada-ku Kobe 657-8501 Japan. Email: amaya@rieb.kobe-u.ac.jp1

1

Introduction

There are many interesting economic and social problems that can be analyzed as coordination games. Since coordination games have multiple equilibria, the question of equilibrium selection has attracted much interest. For
example, the literature in stochastic evolution (e.g. Kandori, Mailath andRob [9] and Young [17]) and the literature in robustness to incomplete information (e.g. Carlsson and van Damme [4]) have selected risk dominantequilibria (Harsanyi and Selten [8]).
There has been a substantial literature in evolutionary game theory whichargues that if players can communicate each other before playing the game,then the evolutionary force leads to Pareto efficient equilibria (e.g. Robson [13], Wärneryd [16], Matsui [11], Kim and Sobel [10]).
The essential idea in evolutionary game theory is that the players play
the same game repeatedly and gradually adjust their behavior. In the evolutionary analysis of pre-play communication, the game to be repeated is acheap-talk game, which consists of two stages. In the first stage, each player
sends a message. In the second stage, each player chooses an action of thecoordination game. The second stage actions can be contingent on the messages observed in the first stage. Therefore, a strategy of the cheap talk gameconsists of two components: (i) a messege to send in the first stage and (ii)a decision rule, which specifies an action to play in the second stage for eachpossible outcome in the first stage. If we fix the set of strategies in the coordination game and the message space, then the strategy space of the cheap
talk game is determined accordingly.
The existing literature on evolution and pre-play communication has assumed (explicitly or in some indirect way) that whenever a player faces anopportunity to adjust her behavior, she can freely adopt anything in thestrategy space of the cheap talk game. In this paper, we claim that thisassumption is not very realistic in many economic applications. We showthat if we modify this assumption in a certain reasonable way, the efficientequilibrium-selection result does not hold any more.
Consider the following example which illustrates the motivation for ourapproach. Suppose there is a society with many people. People are randomly matched into pairs and engage in some productive activity. Each
player chooses between “Big Project” and “Small Project”. The Big Projectsucceeds only when the two players collaborates. If only one player chooses
2the Big Project, she incurs a cost in vain. This game has two pure strategy Nash equilibria; one in which both players choose “Big Project” and theother in which both players choose “Small Project”. Suppose the former
equilibrium Pareto dominates the other. In other words, this is a coordination game. In the cheap-talk extension of this game, each player first sends
a message and then chooses an action of the coordination game.
Now suppose that in order to work on a project, one needs to have aproject-specific equipment (or know-how, or ability) in his hand. Only occasionally does a player have an opportunity to acquire a new equipment
or abondon an existing equipment. In contrast, a player frequently faces anopportunity to adjust the behavior in the cheap talk game, taking the setof equipment in hand as given. For example, if a player has equipment for
both projects, he can choose anything in the strategy space of the cheap talkgame. On the other hand, if he has only the equipment for “Small Project”,
then he is forced to choose “Small Project” in the second stage of the cheap
talk game. However, he still has a freedom in the choice of his message inthe first stage.
This story sounds very reasonable if we consider real economic problems.
A manufacturing firm makes decisions of building a new factory or closing
an existing factory only occasionally. In contrast, it adjusts the project toimplement and how to communicate with other firms with much mobility.
Based on the above motivation, this paper analyzes the effects of pre-playcommunication on equilibrium selection under an evolutionary adjustment
process with the following properties: (i) The players adjust the set of accessible actions of the coordination game only occasionally. (ii) The players
frequently adjust their behaviors in the cheap-talk game, taking the set ofaccessible actions as given.1
We analyze 2×2 symmetric coordination games with two symmetric purestrategy Nash equilibria that are Pareto ranked. We show that whether weobtain an efficient-equilibrium-selection result depends on the structure of
the underlying coordination game, i.e., whether the game is self-signalling ornot.

1
We call strategies in the cheap talk game behaviors to avoid confusion, because we willlabel another object as strategy.

3aba 9, 9 0, 6
b 6, 0 7, 7
Figure 1.
abab9, 9 0, 8
8, 0 7, 7
Figure 2.

A game is said to be self-signalling if a player has a right incentive to reveal
her intention of play. Consider the game of Figure 1. If the row player isplanning to play b, then she has a right incentive to reveal her intention. If
she can successfully convince the column player of her intention of playing
b, then the column player’s rational reaction is to play b, and the row player
receives 7. On the other hand, if the row player misleads the column player
to believe she will play a, this leads the column player to play a, which gives
the row player the payoff of 6. Similarly, if the row player is planning toplay a, then she has a right incentive to reveal it. Therefore this game isself-signalling.
In contrast, in the game of Figure 2, if the row player is planning toplay b, then she does not have a right incentive to reveal her intention. If
she convinces the column player that she will indeed play b, this leads thecolumn player to play b, and her payoff will be 7. If the row player deceives
the column player and lets him believe she will play a, then the column
player plays a and the row player’s payoff will be 8. Therefore this game is
not self-signalling.
For general 2 × 2 symmetric coordination games, if we call the efficientequilibrium strategy a and the inefficient equilibrium strategy b, then thegame is self-signalling if and only if (b, b) gives a higher payoff than (b, a) tothe row player.2
We show that if the underlying coordination game is self-signalling, then
only the Pareto efficient equilibrium outcome is stable. If the underlying game is not self-signalling, then both the efficient equilibrium outcome
and the inefficient equilibrium outcome are stable. Therefore an efficientequilibrium-selection result is obtained if and only if the underlying game2
For more discussion on the self-signalling condition, see a survey of the cheap talkliterature by Farrell and Rabin [6] .

4

is self-signalling. We emphasize here that these results have nothing to dowith the risks of the equilibria. Both in the games of Figure 1 and Figure 2,
the inefficient equilibrium (b, b) is risk dominant. If we increase the payoffs
in the efficient equilibrium (a, a) to 50, then this equilibirum becomes risk
dominant while the self-signalling condition is unchanged.
The result which should be highlighted in comparison with the existing
literature is that the inefficient equilibrium outcome is now stable if the gameis not self-signalling. Let us give an intuition for this result here.
The argument in the existing literature is as the following. Suppose that
initially all the players are playing the inefficient equilibrium action (action b). Now a small population of mutants enters. These mutants senda new message that is not used by the incumbents, and plays the efficientequilibirum action (action a) if and only if the opponent also sends this newmessage. They play b otherwise. After the entry of these mutants, an incumbent player always receives the inefficient equilibrium payoff. On the other
hand, a mutant player receives the inefficient equilibrium payoff when she
is matched with an incumbent, and receives the efficient equilibrium payoff
when matched with another mutant. Therefore, the mutants receive a higher
payoff on average and invade the population. The key point here is that the
mutants can separate themselves away from the incumbents through messages and can coordinate on the efficient equilibrium only among themselves.
This is so called “secret handshake” effect of communication.
Now consider what happens in our analysis. There are three possible
types of players in terms of accessibility to the actions; type a, who hasaccess only to action a, type b, who has access only to action b, and types, who can access both strategies.3 Imagine initially only type b players
exist in the population. Suppose now a small population of mutants enters.
These mutants are type s and plays the “secret handshake” behavior as
described in the previous analysis. Now, before these type s mutants thrivein the population, the incumbents can immediately adjust their messages,
because we are assuming that the adjustment of behaviors under a fixed
type distribution occurs much more frequently than the evolution of types.
If these mutants enter, the incumbents always try to send the same message
3
Of course, we can think of another type who can access neither action. We can consider
a model with this type by properly defining the payoff from playing neither action, i.e.,
exiting the game. We expect this consideration will not change our result.

5

as the munants so as to induce the mutants to play action a. Therefore, themutants can never successfully separate themselves out from the incumbent
through messages. Here, a secret handshake does not work. In fact, theincumbents have such an incentive to pool with the mutants if and only if
the game is not self-signalling.
Let us turn to a discussion of our modelling methodology. In our model,
two things evolve over time. First, the population distribution of types
evolves. Second, the behaviors of the players in the cheap-talk game evolve.
Since we assume the behaviors of the players are adjusted much more frequently than the evolution of types, we separate these two evolutions in thefollowing way. For each fixed type distribution, we look for stable outcomesin the adjustment of behaviors and examine how well each type performs
in the stable outcomes. We model the evolution of the type distribution in
the way that the type earning a higher payoff in the stable outcomes thrives
better. This is the same approach as the literature in evolutoin of preferences(e.g. Ely and Yilankaya [5] and Sandholm [14]). In fact, we can find muchanalogy between our problem and evolution of preferences. In the study of
evolution of preferences, the players’ preferences evolve slowly, while they
adjust their behavior in games taking the current preference as exogenously
fixed.
The rest of the paper is organized as the following. Section 2 describes thecheap talk game, which is to be repeated. Section 3 defines the types of theplayers and the equilibrium under a fixed type distribution. Section 4 studies
the evolution of the type distribution. Section 5 considers the evolution of
behaviors under fixed type distributions. Section 6 discusses how our result
may be changed if we alter some of our assumptions. Section 7 surveys therelated literature. Section 8 concludes.

2

The Cheap Talk GameLet G be the base game. We assume G is a 2 × 2 symmetric coordination
game. The set of pure strategies is {a, b} and πij , i, j = a, b is the payoff
when a player plays i and the opponent plays j. Thus the payoff matrix is
given by Figure 3.

6aba πaa , πaa πab , πba
b πba , πab πbb , πbb
Figure 3.
Assume πaa > πba , πbb > πab , and πaa > πbb . By the first two inequalities thegame has two symmetric pure strategy Nash equilibria, namely both playing
a and both playing b. The last inequality says the former equilibrium isPareto efficient. Also assume there is no tie in payoffs. The game is said tobe self-signalling if πbb > πba . To avoid confusion later, we call the strategies
in the base game actions.
Players are randomly matched into pairs and play the cheap talk game.
The cheap talk game consists of two stages. In the first stage, both players
send a message m ∈ M = {m1 , m2 } simultaneously. In the second stage, bothplayers play either a or b of the base game simultaneously, having observed
the messages sent in the first stage. The play in the second stage can becontingent on the message sent by the opponent in the first stage. The
payoff from the cheap-talk game is determined by the actual action chosen in
the second stage. The first stage messages do not directly affect the players’
payoffs.
To avoid confusion later, we call the strategies in the cheap talk game
behaviors. A behavior σ = (µ, f ) in the cheap talk game consists of two
components. The first component µ ∈ M specifies which message to sendin the first stage. The second component f , which we call a decision rule,
specifies an action of the base game to play in the second stage for eachrealization of the opponent’s message in the first period. Therefore, a decision
rule is a mapping from the message space to the action space. There are four
possible (pure) decision rules fa , fb , fc and fd .
fa (m1 ) = fa (m2 ) = a,fb (m1 ) = fb (m2 ) = b,fc (m1 ) = a, fc (m2 ) = b,
fd (m1 ) = b, fd (m2 ) = a.
We denote the set of all decision rules by F = {fa , fb , fc , fd }.

7

3

Types of the Players and Short Run Games

The type θ of a player describes which actions of the base game are available
for the player. The set of possible types is Θ ≡ {a, b, s}. A player of type acan play only action a, and a player of type b can play only action b. Thereis a third type, called type s, who can choose between actions a and b.
Since a type a player can access only action a, the set of behaviors available for type a players is Σa = {(m1 , fa ), (m2 , fa )}. Similarly, the set of
behaviors available for type b players is Σb = {(m1 , fb ), (m2 , fb )}. Since types players can follow any of the decision rules in F , the set of behaviors available for them is Σs = M × F .
Let x = (x(a), x(b), x(s)) be a vector representing the population ratio of
each type in the whole population, where x(θ) is the proportion of type θ.
Naturally, we require x ∈ ∆Θ where∆Θ ≡ {(x(a), x(b), x(s)) ∈ R3 : x(θ) ∈ [0, 1],

X

x(θ) = 1}.

θIn the rest of the paper, we refer to x as a type population state (TPS).
The idea of this paper is that in the short run, each player takes theset of accessible actions as given and adjust the behavior in the cheap-talkgame. In the terminology of our model, the type of each player is exogenously
fixed (and thus the TPS is fixed) and the players choose their behaviors. We
will call this strategic interaction as a short run game. We assume thatthe adjustment of behaviors is sufficiently fast so that an equilibrium of theshort run game is always played. To properly define the equilibrium conceptof the short run game, we need to specify the information structure. We
assume that each player knows her own type but does not know the typeof the player whom she is matched with. However, the players know thecurrent TPS and also know that the random matching obeys the uniform
distribution. Therefore, the short run game can be described as a game ofincomplete information.
We denote a strategy of the short run game by y. A strategy y specifies
a probability distribution over Σθ for each type θ. Formally, let ∆Σθ be theset of probability distributions over Σθ andy : Θ → ∪θ∈Θ ∆Σθ ,where yθ ∈ ∆Σθ for all θ. Here yθ (σ) is the probability of playing strategy σwhen the type is θ, and yθ = {yθ (σ)}σ∈Σs .
8Here we limit our attention to symmetric equilibria, where all the players
are playing the same strategy y. This is without any loss of generality. It canbe easily verified that if there is an asymmetric Bayesian Nash equilibriumof the short run incomplete information game where proportion α of players
play strategy y and proportion 1 − α of players play strategy y 0 , then thestrategy profile in which all the players are playing αy + (1 − α)y 0 is also a
Bayesian Nash equilibrium.
Let u(σ, σ̃) be the payoff in the cheap talk game to a player when sheplays behavior σ = (µ, f ) and the opponent plays σ̃ = (µ̃, f˜). Therefore,u(σ, σ̃) = πf (µ̃),f˜(µ) .
We assume that a player is randomly matched with another player according
to the uniform distribution. Therefore, under the TPS x, if all the otherplayers are following strategy y, the expected payoff to a player with behavior
σ is given by
X Xv(σ|x, y) =u(σ, σ̃)yθ̃ (σ̃)x(θ̃).
θ̃∈Θ σ̃∈Σθ

Notice that the expected payoff to a player depends on her behavior, but not
on her type. A behavior σ ∈ Σθ is called a best response for a type θ player
against strategy y under the TPS x, if it gives the highest expected payoff
among the behaviors in Σθ . The set of pure best responses to a type θ player
against y under the TPS x is denoted byBRθ (x, y) = argmaxσ∈Σθ v(σ|x, y).
Let BRθ (x, y) be the set of mixed best responses to a type θ player againsty under x, i.e., the set of probability distributions on Σθ which puts positive
probabilities only on the members of BRθ (x, y). We write y 0 ∈ BR(x, y) if
for all θ ∈ Θ, yθ0 ∈ BRθ (x, y). The equilibrium concept of the short run gamecan be defined as the following.
Definition A strategy y is a Bayesian Nash Equilibrium (BNE) under thetype population state (TPS) x if
y ∈ BR(x, y).

9

4Stability of Type Distributions

4.1

The Stability Concept

Now, we define the stability concept of type population states (TPS). The
stability concept we use here borrows the backbones from the traditional stability concepts in evolutionary game theory. To illustrate the idea, consider
the stability of a TPS where all players are of the same type θ. Suppose that
initially all the players are of type θ. Now inject a small populaiton share ² oftype θ0 individuals (θ0 6= θ). The players immediately adjust to play a BNEof the short run game under the ex-post TPS (1 − ²)θ + ²θ0 . The initial TPS
is not invaded by an injection of θ0 if, for sufficiently small ², type θ0 does notreceive higher payoff than type θ in any BNE under the ex-post TPS. The
initial TPS is stable if it is not invaded by any small population of mutants,
where the mutants may be a mixture of multiple types. The following definition generalizes this idea. This formal definition allows both the incumbent
population and the mutant population be a mixture of multiple types.
Definition A TPS x ∈ ∆Θ is stable if
for all x0 ∈ ∆Θ, there exists ²̄ ∈ (0, 1), such that ∀² ∈ (0, ²̄),´X³ Xv(σ|(1 − ²)x + ²x0 , y)yθ (σ) x(θ)θ∈Θ σ∈Σθ

≥

X³ X

´

v(σ|(1 − ²)x + ²x0 , y)yθ (σ) x0 (θ)θ∈Θ σ∈Σθfor all y such that y is a BNE under (1 − ²)x + ²x0 .
Notice the same expressionXv(σ|(1 − ²)x + ²x0 , y)yθ (σ)σ∈Σθ

appears in both side of the inequality. This is the expected payoff of a type θindividual in the BNE y under the post entry TPS (1 − ²)x + ²x0 . Therefore,
the left hand side of the equation is the average post-entry payoff of theincumbents, and the right hand side is the average post-entry payoff of themutants.
10

Two remarks must be stated about this definition of stability. First, sofar, we are staying away from the issue of equilibrium selection in the short
run games. This is of course an important issue and we will discuss it in thenext section. However, we can claim the following. If we find that a TPS
is stable, then we do not need to worry about the equilibium selection in
the short run games. This is because the stability in this definition meansthat no matter what equilibrium is played in the post-entry short run game,the mutants cannot earn a higher average payoff than the incumbents. On
the other hand, if we find that a TPS is not stable, we need to be careful
about the equilibrium selection in the short run game. Instability here means
only that there exists some equilibrium in which the mutants’ average payoff
exceeds the incumbents’ average payoff. But this equilibrium may be an
unreasonable prediction if we think about the equilibrium selection issue.
It is possible that in “reasonable” equilibria the mutants can never earn ahigher payoff than the incumbents.
Second, notice the condition is a weak inequality. It only requires thatno mutant thrives in the sense of earning a strictly higher payoff than theincumbent. This corresponds to the concept of neutrally stable strategy(NSS) in the traditional evolutionary game theory. One may think that it ismore reasonable to require the condition to hold in a strict inequality, whichcorresponds to the concept of evolutionarily stable strategy (ESS). Such a
condition requires that no mutant persist in the sense of earning an equal or
higher payoff than the incumbent. Our result does not hold any longer if we
employ such an ESS-like stability concept.

4.2

Results

Now we state our results. We do not fully characterize the set of stable TPSs.
Instead, we investigate if there is a stable TPS with an outcome such that all
players play the same action of the base game, i.e., an outcome corresponding
to a Nash equilibirum of the base game.
Our first finding is that the Pareto efficient equilibrium outcome is stable.
Proposition 1 Let xs be the TPS such that xs (s) = 1 and xs (a) = xs (b) =0. Then, xs is stable.
Proof See Appendix.
11

Of course, this proposition alone does not tell us the Pareto efficient equilibrium outcome is stable. It is supplemented by Proposition 4 in Section 5.
Proposition 1 says that the TPS where only type s is present is stable. In
this TPS, the short run game has multiple equilibria, in particular an equilibrium in which everyone plays a and another one where everyone plays b.
Proposition 4 shows that if we consider evolution in the short run game, theunique stable outcome is such that everyone plays a.
The intuition for the proof of Proposition 1 is straightforward. Sincea type s player has more freedom in choosing behaviors than other types,
she can imitate the behavior of a player of type a or b. Therefore, in any
equilibrium of the short run game, type s’s payoff is at least as good as othertypes’ payoffs. Hence, a mutant’s payoff can never exceed the payoff of thetype s incumbents.
Secondly, we show that if the base game satisfies the self-signalling condition, then the Pareto inefficient equilibrium outcome is unstable. The only
candidate TPSs in which all the players are playing action b are the TPSs
where only type b and type s are present. Because Proposition 4 in the next
section rules out xs from the candidates, it suffices to show that the TPS
with a positive share of type b is unstable. Proposition 2 shows this.
Proposition 2 For β ∈ (0, 1], let xβ be the TPS such that xβ (a) = 0,xβ (b) = β and xβ (s) = 1 − β. If the base game is self-signalling, thenfor all β ∈ (0, 1], xβ is not stable.
Proof See Appendix.
To prove this, we show that the itinial TPS is unstable against a injectionof type s mutants. In the post-entry TPS, both type s and type b have astrictly positive population share and there are no type a players. Lemma
1 shows that for such an TPS there exists an equilibrium in which type s
receives strictly higher payoff than type b.
Lemma 1 For all β ∈ (0, 1), there exists a strategy of the short-run gamey β such that y β is a BNE under xβ andXv(σ|xβ , y β )ysβ (σ) >

X
σ∈Σb

σ∈Σs

12

v(σ|xβ , y β )ybβ (σ).

Since the incumbents are a mixture of type s and type b and the mutants aretype s, the mutants receive a higher payoff than the incumbents on average.
As we discussed in the remark following the definition of stability, we need
to be careful about whether this instability result is robust to the equilibrium
selection issue in the short run games. In other words, it must be shown thatthe equilibrium in Lemma 1 is a reasonable one. Proposition 5 in the next
section shows that there indeed exists an equilibrium satisfying the condition
in Lemma 1, which is stable with respect to evolution in the short run games.
Lastly, we show that if the base game is not self-signalling, then the Pareto
inefficient equilibrium outcome is stable.
Proposition 3 Let xb be the TPS such that xb (b) = 1 and xb (a) = xb (s) =0. If the base game is not self-signalling, then, xb is stable.
Proof See Appendix.
To prove this, we show that for any post-entry TPS where the population
ratios of type a and type s are sufficiently small, there is no Bayesian Nashequilibrium of the short run game in which type a or type s receives a strictly
higher average payoff than type b. This result shows that if the coordination game is not self-signalling, a secret handshake cannot happen in any
equilibrium of the post-entry short run games.

5

Equilibrium Selection in Short Run Games

This section considers the equilibrium selection problems in short run games.
In the previous section, we were assuming that under each TPS some equilibrium of the short run game is played, and we did not discuss which equilibrium should be played if the short run game has multiple equilibria. Now
we explicitly examine this issue by an evolutionary approach.
This section has two goals. First, we show that in the TPS xs , which wasshown to be stable in Proposition 1, there is a unique outcome that is stablein terms of evolution in the short run game, where all players play action aof the base game.
Second, we show that Proposition 2 is robust with respect to equilibrium
selection in short run games. Proposition 2 says that for β ∈ (0, 1] the TPS
xβ is unstable in the sense that if a certain kind of mutants enters the population, then the mutants receive a higher payoff than the incumbents in some13

equilibrium in the post-entry short run game. In particular, the mutantsreceive a higher payoff than the incumbents in an equilibrium described in
Lemma 1. Now we show that this equilibrium is indeed reasonable, i.e., thisequilibrium is stable in terms of evolution in the short run game.
Our approach here is as the following. We fix a TPS x and asks whether
a set of Bayesian Nash equilibria under x is stable or not. The stability
concepts we use here are cyclically stable set (CSS) proposed by Gilboa andMatsui [7] and equilibrium evolutionarily stable set (EES set) proposed by
Swinkels [15]. Since Matsui [12] showed the equivalence of these two concepts,
we are essentially working with only one solution concept. However, we use
the names of both solution concepts just to make our argument simple andclear.

5.1

Stable Outcome under the TPS xs

Under the TPS xs , all the players have an access to both action a and actionb of the base game. Intuitively speaking, when a player faces an opportunity
to revise her behavior, she can simultaneously choose any message and decision rule. This is exactly the situation analyzed in the existing literature inevolutionary analysis of equilibrium selection with pre-play communication.
In particular, The environment Matsui [11] analyzes coincides exactly withthe short run game under the TPS xs in our model. Matsui considers thecase where the base game is a 2×2 symmetric game with two symmetric purestrategy Nash equilibria that are Pareto ranked and the size of message space
is two. Matsui showed that there is a unique CSS and every strategy distribution in the CSS yields the outcome that all players play the Pareto efficientequilibrium action. We can simply apply Matsui’s result to our analysis.
Proposition 4 Under the TPS xs , there is a unique CSS in the short run
game and every strategy distribution in the CSS yields the outcomethat all players play a.
Proof See Matsui [11].

5.2

Robustness of Proposition 2

Here we show that for all β ∈ (0, 1), there exists a “stable” equilibrium of
the short run game which satisfies the condition in Lemma 1. We use EES
14

set as our solution concept. Let ∆ denote the strategy space of the short run
game.
Definition Y ⊂ ∆ is an equilibrium evolutionarily stable (EES) set under
the TPS x if it is minimal with respect to the following property: (i)Y is a nonempty and closed set of Bayesian Nash equilibria under xand (ii) there exists ²̄ > 0 such that ∀² ∈ (0, ²̄), ∀y ∈ Y and ∀y 0 ∈ ∆,y 0 ∈ BR(x, (1 − ²)y + ²y 0 ) implies (1 − ²)y + ²y 0 ∈ Y .
Proposition 5 Suppose the base game is self-signalling. Let y ∗ and y ∗∗ be
the strategies in short run games defined below:• ya∗ (m1 , fa ) = yb∗ (m2 , fb ) = ys∗ (m1 , fc ) = 1.
• ya∗∗ (m2 , fa ) = yb∗∗ (m1 , fb ) = ys∗∗ (m2 , fd ) = 1.
(i) For all β ∈ (0, 1), {y ∗ } and {y ∗∗ } are (singleton) EES sets under the
TPS xβ . (ii) Furthermore, for all β ∈ (0, 1), both y ∗ and y ∗∗ satisfy theinequality in Lemma 1.
Proof See Appendix.

6

Discussion

This section discusses the robustness of our result with respect to the assumptions made in our model and possible extensions. In particular, we consider
the issue of the solution concept and the size of message spaces. Also, we
make an informal discussion for the reverse case, i.e., the case where themessages evolve slowly.

6.1

Solution Concept

As we mentioned in Section 4.1, our result does not remain true if we use
a stronger stability concept which requires that the incumbents receive astrictly higher payoff than the mutants. In particular, Proposition 3 does
not hold any more. If a small population of type s mutants enters, theyreceive the same payoff as the type b incumbents, and thus they stay inthe population, although they do not grow. One may feel Proposition 3
15

is an unsatisfactory result beause an accumulation of type s mutants may
increase their population share gradually and they may eventually performbetter than type b. We can overcome this problem by slightly modifying ourmodel. Suppose there are small fixed costs of keeping actions accessible. For
example, these costs are the maintenance costs of factories in the example in
Introduction. These costs enter the utility in a lexicographic manner. We say
a player does better than another if either he receives a strictly higher payofffrom the game or he receives the same payoff and incurs less cost of keeping
actions. With these costs, the state xb becomes stable under the stronger
stability concept. If a small population of type s mutants enter, then theyreceive the same payoff as the incumbents and incur more fixed costs. The
readers may feel the lexicographic representation of the fixed costs is too
artificial and unrealistic. We claim it is not. In the real world, very manybut only finite people are interacting each other. A continuous population
model is only an approximation for such a society. Suppose the fixed cost isso small that one player’s payoff may be increased or decreased by more than
the fixed cost if only one of the other players changes the behavior. In sucha case, the entry of the smallest possible population of mutants may havea larger impact than the fixed cost. However, when we consider stability ina continuous population model, the population share of the mutants can betaken arbitrarily small so that the impact of the mutants’ entry can neverdominate the fixed cost. If we remain working with a continuous population
model and want to incorporate the possibility that the minimal mutants’effect dominate the fixed cost, it is fairly reasonable to model the fixed costin a lexicographic manner.

6.2

The Size of The Message SpaceWe worked on a model with the message space of size two, primarily fornotational simplicity. Here we argue that our results remain to hold when thesize of the message space is larger. Generally speaking, the secret handshake
becomes easier as the size of the message space becomes larger, because it
becomes easier for the mutants to find a message that is not used by theincumbents. Thus we are looking at the environment where destabilizing
the inefficient equilibrium outcome is the most difficult. Proposition 2 and 4
show that even in such an environment, we can still destabilize the inefficientequilibrium. It is natural to guess that the same result can be obtained for16the cases with larger message spaces. On the other hand, Proposition 3 may
be regarded as a weak result because it only shows that the secret handshakeis impossible in the most difficult environment. However, this result does
not depend on the smallness of the message space. We can easily extend theresult to the cases with larger message spaces.

6.3

Slow Adjustment of Messages

Consider the opposite case where the players change their messages only
occasionally. In short run, each player takes his message as given and adjust
their decision rules. This consideration applies to some biological evolution
issues. Here a message is interpreted as a physical trait of an animal. A
physical trait is inherited from ancestors and each individual animal takes
it as exogenously given. Each individual animal frequently adjust which
action to play in the coordination game, and the action may depend on
the opponent’s appearance, i.e., the message. With this interpretation, it isreasonable to assume it is the message of each individulal player that evolves
slowly, rather than the set of available messages.
Consider the cheap talk game defined in Section 2. There are two typesof players, i ∈ {1, 2}. A type i player is forced to send message mi in thefirst stage. However, he can adopt any decision rule in F = {fa , fb , fc , fd }.
Suppose initially only type 1 players are present and they are playing
action b. We investigate if an injection of type 2 mutants can destabilize theinefficient equilibrium outcome. Suppose the type 1 incumbents are using
the decision rule fb , i.e., they always play action b. In this case, the type 2
mutants can do better than the incumbents if they adopt fd , i.e., play actionb when observing message m1 and play action a when observing message
m2 . After the entry of these mutants, a type 1 incumbent always receives
the inefficient equilibrium payoff. A type 2 mutant receives the inefficientequilibirum payoff when she is matched with an incumbent, and receives theefficient equilibrium payoff when matched with another mutant. A type 1
incumbent has no incentive to change her decision rule if all the other type 1
players are following fb and all type 2 players are following fd In fact, it is anequilibrium of the short run game. Therefore, type 2 thrives and eventually
dominates the population, and they play the efficient equilibrium. The same
logic as the existing literature works here and the efficient equilibrium isselected no matter whether the game is self-signalling or not. One may worry
17

the mutants cannot separate themselves through messages if both type 1 and
2 are initially present and they are playing the inefficient equilibrium. We
can overcome this problem by just applying the argument of drift in theexisting literature.

7

Related Literature

Our argument that the self-signalling condition is necessary for a communication to help achieving the efficient equilibrium has an analogy with Aumann’s [1] discussion. Aumann raises a question to the old justification for
Nash equilibrium as “self-enforcing agreements”, which claims that a preplay agreement to play a certain strategy profile will be kept if and only if
it is a Nash equilibrium. Aumann considers the game of Figure 2 and starts
from assuming that players are cautious so that they are likely to play therisk dominant equilibrium (b, b) without communication. Aumann asks if a
pre-play agreement to play (a, a) will be kept. Aumann argues that even if
a player is very cautious and therefore is planning to play b in any case, shewants to agree on playing (a, a) because it leads the other player to choose
a and induces her a higher payoff. Therefore, the fact that an agreement isachieved contains no information about the intention of the opponent andthus there is no reason to keep the agreement.
Baliga and Morris [2] discuss the relevance of Aumann’s intuition to two
player games with one-sided incomplete information. In Baliga and Morris’s
model, one player has a payoff relevant private information. In the cheap-talkgame, the informed player sends a message and then the two players choose
an action. They ask (i) when there is full communication, in the sense thatthe informed player truthfully reveals his type and the players then play aNash equilibrium of the underlying complete information game and (ii) when
there is no communication, so that the equilibria of the cheap talk game areoutcome equivalent to equilibria where cheap talk is not allowed. Baliga andMorris show that if the uninformed player has only two actions, then a failureof self-signalling implies that no communication is possible. The short run
game in our model can be interpreted as an extension of Baliga and Morris’s
analysis to two-sided incomplete information.4 Although we do not know
4
In Baliga and Morris’s model, the action space of a player is independent of his type.
Our model fits their framework if we assume that a type a (type b) player can acess action18

in general how Baliga and Morris’s results can be extended to games with
two-sided incomplete information, our result suggests similar results may beobtained.
Blume [3] demonstrates a possibility that evolution and communication
may fail to select the efficient equilibrium outcome, by a different approachfrom ours. Blume points out that the previous literature in evolution andcommunication considered models in which the dynamics are gradual, especially an arrival of mutants affects only a small fraction of the entire
population. Blume proposes a class of population dynamics which permit
simultaneous adjustment of strategies of large fractions of the populationand shows that whether the efficient-equilibrium-selection result is obtained
depends on the risks of the underlying game and the size of the message
space. Our analysis does not depart from the previous literature in the sensethat the adjustment is only gradual, and our result has nothing to do withthe risks. On the other hand, Blume keeps the same assumption with theprevious literature that whenever a player faces an opportunity to adjust her
behavior, she can freely adopt anything in the strategy space of the cheap
talk game. The self-signalling condition does not distinguish the result inBlume’s model.

8Conclusion

In many economic problems, the set of available alternatives in game theoretic situations is determined endogenously. In particular, long term decisions such as opening and closing a factory may restrict the flexibility ofshort term decisions such as choosing which product to produce. Therefore
it is worthwhile to analyze an evolutionary model in which the set of available actions is adjusted slowly and the short term adjustments are restrictedby the availability. This paper studied the effect of pre-play communication
on equilibrium selection in coordination games and showed that the existing
efficiency result is fragile to the consideration of the difference in the speedof evolution. The incentive of a player to pool with players with different
availability is the main obstruction in achieving efficiency.
b (action a) but this action is very costly so that action a (action b) is the dominant
strategy.

19

A

Appendix: Proofs

A.1

Proof of Proposition 1

Fix x0 ∈ ∆Θ and ² ∈ (0, 1) arbitrarily. Let y be a BNE under (1 − ²)xs + ²x0 .
From the definition of BNE,X

v(σ|(1 − ²)xs + ²x0 , y)yθ (σ) = max v(σ|(1 − ²)xs + ²x0 , y)
σ∈Σθ

σ∈Σθ

for all θ ∈ Θ. Since Σa ⊂ Σs and Σb ⊂ Σs ,max v(σ|(1 − ²)xs + ²x0 , y) ≥ max v(σ|(1 − ²)xs + ²x0 , y),
σ∈Σs

σ∈Σθ

for θ ∈ {a, b}. Now,
Xµ X

¶
s

0

v(σ|(1 − ²)x + ²x , y)yθ (σ) (xs (θ) − x0 (θ))θ∈Θ σ∈Σθ==Xµmax v(σ|(1 − ²)x + ²x , y) (xs (θ) − x0 (θ))

θ∈Θ

X µ

¶

s

s

0

σ∈Σθ

¶

0

max v(σ|(1 − ²)x + ²x , y) − max v(σ|(1 − ²)x + ²x , y) x0 (θ)θ∈{a,b}

s

σ∈Σs

0

σ∈Σθ

≥ 0,
which proves the proposition.

A.2

Proof of Proposition 2

Lemma 1 For all β ∈ (0, 1), there exists a strategy of the short-run gamey β such that y β is a BNE under xβ andXv(σ|xβ , y β )ysβ (σ) >

σ∈Σs

X

v(σ|xβ , y β )ybβ (σ).

σ∈ΣbProof For all β ∈ (0, 1), let a strategy y β satisfy ysβ (m1 , fc ) = 1, yaβ (m1 , fa ) =1 and ybβ (m2 , fb ) = 1. It can be easily verified that this is indeed a BNE
if the base game is self-signalling. The left hand side of the inequalityis (1 − β)πaa + βπbb and the right hand side is πbb . Therefore, theinequality holds.
20

Proof of Proposition 2
Let x = xβ and x0 = xs . Fix any ² ∈ (0, 1). Then, (1 − ²)x + ²x0 = x(1−²)β .
From Lemma 1, there exsists y (1−²)β such that y (1−²)β is a BNE under x(1−²)βandXv(σ|x(1−²)β , y (1−²)β )ys(1−²)β (σ) >X(1−²)βv(σ|x(1−²)β , y (1−²)β )yb

(σ).

σ∈Σb

σ∈Σs

This implies thatXµ X¶

v(σ|x(1−²)β , y (1−²)β )ys(1−²)β (σ) x0 (θ)θ∈Θ σ∈Σθ

>

Xµ X

¶

v(σ|x

(1−²)β,y(1−²)β(1−²)β
)yb
(σ)

x(θ).

θ∈Θ σ∈Σθ

Therefore, xβ is not stable.

A.3

Proof of Proposition 3

Let η > 0 be a positive constant. We claim that if η is sufficiently small,then under any TPS x with x(b) ≥ 1 − η, there exists no BNE of the short
run game in which either type a or type s receives a higher payoff than typeb. Once the claim is established, proof of the proposition is straightforward.
Now we prove the claim. First we show that in any equilibrium type adoes not receive a higher payoff than type b. A type a player is matched with
type b and receives a payoff πab with at least probability 1 − η. Therefore, atype a player’s average payoff is no greater than (1 − η)πab + ηπaa . A type b
player is matched with another type b and receives a payoff πbb with at least
probability 1 − η. Therefore, a type b player’s average payoff is no less than
(1 − η)πbb + ηπba . For η sufficiently small, (1 − η)πab + ηπaa < (1 − η)πbb + ηπba
holds. Thus, type a never receives a higher payoff than type b.
Next we show that there does not exist any equilibrium in which type s
receives a strictly higher payoff than type b. Suppose such an equilibirum
exists. The equilibrium is denoted by y. First, in this equilibrium the decision
rule fa is not chosen with positive probability by type s. This is because thedecision rule fa can never yield a higher payoff than type b players by thesame argument as above. Second, if type s chooses the decision rule fb with21

probability 1, then type s and type b receive the same payoff. Therefore, in
equilibrium y, either fc or fd must be chosen with positive probability bytype s.
• Consider the case where fc is chosen with higher probability than fd .
In this case, a type b player’s best response is only (m1 , fb ), and thus
we have yb (m1 , fb ) = 1. Here, a type s player employing the decision
rule fc receives a payoff πab when she is matched with a type b player.
Therefore, her payoff is no greater than (1 − η)πab + ηπaa . For thesame reason as the previous argument about type a players, here atype s player does not receive a higher payoff than a type b player.
Contradiction.
• The same argument applies to the case where fd is chosen with higher
probability than fc .
• The remaining case is where type s chooses decision rules fc and fd
with a posive and equal probability. This case can be divided into two
sub-cases. First, consider the case where yb (m1 , fb ) ≥ 12 . When a types player with the decision rule fc is matched with a type b player, her
expected payoff is yb (m1 , fb )πab + yb (m2 , fb )πbb , which is less than orequal to 21 (πab + πbb ). Therefore the payoff for a type s player with thedecision rule fc is no greater than (1−η) 12 (πab +πbb )+ηπaa . On the other
hand, a type b player’s average payoff is no less than (1 − η)πbb + ηπba .
Therefore, for a sufficiently small η, a type b player receives a higher
payoff than a type s player with decision rule fc . This contradicts withthe assumption that y is a BNE where type s receives a higher payoffthan type b and fc is chosen by type s with positive probability by types. For the opposite case where yb (m2 , fb ) ≥ 21 , we can make the same
argument by looking at the payoff of a type s player with the decision
rule fd .
We started from the assumption that there exists an equilibrium in which
type s receives a strictly higher payoff than type b and reached to a contradiction for all possible cases. Therefore we can conclude that such anequilibrium does not exist.

22

A.4

Proof of Proposition 5

The second statement of the theorem can be easily verified and thus theproof if omitted. Here we prove the first statement only for {y ∗ }, because
the proof for {y ∗∗ } is essentially the same.
Since {y ∗ } is a singleton, it is obviously closed and has no proper nonempty
subset. Therefore, it suffices to show that y ∗ is a BNE and satisfies condition(ii) in the definition of EES set.
It can be easily verified that for all β ∈ (0, 1),
BRa (xβ , y ∗ ) = {(m1 , fa )},BRb (xβ , y ∗ ) = {(m2 , fb )},BRs (xβ , y ∗ ) = {(m1 , fc )}.
This establishes that y ∗ is a Bayesian Nash equilibrium under xβ .
Since each type has a unique best response, i.e., any other behavior gives
strictly lower payoff, the best response remains the unique best responsewhen other players’ behaviors are slightly perturbed. In other words, for allβ ∈ (0, 1), there exists a sufficiently small ²̄β > 0 such that for all ² ∈ (0, ²̄β )and for all y 0 ∈ ∆,BRa (xβ , (1 − ²)y ∗ + ²y 0 ) = {(m1 , fa )},BRb (xβ , (1 − ²)y ∗ + ²y 0 ) = {(m2 , fb )},BRs (xβ , (1 − ²)y ∗ + ²y 0 ) = {(m1 , fc )}.
Hence, for all θ ∈ Θ, ya00 ∈ BRa (xβ , (1−²)y ∗ +²y 0 ) implies ya00 = y ∗ . Therefore,y 0 ∈ BR(xβ , (1 − ²)y ∗ + ²y 0 ) implies y 0 = y ∗ , and thus (1 − ²)y + ²y 0 ∈ Y .

References[1] Aumann, R. (1990). “Nash Equilibria Are Not Self-Enforcing,” in Economic Decision Making: Games, Econometrics and Optimization, (J.
J. Gabszewicz, J.-F. Richard, and L. A. Wolsey, Eds.). Amsterdam:
North-Holland.
[2] Baliga, S., and Morris, S. (2002). “Coordination, Spillovers and Cheap
Talk,” Journal of Economic Theory, 105, 450-468.
23

[3] Blume, A. (1998). “Communication, Risk, and Efficiency in Games,”
Games and Economic Behavior, 22, 171-202.
[4] Carlsson, H., and van Damme, E. (1993). “Global Games and Equilibrium Selection,” Econometrica, 61, 989-1018.
[5] Ely, J., and Yilankaya, O. (2001). “Nash Equilibrium and the Evolutoinof Preferences,” Journal of Economic Theory, 97, 255-272.
[6] Farrell, J., and Rabin, M. (1996). “Cheap Talk,” Journal of Economic
Perspectives, 10, 103-118.
[7] Gilboa, I., and Matsui, A. (1991). “Social Stability and Equilibrium,”
Econometrica, 59, 859-867.
[8] Harsanyi, J. C., and Selten, R. (1988). A General Theory of Equilibrium
Selection in Games, Cambridge and London, MIT Press.
[9] Kandori, M., Mailath, G., and Rob, R. (1993). “Learning, Mutation andLong Run Equilibria in Games,” Econometrica, 61, 27-56.
[10] Kim, Y.-G., and Sobel, J. (1995). “An Evolutionary Approach to PrePlay Communication,” Econometrica, 63, 1181-1193.
[11] Matsui, A. (1991). “Cheap Talk and Cooperation in Society,” Journalof Economic Theory, 54, 245-258.
[12] Matsui, A. (1992). ”Best Response Dynamics and Socially Stable Strategies,” Journal of Economic Theory, 57, 343-362.
[13] Robson, A. J. (1990). “Efficiency in Evolutionary Games: Darwin, Nashand the Secret Handshake,” Journal of Theoretical Biology, 144, 379396.
[14] Sandholm, W. H. (2001). “Preference Evolution, Two-Speed Dynamics,
and Rapid Social Change,” Review of Economic Dynamics, 4, 637-679.
[15] Swinkels, J. (1992). “Evolutionary Stability with Equilibirum Entrants,”
Journal of Economic Theory, 57, 306-332.

24

[16] Wärneryd, K. (1991). “Evolutionary Stability in Unanimity Games with
Cheap Talk,” Economics Letters, 36, 375-378.
[17] Young, P. (1993). “The Evolution of Conventions,” Econometrica, 61,
57-83.

25