Chester Clinic

 

Rieb.kobe-u.ac.jp

An Evolutionary Analysis of Pre-Play Communication and Efficiency in Games Kenichi Amaya∗ November 17, 2004 This paper studies the effects of pre-play communication on equi- librium selection in 2 × 2 symmetric coordination games. The playersrepeatedly play a coordination game preceded by an opportunity toexchange payoff irrelevant messages and gradually adjust their behav-ior. In short run, the players' access to the actions of the coordinationgame may be restricted. While the players can revise the set of acces-sible actions only occasionally, they frequently adjust their behaviorin the cheap-talk game, taking the set of currently available actions asgiven. We obtain an efficient-equilibrium-selection result if the under-lying 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: C72Key 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: [email protected] There are many interesting economic and social problems that can be ana-lyzed as coordination games. Since coordination games have multiple equi-libria, the question of equilibrium selection has attracted much interest. Forexample, the literature in stochastic evolution (e.g. Kandori, Mailath andRob [9] and Young [17]) and the literature in robustness to incomplete in-formation (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 which argues that if players can communicate each other before playing the game,then the evolutionary force leads to Pareto efficient equilibria (e.g. Rob-son [13], W¨arneryd [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 evo-lutionary analysis of pre-play communication, the game to be repeated is acheap-talk game, which consists of two stages. In the first stage, each playersends a message. In the second stage, each player chooses an action of thecoordination game. The second stage actions can be contingent on the mes-sages 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 coor-dination game and the message space, then the strategy space of the cheaptalk game is determined accordingly.
The existing literature on evolution and pre-play communication has as- sumed (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 efficient-equilibrium-selection result does not hold any more.
Consider the following example which illustrates the motivation for our approach. Suppose there is a society with many people. People are ran-domly matched into pairs and engage in some productive activity. Eachplayer chooses between "Big Project" and "Small Project". The Big Projectsucceeds only when the two players collaborates. If only one player chooses the Big Project, she incurs a cost in vain. This game has two pure strat-egy Nash equilibria; one in which both players choose "Big Project" and theother in which both players choose "Small Project". Suppose the formerequilibrium Pareto dominates the other. In other words, this is a coordina-tion game. In the cheap-talk extension of this game, each player first sendsa message and then chooses an action of the coordination game.
Now suppose that in order to work on a project, one needs to have a project-specific equipment (or know-how, or ability) in his hand. Only oc-casionally does a player have an opportunity to acquire a new equipmentor 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 forboth 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 cheaptalk 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 closingan 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-play communication on equilibrium selection under an evolutionary adjustmentprocess with the following properties: (i) The players adjust the set of ac-cessible actions of the coordination game only occasionally. (ii) The playersfrequently 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 pure strategy Nash equilibria that are Pareto ranked. We show that whether weobtain an efficient-equilibrium-selection result depends on the structure ofthe 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 will label another object as strategy.
a 9, 9 0, 6 b 6, 0 7, 7 a 9, 9 0, 8 b 8, 0 7, 7 A game is said to be self-signalling if a player has a right incentive to revealher 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. Ifshe can successfully convince the column player of her intention of playingb, then the column player's rational reaction is to play b, and the row playerreceives 7. On the other hand, if the row player misleads the column playerto believe she will play a, this leads the column player to play a, which givesthe 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 to play b, then she does not have a right incentive to reveal her intention. Ifshe 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 deceivesthe column player and lets him believe she will play a, then the columnplayer plays a and the row player's payoff will be 8. Therefore this game isnot self-signalling.
For general 2 × 2 symmetric coordination games, if we call the efficient equilibrium 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 underly-ing game is not self-signalling, then both the efficient equilibrium outcomeand the inefficient equilibrium outcome are stable. Therefore an efficient-equilibrium-selection result is obtained if and only if the underlying game 2 For more discussion on the self-signalling condition, see a survey of the cheap talk literature by Farrell and Rabin [6] .
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 payoffsin the efficient equilibrium (a, a) to 50, then this equilibirum becomes riskdominant 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 (ac-tion 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 incum-bent player always receives the inefficient equilibrium payoff. On the otherhand, a mutant player receives the inefficient equilibrium payoff when sheis matched with an incumbent, and receives the efficient equilibrium payoffwhen matched with another mutant. Therefore, the mutants receive a higherpayoff on average and invade the population. The key point here is that themutants can separate themselves away from the incumbents through mes-sages 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 asdescribed 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 fixedtype 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.
as the munants so as to induce the mutants to play action a. Therefore, themutants can never successfully separate themselves out from the incumbentthrough messages. Here, a secret handshake does not work. In fact, theincumbents have such an incentive to pool with the mutants if and only ifthe 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 typesevolves. Second, the behaviors of the players in the cheap-talk game evolve.
Since we assume the behaviors of the players are adjusted much more fre-quently 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 performsin the stable outcomes. We model the evolution of the type distribution inthe way that the type earning a higher payoff in the stable outcomes thrivesbetter. 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 ofevolution of preferences, the players' preferences evolve slowly, while theyadjust their behavior in games taking the current preference as exogenouslyfixed.
The rest of the paper is organized as the following. Section 2 describes the cheap talk game, which is to be repeated. Section 3 defines the types of theplayers and the equilibrium under a fixed type distribution. Section 4 studiesthe evolution of the type distribution. Section 5 considers the evolution ofbehaviors under fixed type distributions. Section 6 discusses how our resultmay be changed if we alter some of our assumptions. Section 7 surveys therelated literature. Section 8 concludes.
The Cheap Talk Game Let G be the base game. We assume G is a 2 × 2 symmetric coordinationgame. The set of pure strategies is {a, b} and πij, i, j = a, b is the payoffwhen a player plays i and the opponent plays j. Thus the payoff matrix isgiven by Figure 3.
a πaa, πaa πab, πba πba, πab πbb, πbb Assume πaa > πba, πbb > πab, and πaa > πbb. By the first two inequalities thegame has two symmetric pure strategy Nash equilibria, namely both playinga 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 strategiesin 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 playerssend a message m ∈ M = {m1, m2} simultaneously. In the second stage, bothplayers play either a or b of the base game simultaneously, having observedthe 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. Thepayoff from the cheap-talk game is determined by the actual action chosen inthe 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 twocomponents. 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 decisionrule is a mapping from the message space to the action space. There are fourpossible (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}.
Types of the Players and Short Run Games The type θ of a player describes which actions of the base game are availablefor 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 avail- able for type a players is Σa = {(m1, fa), (m2, fa)}. Similarly, the set ofbehaviors 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 avail-able 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(θ) = 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 the set 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 exogenouslyfixed (and thus the TPS is fixed) and the players choose their behaviors. Wewill 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. Weassume 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 uniformdistribution. 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 Σθ and y : Θ → ∪θ∈Θ∆Σθ, where yθ ∈ ∆Σθ for all θ. Here yθ(σ) is the probability of playing strategy σwhen the type is θ, and yθ = {yθ(σ)}σ∈Σ .
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 playersplay strategy y and proportion 1 − α of players play strategy y0, then thestrategy profile in which all the players are playing αy + (1 − α)y0 is also aBayesian Nash equilibrium.
Let u(σ, ˜ σ) be the payoff in the cheap talk game to a player when she plays behavior σ = (µ, f ) and the opponent plays ˜ f ). Therefore, u(σ, ˜ σ) = π µ), ˜ f (µ) We assume that a player is randomly matched with another player accordingto 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 v(σ x, y) = u(σ, ˜ θ∈Θ ˜ Notice that the expected payoff to a player depends on her behavior, but noton her type. A behavior σ ∈ Σθ is called a best response for a type θ playeragainst strategy y under the TPS x, if it gives the highest expected payoffamong the behaviors in Σθ. The set of pure best responses to a type θ playeragainst y under the TPS x is denoted by BRθ(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 positiveprobabilities only on the members of BRθ(x, y). We write y0 ∈ BR(x, y) iffor all θ ∈ Θ, y0 ∈ BR θ(x, y). The equilibrium concept of the short run game can be defined as the following.
Definition A strategy y is a Bayesian Nash Equilibrium (BNE) under the type population state (TPS) x if y ∈ BR(x, y). Stability of Type Distributions The Stability Concept Now, we define the stability concept of type population states (TPS). Thestability concept we use here borrows the backbones from the traditional sta-bility concepts in evolutionary game theory. To illustrate the idea, considerthe stability of a TPS where all players are of the same type θ. Suppose thatinitially 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 TPSis 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. Theinitial 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 defini-tion generalizes this idea. This formal definition allows both the incumbentpopulation 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, ¯²), v(σ (1 − ²)x + ²x0, y)yθ(σ) x(θ) v(σ (1 − ²)x + ²x0, y)yθ(σ) x0(θ) for all y such that y is a BNE under (1 − ²)x + ²x0.
Notice the same expression X v(σ (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.
Two remarks must be stated about this definition of stability. First, so far, we are staying away from the issue of equilibrium selection in the shortrun 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 TPSis stable, then we do not need to worry about the equilibium selection inthe 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. Onthe other hand, if we find that a TPS is not stable, we need to be carefulabout the equilibrium selection in the short run game. Instability here meansonly that there exists some equilibrium in which the mutants' average payoffexceeds the incumbents' average payoff. But this equilibrium may be anunreasonable 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 that no 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 acondition requires that no mutant persist in the sense of earning an equal orhigher payoff than the incumbent. Our result does not hold any longer if weemploy such an ESS-like stability concept.
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 allplayers play the same action of the base game, i.e., an outcome correspondingto 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.
Of course, this proposition alone does not tell us the Pareto efficient equi-librium 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. Inthis TPS, the short run game has multiple equilibria, in particular an equi-librium 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. Since a 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 anyequilibrium 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 con- dition, then the Pareto inefficient equilibrium outcome is unstable. The onlycandidate TPSs in which all the players are playing action b are the TPSswhere only type b and type s are present. Because Proposition 4 in the nextsection rules out xs from the candidates, it suffices to show that the TPSwith 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. Lemma1 shows that for such an TPS there exists an equilibrium in which type sreceives strictly higher payoff than type b.
Lemma 1 For all β ∈ (0, 1), there exists a strategy of the short-run game yβ such that yβ is a BNE under xβ and v(σ xβ, yβ)yβ(σ) > 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 equilibriumselection 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 nextsection shows that there indeed exists an equilibrium satisfying the conditionin 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 populationratios 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 strictlyhigher average payoff than type b. This result shows that if the coordina-tion game is not self-signalling, a secret handshake cannot happen in anyequilibrium of the post-entry short run games.
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 equi-librium of the short run game is played, and we did not discuss which equi-librium should be played if the short run game has multiple equilibria. Nowwe explicitly examine this issue by an evolutionary approach.
This section has two goals. First, we show that in the TPS xs, which was shown 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 TPSxβ is unstable in the sense that if a certain kind of mutants enters the popu-lation, then the mutants receive a higher payoff than the incumbents in some equilibrium in the post-entry short run game. In particular, the mutantsreceive a higher payoff than the incumbents in an equilibrium described inLemma 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 stabilityconcepts we use here are cyclically stable set (CSS) proposed by Gilboa andMatsui [7] and equilibrium evolutionarily stable set (EES set) proposed bySwinkels [15]. Since Matsui [12] showed the equivalence of these two concepts,we are essentially working with only one solution concept. However, we usethe names of both solution concepts just to make our argument simple andclear.
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 opportunityto revise her behavior, she can simultaneously choose any message and deci-sion 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 spaceis two. Matsui showed that there is a unique CSS and every strategy distri-bution 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].
Robustness of Proposition 2 Here we show that for all β ∈ (0, 1), there exists a "stable" equilibrium ofthe short run game which satisfies the condition in Lemma 1. We use EES set as our solution concept. Let ∆ denote the strategy space of the short rungame.
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 ∀y0 ∈ ∆,y0 ∈ BR(x, (1 − ²)y + ²y0) implies (1 − ²)y + ²y0 ∈ Y .
Proposition 5 Suppose the base game is self-signalling. Let y∗ and y∗∗ be the strategies in short run games defined below: • y∗(m 1, fa) = y∗ 2, fb) = y∗ 1, fc) = 1.
2, fa) = y∗∗ 1, fb) = y∗∗ 2, fd) = 1.
(i) For all β ∈ (0, 1), {y∗} and {y∗∗} are (singleton) EES sets under theTPS xβ. (ii) Furthermore, for all β ∈ (0, 1), both y∗ and y∗∗ satisfy theinequality in Lemma 1.
Proof See Appendix.
This section discusses the robustness of our result with respect to the assump-tions made in our model and possible extensions. In particular, we considerthe issue of the solution concept and the size of message spaces. Also, wemake an informal discussion for the reverse case, i.e., the case where themessages evolve slowly.
As we mentioned in Section 4.1, our result does not remain true if we usea stronger stability concept which requires that the incumbents receive astrictly higher payoff than the mutants. In particular, Proposition 3 doesnot 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 is an unsatisfactory result beause an accumulation of type s mutants mayincrease 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. Forexample, these costs are the maintenance costs of factories in the example inIntroduction. These costs enter the utility in a lexicographic manner. We saya 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 keepingactions. With these costs, the state xb becomes stable under the strongerstability concept. If a small population of type s mutants enter, then theyreceive the same payoff as the incumbents and incur more fixed costs. Thereaders may feel the lexicographic representation of the fixed costs is tooartificial and unrealistic. We claim it is not. In the real world, very manybut only finite people are interacting each other. A continuous populationmodel 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 thanthe 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 populationmodel 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.
The Size of The Message Space We 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 handshakebecomes easier as the size of the message space becomes larger, because itbecomes easier for the mutants to find a message that is not used by theincumbents. Thus we are looking at the environment where destabilizingthe inefficient equilibrium outcome is the most difficult. Proposition 2 and 4show that even in such an environment, we can still destabilize the inefficientequilibrium. It is natural to guess that the same result can be obtained for the cases with larger message spaces. On the other hand, Proposition 3 maybe regarded as a weak result because it only shows that the secret handshakeis impossible in the most difficult environment. However, this result doesnot depend on the smallness of the message space. We can easily extend theresult to the cases with larger message spaces.
Slow Adjustment of Messages Consider the opposite case where the players change their messages onlyoccasionally. In short run, each player takes his message as given and adjusttheir decision rules. This consideration applies to some biological evolutionissues. Here a message is interpreted as a physical trait of an animal. Aphysical trait is inherited from ancestors and each individual animal takesit as exogenously given. Each individual animal frequently adjust whichaction to play in the coordination game, and the action may depend onthe opponent's appearance, i.e., the message. With this interpretation, it isreasonable to assume it is the message of each individulal player that evolvesslowly, rather than the set of available messages.
Consider the cheap talk game defined in Section 2. There are two types of 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 usingthe decision rule fb, i.e., they always play action b. In this case, the type 2mutants can do better than the incumbents if they adopt fd, i.e., play actionb when observing message m1 and play action a when observing messagem2. After the entry of these mutants, a type 1 incumbent always receivesthe 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 1incumbent has no incentive to change her decision rule if all the other type 1players 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 eventuallydominates the population, and they play the efficient equilibrium. The samelogic as the existing literature works here and the efficient equilibrium isselected no matter whether the game is self-signalling or not. One may worry the mutants cannot separate themselves through messages if both type 1 and2 are initially present and they are playing the inefficient equilibrium. Wecan overcome this problem by just applying the argument of drift in theexisting literature.
Related Literature Our argument that the self-signalling condition is necessary for a communi-cation to help achieving the efficient equilibrium has an analogy with Au-mann's [1] discussion. Aumann raises a question to the old justification forNash equilibrium as "self-enforcing agreements", which claims that a pre-play agreement to play a certain strategy profile will be kept if and only ifit is a Nash equilibrium. Aumann considers the game of Figure 2 and startsfrom assuming that players are cautious so that they are likely to play therisk dominant equilibrium (b, b) without communication. Aumann asks if apre-play agreement to play (a, a) will be kept. Aumann argues that even ifa 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 choosea 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'smodel, one player has a payoff relevant private information. In the cheap-talkgame, the informed player sends a message and then the two players choosean 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) whenthere 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 rungame in our model can be interpreted as an extension of Baliga and Morris'sanalysis 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 action in general how Baliga and Morris's results can be extended to games withtwo-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, es-pecially an arrival of mutants affects only a small fraction of the entirepopulation. Blume proposes a class of population dynamics which permitsimultaneous adjustment of strategies of large fractions of the populationand shows that whether the efficient-equilibrium-selection result is obtaineddepends on the risks of the underlying game and the size of the messagespace. 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 herbehavior, she can freely adopt anything in the strategy space of the cheaptalk game. The self-signalling condition does not distinguish the result inBlume's model.
In many economic problems, the set of available alternatives in game the-oretic situations is determined endogenously. In particular, long term de-cisions such as opening and closing a factory may restrict the flexibility ofshort term decisions such as choosing which product to produce. Thereforeit is worthwhile to analyze an evolutionary model in which the set of avail-able actions is adjusted slowly and the short term adjustments are restrictedby the availability. This paper studied the effect of pre-play communicationon equilibrium selection in coordination games and showed that the existingefficiency result is fragile to the consideration of the difference in the speedof evolution. The incentive of a player to pool with players with differentavailability is the main obstruction in achieving efficiency.
b (action a) but this action is very costly so that action a (action b) is the dominantstrategy.
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θ(σ) = maxv(σ (1 − ²)xs + ²x0,y) for all θ ∈ Θ. Since Σa ⊂ Σs and Σb ⊂ Σs, max v(σ (1 − ²)xs + ²x0, y) ≥ max v(σ (1 − ²)xs + ²x0, y), for θ ∈ {a, b}. Now, v(σ (1 − ²)xs + ²x0, y)yθ(σ) (xs(θ) − x0(θ)) max v(σ (1 − ²)xs + ²x0, y) (xs(θ) − x0(θ)) max v(σ (1 − ²)xs + ²x0, y) − max v(σ (1 − ²)xs + ²x0, y) x0(θ) ≥ 0, which proves the proposition.
Proof of Proposition 2 Lemma 1 For all β ∈ (0, 1), there exists a strategy of the short-run game yβ such that yβ is a BNE under xβ and v(σ xβ, yβ)yβ(σ) > Proof For all β ∈ (0, 1), let a strategy yβ satisfy yβ(m 1, fc) = 1, yβ 1 and yβ(m 2, 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.
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−²)βand This implies that Therefore, xβ is not stable.
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 shortrun 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 a does not receive a higher payoff than type b. A type a player is matched withtype 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 bplayer is matched with another type b and receives a payoff πbb with at leastprobability 1 − η. Therefore, a type b player's average payoff is no less than(1 − η)πbb +ηπba. For η sufficiently small, (1−η)πab +ηπaa < (1−η)πbb +ηπbaholds. 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 equilibirumexists. The equilibrium is denoted by y. First, in this equilibrium the decisionrule 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 with probability 1, then type s and type b receive the same payoff. Therefore, inequilibrium 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 thuswe have yb(m1, fb) = 1. Here, a type s player employing the decisionrule 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 twosub-cases. First, consider the case where yb(m1, fb) ≥ 1. When a type s player with the decision rule fc is matched with a type b player, herexpected payoff is yb(m1, fb)πab + yb(m2, fb)πbb, which is less than orequal to 1(π ab + πbb). Therefore the payoff for a type s player with the decision rule fc is no greater than (1−η)1(π 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 higherpayoff 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) ≥ 1, we can make the same argument by looking at the payoff of a type s player with the decisionrule fd.
We started from the assumption that there exists an equilibrium in whichtype s receives a strictly higher payoff than type b and reached to a con-tradiction for all possible cases. Therefore we can conclude that such anequilibrium does not exist.
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∗}, becausethe 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 y0 ∈ ∆, BRa(xβ, (1 − ²)y∗ + ²y0) = {(m1, fa)}, BRb(xβ, (1 − ²)y∗ + ²y0) = {(m2, fb)}, BRs(xβ, (1 − ²)y∗ + ²y0) = {(m1, fc)}. Hence, for all θ ∈ Θ, y00 ∈ BR = y∗. Therefore, a(xβ , (1 − ²)y∗ + ²y0) implies y00 y0 ∈ BR(xβ, (1 − ²)y∗ + ²y0) implies y0 = y∗, and thus (1 − ²)y + ²y0 ∈ Y .
[1] Aumann, R. (1990). "Nash Equilibria Are Not Self-Enforcing," in Eco- nomic 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.
[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 Equilib- rium Selection," Econometrica, 61, 989-1018.
[5] Ely, J., and Yilankaya, O. (2001). "Nash Equilibrium and the Evolutoin of 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 and Long Run Equilibria in Games," Econometrica, 61, 27-56.
[10] Kim, Y.-G., and Sobel, J. (1995). "An Evolutionary Approach to Pre- Play Communication," Econometrica, 63, 1181-1193.
[11] Matsui, A. (1991). "Cheap Talk and Cooperation in Society," Journal of Economic Theory, 54, 245-258.
[12] Matsui, A. (1992). "Best Response Dynamics and Socially Stable Strate- gies," Journal of Economic Theory, 57, 343-362.
[13] Robson, A. J. (1990). "Efficiency in Evolutionary Games: Darwin, Nash and the Secret Handshake," Journal of Theoretical Biology, 144, 379-396.
[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.
[16] W¨arneryd, 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,

Source: http://www.rieb.kobe-u.ac.jp/academic/ra/dp/English/dp165.pdf