{'fraction_non_alphanumeric': 0.046842635212888374, 'fraction_numerical': 0.011946202531645569, 'mean_word_length': 3.9408691944138448, 'pattern_counts': {'":': 0, '<': 83, '<?xml version=': 0, '>': 103, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 62, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Communication, Renegotiation and Coordination with Private Values (Extended Version)

An equilibrium is communication-proof if it is unaffected by new opportunities to communicate and renegotiate. We characterize the set of equilibria of coordination games with pre-play communication in which players have private preferences over the feasible coordinated outcomes. Communication-proof equilibria provide a narrow selection from the large set of qualitatively diverse Bayesian Nash equilibria in such games. Under a communication-proof equilibrium, players never miscoordinate, play their jointly preferred outcome whenever there is one, and communicate only the ordinal part of their preferences. Moreover, such equilibria are robust to changes in players' beliefs, interim Pareto efficient, and evolutionarily stable.


Introduction
We characterize communication-proof equilibria for a class of coordination games with pre-play cheap-talk communication in which all agents have private information about what action they would prefer to coordinate on. A Bayesian Nash equilibrium is communication-proof if, after the pre-play cheap talk and given the information that this reveals, a new opportunity for additional communication does not allow the players to jointly deviate to a Pareto-improving equilibrium. 1 We are interested in two typical kinds of situations for which communication-proofness is an appropriate solution concept, albeit for different reasons in the two situations. The first kind of situation is one in which agents are sophisticated and keep (strategically) communicating until they reach a mutually beneficial solution. Communication-proofness is defined to capture this idea, similarly to the notions of renegotiation-proofness in contract theory (Hart and Tirole, 1988) or in the repeated games literature (Farrell and Maskin, 1989). As an example, consider a situation of two firms trying to collude by implementing a market-sharing agreement by which one firm sells in certain regions whereas the rival sells in other regions, and each firm has private information about which regions they prefer to serve. The second kind of situation is one in which communication is feasible and in which behavior is governed by a long-run learning (or evolutionary) process. Communication-proofness here corresponds to a requirement of evolutionary stability at an interim level, when agents can experiment with new behavior that is contingent on the use of additional communication (Robson, 1990). As an example consider the problem of two pedestrians suddenly finding themselves face-to-face and trying to get past each other, when they have private information about the direction they want to take after the encounter.
The standard solution concept of Bayesian Nash equilibrium is not helpful in predicting whether players can achieve coordination in such incomplete-information settings, how efficient it is if they do, and how communication is used to achieve it. Coordination games with pre-play communication have a wide range of qualitatively very different equilibria. Among these are babbling equilibria with a high likelihood of miscoordination that are evolutionarily stable in the absence of communication, and equilibria in which agents reveal some information about the intensity of their preferences and yet often miscoordinate.
Casual observation suggests that players manage to coordinate in at least some such situations.
action" interpretation of equilibrium given by Nash (1950), and then taken up more formally in Maynard Smith and Price (1973) who define the notion of evolutionary stability. 5 It is well known that all pure equilibria in coordination games are evolutionarily stable (whereas mixed equilibria are not stable). This literature thus supports the view that while play in the long run will be coordinated, it is not necessarily efficiently coordinated. 6 Another explanation for coordination is that it is achieved through communication, even if it is simply cheap talk as in Crawford and Sobel (1982). Early seminal contributions in this direction are Farrell (1987) and Rabin (1994). Communication alone, however, only adds equilibria: the equilibria of the game without communication "survive" the introduction of communication as babbling equilibria. The problem, therefore, of how play focuses on the coordinated equilibria does not go away, and one can again appeal to one of the above-mentioned criteria to explain why this might happen.
There is a literature that studies the evolutionary outcome of coordination games with cheap talk, initiated by Robson (1990). If play is stuck in an inferior equilibrium, a small group of experimenting agents can recognize each other by means of a "secret handshake" and play Pareto-optimal strategy with each other and the inferior equilibrium strategy with agents who are not part of this group, thereby outperforming the agents outside the group. All the above-mentioned literature (on coordination) focuses on complete-information games.
However, one of the main reasons why people communicate is that they have privately known preferences that they feel useful to share at least partially before finally choosing actions, as seen in the above examples. One of the main stumbling blocks of studying how communication helps achieve coordination in the presence of incomplete information is that it "requires overcoming formidable multiple-equilibrium problems" (Crawford and Haller, 1990, p. 592).
We identify Blume and Sobel's (1995) notion of communication-proof equilibrium, adapted to our two-sided private information setting, as the appropriate extension of the secret-handshake argument to incomplete-information games. With our characterization result we then show that the plausible refinement of communication-proof equilibria removes this multiplicity problem to a large extent, in the sense that communication-proof equilibria, in contrast to Bayesian Nash equilibria, make very similar predictions.
Baseline model and extensions While we take into account incomplete information in the coordination problem, we try to keep the baseline model tractable by simplifying other aspects of the problem. We restrict attention in the baseline model to (incomplete information) two-player 5 See, Weibull (1995) and Sandholm (2010) for a textbook treatment of evolutionary game theory. 6 Kandori et al. (1993) and Young (1993) show that in the very long run and under persistent low-probability errors an evolutionary (learning) process leads to the risk-dominant, not necessarily Pareto-dominant, pure strategy equilibrium in two-by-two coordination games. two-action (coded as left and right) coordination problems, in which every type has a coordination concern. Different types only differ in how much they prefer coordination on one action over the other one. Players can communicate only once before the game is played. Sections 2.1 and 8 provide a series of extensions and robustness checks of our baseline model. First, we show that all our results hold for any length of pre-play communication. Second, we show that all our results hold for all two by two incomplete information coordination games, in which for all feasible types the preferred coordinated action is also the risk-dominant action (i.e., the best reply against an opponent who plays each action uniformly; see Harsanyi and Selten, 1988). Example 2 demonstrates that without this assumption there can be additionalcommunication-proof equilibria, in which players fail to coordinate after some messages. Next, we extend our key results to general (possibly asymmetric) coordination games, which might involve more than two players and more than two actions. Finally, we study a variant of our baseline model in which a few types have dominant actions. We show that in this setup, there is a unique communication-proof equilibrium strategy among the strategies satisfying our three key properties (the identity of this unique strategy depends on the distribution of types with dominant actions).
Structure Section 2 presents our baseline model. Section 3 defines Bayesian Nash equilibria and the three key properties that communication-proof equilibria have. Section 4 defines the concept of communication-proofness appropriately adapted to our incomplete-information strategic setting. Section 5 presents the main result and a sketch of its proof. Section 6 discusses the efficiency properties of communication-proof equilibria. Section 7 discusses additional notions of evolutionary stability beyond the secret-handshake stability implied by communication-proofness. Section 8 provides a series of robustness checks and extensions. Section 9 concludes. The formal proofs are presented in the online appendices.
Payoff matrix For any realized pair of types, u and v, the players play a coordination game given by the following payoff matrix, where the first entry is the payoff of the player of type u (choosing row) and the second entry is the payoff of the player of type v (choosing column).
We call this game the coordination game without communication and denote it by Γ.

Interpretation of the model and the motivating examples
In the example of two firms trying to collude by market-sharing, choosing the same action corresponds to dividing the market such that each firm is a monopolist in one of the two regions, and choosing different actions corresponds to the firms competing in the same region, which yields a low profit normalized to zero. A firm's type u corresponds to how profitable it is for the firm to be a monopolist in one region relative to being one in the other region. In the second motivating example of pedestrians suddenly finding themselves face to face and trying to get past each other, each action corresponds to the direction in which the pedestrians turn to avoid bumping into each other. When both pedestrians choose the same side (say, each pedestrian the three key properties is strongly communication-proof. Theorem 2 shows that the "3 ⇒ 1" part of the theorem holds as well under the restriction of "unambiguous coordination preferences," which requires that for all feasible types the preferred coordinated action also be the risk-dominant action (i.e., the best reply against an opponent who plays each action uniformly; see Harsanyi and Selten, 1988). Example 2 in Appendix E.2 demonstrates that without this restriction (i.e., with stag-huntlike types for which the payoff-dominant action does not coincide with the risk-dominant action), equilibria with miscoordination can be communication-proof.
Asymmetric coordination game and asymmetric equilibria The baseline model assumes that both players' types have the same distribution F, and our solution concept focuses on symmetric equilibria. This is done to simplify the notation, and to ease the analysis of evolutionary stability in Section 7 (where some of the relevant solution concepts are defined only for symmetric games). Appendix E.4 shows that all our results hold in asymmetric coordination games in which the distributions of the types of the two players' positions may differ, or when allowing asymmetric equilibria of symmetric coordination games.
More than two players Our baseline model has only two players. In Appendix E.3 we show that our results hold for any number of n ≥ 2 players, under the assumption that the payoff of each player of type u is equal to u if all players play R, it is equal to 1 − u if all players play L, and it is equal to zero if all players do not play the same action. The interesting case in which players can get positive payoffs by coordination of a subset of the players on the same action is left for future research.
General action functions The baseline model restricts the action functions to the set of cutoff functions of the form ξ : M × M → U . In principle, we should allow more general action functions ξ : U ×M ×M → △{L, R}, which specify the probability that an agent chooses L as a function of the observed message profile and the agent's type. It is simple to see, however, and proven in Lemma 1 in Appendix A.1, that any "generalized" strategy is dominated by a strategy that uses a cutoff action function in the second stage. The intuition, is that following the observation of any pair of messages, lower types always gain more (less) than higher types from choosing L (R). Thus, the restriction to cutoff action functions is without loss of generality. Other extensions affect some (but not all) of our results: allowing more than two actions, and allowing extreme types with dominant actions. We postpone the discussion of these extensions to Section 8

Equilibrium Strategies and Three Key Properties
We here define the standard notion of (Bayesian Nash) equilibrium strategies, present the three key properties that communication-proof equilibria turn out to have, and present examples of equilibria in the coordination game with communication with and without these properties. These equilibria are illustrated in Figure 1 in the end of this section.
Given a strategy profile (σ , σ ′ ) and a type profile u, v ∈ U , let π u,v (σ , σ ′ ) denote the payoff of a player of type u who follows strategy σ and faces an opponent of type v who follows strategy σ ′ . Formally, for σ = (µ, ξ ) and σ ′ = (µ ′ , ξ ′ ), where 1 {x} is the indicator function equal to 1 if statement x is true and zero otherwise. Let denote the expected interim payoff of a player of type u who follows strategy σ and faces an opponent with a random type who follows strategy σ ′ . Finally, let, π σ , σ ′ = E u π u σ , σ ′ ≡ 1 u=0 π u σ , σ ′ f (u) du denote the ex-ante expected payoff of an agent who uses strategy σ against strategy σ ′ .
We call a strategy coordinated if ξ (m, m ′ ) = ξ (m ′ , m) ∈ {L, R} for any pair of messages m, m ′ ∈ supp(μ). A coordinated strategy never leads to miscoordination after any (used) message pair.
For any message m ∈ M, define the expected probability of a player's opponent playing L conditional on the player sending message m and the opponent following strategy σ = (µ, ξ ) ∈ Σ, as We say that strategy σ has binary communication if there are two numbers 0 ≤ β σ ≤ β σ ≤ 1 such that for all messages m ∈ M we have β σ (m) ∈ [β σ , β σ ], for all messages m ∈ M such that there is a type u < 1 /2 with µ u (m) > 0 we have β σ (m) = β σ , and for all messages m ∈ M such that there is a type u > 1 /2 with µ u (m) > 0 we have β σ (m) = β σ . That is, binary communication implies that players (essentially) use just two kinds of messages: any message sent by types u < 0.5 induces the same consequence of maximizing the probability of the opponent playing L, and any message sent by types u > 0.5 induces the opposite consequence of maximizing the opponent's probability of playing R. Note that, as defined here, a strategy with no communication also has binary communication (in which the player's message does not affect the probability of the partner playing L).
In Appendix B we show that no single one of these three properties is implied by the other two. Clearly, a strategy that has binary communication and is coordinated must be an equilibrium. In Appendix B we also show that no combination of any two of these three properties implies that a strategy is an equilibrium.
Left tendency α σ Consider a strategy that satisfies the above three properties. Coordination and mutual-preference consistency jointly determine the behavior of agents with the same ordinal preferences (i.e., when both types are below 1 /2, or both above 1 /2). The property of binary communication, then, implies that the probability with which the players coordinate on L, conditional on having different ordinal preferences (i.e., conditional on one player having type u < 1 /2 and the other player having type v > 1 /2), is independent on the message sent by the player. We denote this probability by α σ , and refer to it as the left tendency of the strategy. We can express β and β σ as follows: The first equality (β σ = F( 1 /2)α σ ) is implied by the fact that when any type u > 1 /2 sends a message expressing her preference for coordination on R, the players coordinate on L only if the opponent's preferred outcome is L (which happens with a probability of F( 1 /2)), and they then coordinate on L with a probability of α σ . The second equality (β σ = F( 1 /2) + (1 − F( 1 /2)) α σ ) is implied by the fact that when any type u < 1 /2 sends a message expressing her preference for coordination on L, the players coordinate on L with probability one if the opponent's preferred outcome is L, and they coordinate on L with a probability of α σ if the opponent's preferred action is R.
Examples of equilibria satisfying all properties The following strategies, denoted by σ L , σ R , and σ C , are prime examples (that play a special role in later sections) of strategies that are all mutualpreference consistent, coordinated, and have binary communication.
The strategies σ L and σ R are given by the pairs (µ * , ξ L ) and (µ * , ξ R ), respectively. The message function µ * has the property that there are messages m L , m R ∈ M such that message m L indicates a preference for L and m R a preference for R, and the action functions ξ L and ξ R are defined as follows: This means that the "fallback norm" of σ L (which is applied when the agents have different preferred outcomes) is to coordinate on L, while that of σ R is to coordinate on R. In other words the left tendency of σ L is one and the left tendency of σ R is zero.
Strategy σ C = (µ C , ξ C ) has the "fallback norm" of using a joint lottery to choose the coordinated outcome. Each agent simultaneously sends a random bit and the coordinated outcome depends on whether the random bits are equal or not.
We denote four distinct messages by m L,0 , m L,1 , m R,0 , m R,1 ∈ M, where we interpret the first subscript (R or L) as the agent's preferred direction, and the second subscript (0 or 1) as a random binary number chosen with probability 1 /2 each by the agent. Formally, the message function µ C is defined as follows: where αm ⊕ (1 − α)m ′ is a lottery with a probability of α on message m and 1 − α on message m ′ .
In the second stage, if both agents share the same preferred outcome they play it. Otherwise, they coordinate on L if their random numbers differ, and coordinate on R otherwise. Formally: The outcome of σ C can also be implemented by a fair joint lottery that determines which of the two players determines the coordinated action used by both players. This alternative implementation yields exactly the same outcome: if both agents share the same preferred outcome they play it, and conditional on the agents disagreeing on the preferred outcome, they coordinate on each action with equal probability.
One-dimensional set of strategies satisfying the properties The set of strategies with the above three properties (coordination, mutual-preference consistency, and binary communication) is essentially one-dimensional because the left tendency α σ ∈ [0, 1] of such a strategy σ describes all payoff-relevant aspects. Two strategies with the same left tendency can only differ in the way in which the players implement the joint lottery when they have different preferred outcomes, but these implementation differences are nonessential, as the probability of the joint lottery inducing the players to coordinate on L remains the same.
Any left-tendency α σ ∈ [0, 1], which is a rational number, can be implemented by a jointly controlled lottery in which the players send random messages in such a way that they are indifferent between all messages, and the joint distribution of random messages induces α σ (Aumann and Maschler, 1968; see also Heller, 2010, for a recent implementation, which is robust to joint deviations). This is demonstrated for α σ = 1 /2 in the strategy σ C presented above.
Note that of all the strategies that satisfy the three properties, strategies σ L and σ R are the simplest in terms of the number of "bits" needed to implement the message function. Strategy σ C is in a certain sense the fairest: conditional on a coordination conflict, i.e., conditional on one agent having a type between 0 and 1 /2 and the other agent having a type between 1 /2 and 1, both agents expect the same payoff. By contrast, strategy σ L favors types below 1 /2, and strategy σ R favors types above 1 /2.
Examples of equilibria not satisfying some of the properties The coordination game with communication Γ, M admits many more equilibria that satisfy only some or even none of the three properties defined above.
First, the game admits babbling equilibria, which do not satisfy mutual-preference consistency. Each babbling equilibrium can be identified with an x ∈ [0, 1] that satisfies F(x) = x, where agents choose L iff their type is below x. The case of x = 1 (resp., x = 0) corresponds to a uniform norm of always playing L (resp., R). A case of x ∈ (0, 1) corresponds to an inefficient babbling equilibria, in which agents sometimes miscoordinate.
The game also admits equilibria in which agents reveal some information about the intensity of their preferences (i.e., some information beyond only stating whether u ≤ 1 /2 or u > 1 /2). One simple example of such an equilibrium for a specific distribution F is Example 1 in Section 6. It is not completely straightforward to construct such examples for all possible distributions F if we consider only a single round of communication as we do in the main body of this paper. In Section 8, however, we show that our main results continue to hold if we allow multiple rounds of communication. In the case of multiple rounds of communication it is relatively straightforward to construct examples of equilibria that do not have binary communication and that, therefore, reveal some cardinal content of the players' preferences. For simplicity, assume that the distribution F is for all x ∈ [0, 1]. In particular, we have that F( 1 /2) = 1 /2.
The equilibrium σ ex is such that there is an x satisfying 0 < x < 1 /2 such that in the first round of communication players indicate whether their preferences are "extreme" (i.e., u ≤ x or u > 1 − x) or "moderately left" (x < u ≤ 1 /2) or "moderately right" ( 1 /2 < u ≤ 1 − x). In the second round individuals only reveal additional information if in the first round one sent the extreme message and the other a moderate message, in which case the extreme type now reveals which side she prefers (u ≤ 1 /2 or u > 1 /2). In this case, joint play is dictated by the extreme type's preferences. If both players sent the extreme message in the first round, then there is no more communication and both types follow their inclination (play L if u ≤ 1 /2 and R otherwise). This leads to miscoordination with a conditional probability of a half.
Any two moderate types essentially play the coordinated strategy σ C ; that is if they have the same preferred outcome, then they play it, and, otherwise, they use communication to induce a joint fair lottery over both playing L and both playing R. In Appendix C we formally present this strategy and show that for any distribution F there is an x ∈ (0, 1 /2) such that this strategy is a Nash equilibrium of the coordination game with two rounds of communication.
Illustration of equilibria and the first-best outcome Figure 1 illustrates five of the equilibria described above: the equilibria that satisfy the three key properties: σ L , σ R , and σ C , the babbling equilibrium of always playing R, and the equilibrium σ ex , which satisfies none of the three key properties. It also depicts (in the bottom right panel) the first-best outcome in which the players reveal their types and then coordinate on the action that maximizes the sum of payoffs (i.e., the players coordinate on L if u +v ≤ 1 and they coordinate on R if u +v > 1). This is not an equilibrium: each player has an incentive to present a more extreme type than her real type (e.g., all types u > 1 /2 would claim to have type 1).

Definition of Communication-Proofness
For any given strategy in Σ employed by both players in the game Γ, M , communication and knowledge of this strategy lead to updated and possibly, different and asymmetric information about the two agents' types. Suppose that the updated distributions of types are given by some distribution functions G and H. The two agents then face a (possibly asymmetric) game of coordination without communication, which we shall denote by Γ(G, H). Note that the original game (without communication) Γ is then given by Γ(F, F).
Let f m be the type density conditional on the agent following a given strategy in the game Γ, M and sending a message 8 m ∈ supp(μ), i.e., Figure 1: Six example strategies. The axis represent the two players' types u and v. Letters L, R, C, and M represent coordination on L, coordination on R, coordination on a random action, and miscoordination (both players playing their preferred action), respectively. and let F m be the cumulative distribution function associated with density f m . We allow players to renegotiate after communication. Renegotiating players can use a new round of communication. Given a strategy of the game Γ, M employed by both players, we denote the induced renegotiation game after a positive probability message pair m, m ′ ∈ M by Γ(F m , F m ′ ), M .
Let π H u (σ , σ ′ ) denote the expected payoff for the player using strategy σ of type u given strategy profile (σ , σ ′ ) in game Γ(G, H), M : and similarly let π G v (σ , σ ′ ) denote the expected payoff for the player using strategy σ ′ of type v in Γ(G, H), M : Let E (G, H) be the set of all (possibly asymmetric) equilibria of the coordination game with communication 9 Γ(G, H), M . Let π (m,m ′ ),H m ′ u (σ , σ ′ ) (resp., π (m,m ′ ),G m v (σ , σ ′ )) denote the post-communication 9 As the support of G and H may generally be a strict subset of [0, 1], there may be many equivalent strategies (and, payoff for the player using strategy σ (resp., σ ′ ) of a type u (resp., v) given (σ = (µ, ξ ), σ ′ = (µ ′ , ξ ′ )) in game Γ(G, H), M conditional on message pair m ∈ supp(σ ), m ′ ∈ supp(σ ′ ) : Following Blume and Sobel (1995), we say that a strategy profile (τ, τ ′ ) CP trumps another strategy profile (σ , σ ′ ) if there is a possible pair of messages such that, given the information induced by the message pair, the profile (τ, τ ′ ), using another round of communication, yields a Paretoimprovement over the post-communication expected payoffs induced by (σ , σ ′ ). Formally: We say that a strategy σ is strongly communication-proof if for any possible message profile, there does not exist a new equilibrium, which might require another round of communication, that Pareto-dominates the post-communication payoff of σ . The weaker notion of weak communicationproofness allows such a Pareto-improving equilibrium to exist as long as this latter equilibrium is not stable in the sense that it is CP trumped by another equilibrium. Formally: Definition 2. An equilibrium strategy σ ∈ E is strongly communication-proof if it is not CP trumped with respect to (F, F) by any strategy profile.
Observe that in games with complete information, our two notions coincide, and they are both equivalent to the (nonempty) Pareto frontier of the set of Nash equilibria, i.e., to the subset of Nash thus, many equivalent equilibria). equilibria that are not Pareto-dominated by other Nash equilibria. Blume and Sobel's (1995) notion of communication-proofness lies in between our two notions. Blume and Sobel's notion is defined in the spirit of von Neumann and Morgenstern's (1944) set stability: the set of equilibria is divided into stable and unstable equilibria; a strategy profile is communication-proofà la Blume and Sobel if it is not CP trumped by a stable equilibrium; and the set of stable equilibria is defined consistently (any stable equilibrium is only CP trumped by unstable equilibria, and any unstable equilibrium is CP trumped by some stable equilibrium). Blume and Sobel show that any sender-receiver game (in which only one player has private information and her set of actions is a singleton) admits a communication-proof equilibrium.

Evolutionary Interpretation of Communication-Proofness
The notion of robustness to a secret handshake (Robson, 1990) has been applied to games with complete information (see, e.g., Matsui, 1991;Wärneryd, 1991;Kim and Sobel, 1995;Santos et al., 2011). The notion relies on the argument that if play is stuck in an inferior equilibrium σ , a small group of experimenting agents can recognize each other by means of a "secret handshake" and play a Pareto-improving equilibrium σ ′ with each other and play the inferior equilibrium σ with agents who are not part of this group, thereby outperforming the agents outside the group.
To the best of our knowledge the notion has not been applied to games with private types. Arguably, there are two main ways to adapt robustness to secret handshakes to a setup with private types: ex-ante adaptation and interim adaptation. Ex-ante adaptation assumes that if there exists an alternative equilibrium σ ′ with a higher ex-ante payoff than the current equilibrium σ , then agents would use a secret handshake to play σ ′ among themselves. We think that ex-ante adaptation is problematic in a setup, which is common in applications, in which agents can only use the secret handshake after they know their type. It seems unlikely that a type would agree to use a secret handshake that decreases her payoff due to its ex-ante advantage.
In such setups, it seems reasonable to use an interim adaptation, which allows only secret handshakes that benefit all types. This is exactly what is captured by the definition of strong communication-proofness. One could adapt this interim notion of secret handshake, by (1) only allowing "stable" secret handshake that are robust to additional deviations (which is captured by the notion of weak communication-proofness), or (2) allowing agents to use secret handshake also before communicating (See Remark 1). The results of Sections 5-6 show that all these variants of interim robustness to secret handshake lead to the same characterization of robust strategies (namely, to our characterization of coalition-proof equilibria.)

Main Result
Our main result shows that both of our notions of communication-proofness coincide in our setup, and they are characterized by satisfying the three key properties of Section 3.
Theorem 1. Let σ be a strategy of the game with communication Γ, M . The following three statements are equivalent: 1. σ is mutual-preference consistent, coordinated, and has binary communication.
2. σ is a strongly communication-proof equilibrium strategy.
3. σ is a weakly communication-proof equilibrium strategy.
Sketch of proof. The proof that "1" implies "2" is fairly straightforward (and is proven in Appendix A.2). The proof implies, in particular, that σ L , σ R , and σ C are not CP trumped by any other strategy profiles. It is immediate that "2" implies "3." We here provide a sketch of the proof that "3" implies "1." The proof in Appendix A.2 is split into three lemmas, each showing that one of the three properties must hold.
Lemma 2 proves that a weakly communication-proof equilibrium strategy must be coordinated: if play after any message pair is not coordinated then it is CP trumped in the renegotiation game by either σ L , σ R , or σ C . To see this, suppose first that both players use thresholds below 1 /2. Then this strategy is Pareto-dominated by σ R as types above 1 /2 gain because σ R induces their first-best outcome, and types below 1 /2 gain because σ R yields a higher coordination probability and a higher probability of the opponent playing this type's preferred action L. Analogously, an equilibrium in which both players use thresholds above 1 /2 is Pareto-dominated by σ L . Suppose, finally, that player one uses threshold x < 1 /2, while player two uses threshold x ′ > 1 /2. Observe that x < 1 /2 (resp., x ′ > 1 /2) can be an equilibrium threshold only if player two (resp., player one) plays L with an average probability of less (resp., more) than 1 /2. This, implies that players in these equilibria coordinate with a probability of at most 1 /2, and one can show that such a low coordination probability implies that these equilibria are Pareto-dominated by σ C .
Next, we show in Lemma 3 that a weakly communication-proof equilibrium strategy must have binary communication. The reason for this is that if a strategy is coordinated, then different messages can only lead to different ex-ante probabilities of coordination on L (and R). Thus, any type who favors L, i.e., any type u < 1 /2, will choose a message to maximize this probability, while any type u > 1 /2 will choose a message to minimize this probability. Thus, essentially only two kinds of messages are used in a coordinated equilibrium strategy.
Finally, we show in Lemma 4 that a weakly communication-proof equilibrium strategy must be mutual-preference consistent. Given that it is coordinated, we know that any message pair will lead to either coordination on L or on R. If it is not mutual-preference consistent then, without loss of generality, there are two types u, u ′ < 1 /2 that, with positive probability, send a message pair (m, m ′ ) that leads them to coordinate on R. But then all types who send this message pair would be weakly better off (and some strictly better off) if instead of coordinating on R they use strategy σ R , which would allow them to coordinate on L if and only if both types are below 1 /2.
As the two notions of communication-proofness coincide in our setup, we henceforth omit the word "weakly"/ "strongly" and write communication-proof equilibrium strategy to describe either of our (equivalent) solution concepts. Note that the set of communication-proof equilibria is completely independent of the distribution F (i.e., for any two distributions of types F and F ′ , strategy σ is a communication-proof equilibrium in Γ(F) iff it is is communication-proof Γ(F ′ ).) It is not difficult to show that this implies that any communication-proof equilibrium strategy remains communication-proof even in setups in which the distributions of types are correlated, and in setups in which different types have different beliefs about the opponent's type.

On Efficiency
In this section we investigate the efficiency properties of communication-proof equilibria. We first provide an example of an equilibrium with high ex-ante payoffs that is not, however, communicationproof. We then show that all communication-proof equilibria, while not necessarily ex-ante payoff optimal, are at least interim Pareto efficient. Finally, we show that at least one of the equilibria, σ L and σ R , provides the highest ex-ante payoff of all the coordinated equilibria, and that any equilibrium without communication is Pareto-dominated by either one of these extreme communication-proof equilibria or by the action-symmetric communication-proof equilibrium σ C .
High payoff of non-coordinated equilibria Equilibria with miscoordination (which cannot be communication-proof due to Theorem 1) may induce agents to credibly reveal some cardinal information about their type. This can happen if there is a message that induces a higher probability of coordinating on the agent's preferred outcome but also a higher probability of miscoordination compared with some other available message. Such a message can then be chosen by extreme types with u far from 1 /2, while moderate types with u closer to 1 /2 choose the other message. Such equilibria with miscoordination may induce a higher ex-ante payoff, if the benefit from signaling the extremeness of the type outweighs the loss due to miscoordination. Consider the following example.
Example 1. For simplicity we let the distribution of types F be discrete with four atoms 1 /10 + ε, 1 /2 − ε, 1 /2 + ε, 9 /10 − ε, with a probability of 1 /4 for each atom and ε > 0 sufficiently small. 11 The game admits three babbling equilibria: always coordinating on L, always coordinating on R, both with an ex-ante payoff of 1 /2, and playing L if and only if the type is less than 1 /2 with an ex-ante payoff of 7 /20 < 1 /2 for all ε sufficiently small. Theorem 1 (together with the symmetry of the distribution F) implies that with communication, any communication-proof equilibrium strategy (in particular σ L or σ R ) induces the same expected ex-ante payoff of 3 /5 > 1 /2 for all ε sufficiently small.
This game also has a (non-communication-proof) equilibrium strategy with miscoordination that yields a higher ex-ante payoff than the communication-proof payoff of 3 /5, provided that the message set M has sufficiently many elements. To simplify the presentation we here allow the players to use public correlation devices to determine their joint play after sending messages, which can be approximately implemented by a sufficiently large message set (à la Aumann and Maschler, 1968; see the similar construction in Case (II) of the proof of Proposition 9 in Appendix E.7.3). Let m L , m l , m r , m R ∈ M and consider strategy σ = (µ, ξ ) as follows. Let µ( 1 /10 + ε) = m L , µ( 1 /2 − ε) = m l , µ( 1 /2 + ε) = m r , and µ( 9 /10 − ε) = m R , and let ξ (m a , be a joint lottery to coordinate on L or R with probability 1 /2 each, and, finally, let ξ (m L , m R ) = ξ (m R , m L ) be a joint lottery to coordinate on L or R with probability 3 /10 each, and to play the inefficient mixed equilibrium (in which each type plays her preferred outcome with probability 9 /10 − ε) with probability 4 /10. It is straightforward to verify that for, say ε = 1 /100, this strategy is indeed an equilibrium strategy with an ex-ante payoff of around 0.627, which is higher than the ex-ante payoff of 3 /5 of all the communication-proof equilibria. This equilibrium strategy is not coordinated (nor does it satisfy the other two properties of mutual-preference consistency and binary communication) and hence, by Theorem 1, it is not communication-proof.
Interim (pre-communication) Pareto optimality An (ex-ante symmetric) social choice function is a function φ : [0, 1] 2 → ∆ {L, R} 2 assigning to each pair of types a possibly correlated profile We interpret φ u,v as the correlated action profile played by the two players when a player of type u interacts with a player of type v. Let Φ be the set of all such functions.
Any strategy of any coordination game with communication induces a social choice function in Φ, but not all social choice functions in Φ can be generated by a strategy of a given coordination game with communication. One can interpret Φ as the set of outcomes that can be implemented by a designer who perfectly observes the types of both players and, can force the players to play arbitrarily.
continuum of nearby types. 12 We restrict attention to symmetric social choice functions in order to maintain our focus on symmetric equilibria, and in order to allow us to use a simpler notation without player subscripts. Proposition 1 below, however, also holds even if we allow asymmetric social choice functions.
For each type u ∈ [0, 1], let π u (φ ) denote the expected payoff of a player of type u under social A strategy is interim Pareto-dominated if there is a social choice function that is weakly better for all types, and strictly better for some types.
for each type u ∈ [0, 1], with a strict inequality for a positive measure set of types.
A strategy σ ∈ Σ is interim Pareto optimal if it is not interim Pareto-dominated by any φ ∈ Φ. Note that our requirement of Pareto optimality is strong because we allow the designer to perfectly observe the players' types, and to enforce non-Nash play on the players.
Our next result shows that all communication-proof equilibria satisfy our strong requirement of interim Pareto optimality. That is, even a designer with perfect ability to observe the players' types and to enforce any behavior cannot achieve a Pareto improvement with respect to any communication-proof equilibrium strategy. 13

Proposition 1. Every communication-proof equilibrium strategy of a coordination game with communication is interim Pareto optimal.
Sketch of proof; see Appendix A.3 for the formal proof. Recall that by Theorem 1 and the discussion on the one-dimensional set of strategies in Section 3, any communication-proof equilibrium strategy σ is characterized by its left tendency α σ . In order for a social choice function φ to improve the payoff of any type u < 1 /2 (resp., u > 1 /2) relative to the payoff induced by σ , it must be that φ induces any u < 1 /2 (resp., u > 1 /2) to coordinate on L with probability larger (resp., smaller) than α σ . This implies that the probability of two players coordinating on L, conditional on the players having different preferred outcomes, must be larger (resp., smaller) than α σ . However, these two requirements contradict each other.
Earlier we have given an example of an equilibrium strategy that provides a higher ex-ante payoff than any communication-proof equilibrium. This strategy involved a certain degree of miscoordination. In the following proposition we show that any equilibrium without miscoordination, i.e., any coordinated equilibrium, must provide an ex-ante expected payoff that is less than or equal to the maximal ex-ante payoff of the two "extreme" communication-proof strategies σ L and σ R .
Proposition 2. Let σ ∈ E be a coordinated equilibrium strategy. Then 13 As discussed at the end of Appendix E.4, the result that any communication-proof equilibrium is interim Paretooptimal holds also for asymmetric equilibria. Moreover, two of these asymmetric communication-proof equilibria are also ex-ante Pareto efficient: the equilibrium that always chooses the action preferred by Player 1, and the analogous equilibrium that always chooses the action preferred by Player 2.
Sketch of proof; see Appendix A.3 for the formal proof. Let α σ be the probability of two players who each follow σ to coordinate on L, conditional on the players having different preferred outcomes. It is easy to see that σ is dominated by the communication-proof equilibrium strategy with the same left tendency α σ , and that the payoff of the latter strategy is a convex combination of the payoffs of σ L and σ R , which implies that π Remark 1. One could refine the notion of communication-proofness to allow agents to renegotiate to a Pareto-improving equilibrium also in earlier stages (à la Benoit and Krishna, 1993): in the interim stage before observing the realized messages induced by the original equilibrium, and in the exante stage before each agent observes her own type. Proposition 1 implies that allowing agents to renegotiate also in the interim stage does not change the set of communication-proof equilibria. Proposition 2 implies that if π (σ L , σ L ) = π (σ R , σ R ) then allowing agents to renegotiate also in the ex-ante stage yields a unique "all-stage" communication-proof equilibrium, which is either σ L or σ R (while the set of communication-proof equilibria is not affected by introducing ex-ante renegotiation if π (σ L , σ L ) = π (σ R , σ R )).
Next, we show that σ L or σ R provides a strictly higher ex-ante expected payoff than any equilibrium of the game without communication (and therefore than any babbling equilibrium of the game with communication). Recall from Remark 2 and the text preceding it that in the coordination game without communication any equilibrium is characterized by a cutoff value x ∈ [0, 1] such that x = F(x) with the interpretation that types u ≤ x play L and types u > x play R.
Let π u (x, x ′ ) denote the payoff of an agent with type u who follows a strategy with cutoff x and faces a partner of unknown type who follows a strategy with cutoff x ′ : be the ex-ante expected payoff of an agent who follows x and faces a partner who follows x ′ . Next we show that any (possibly asymmetric) equilibrium in the game without communication is Pareto-dominated by either σ L , σ R , or σ C .
Moreover, all the inequalities are strict for almost all types.
Corollary 1 is immediately implied by Lemma 2 in Appendix A.2, and the sketch of proof of the lemma is presented as part of the sketch of the proof of Theorem 1.

Evolutionary Stability
A common interpretation of a Nash equilibrium is a convention that is reached as a result of a process of social learning when similar games are repeatedly played within a large population. This interpretation seems very apt, for instance, if we think of our motivating example of how pedestrians avoid bumping into each other. Specifically, consider a population in which a pair of agents from a large population are occasionally randomly matched and play the coordination game with communication Γ, M . The agents can observe past behavior of other agents who played similar games in the past. It seems plausible that the aggregate behavior of the population would gradually converge into a self-enforcing convention, which is a symmetric Nash equilibrium of Γ, M (see the "mass action" by Nash (1950); and see Weibull (1995) and Sandholm (2010) for a textbook introduction).
We have argued that communication-proofness is a necessary condition of evolutionary stability by capturing the idea of stability with respect to secret-handshake mutations as in Robson (1990). In this section we report results from Appendix D in which we investigate the evolutionary stability properties of both σ L and σ R (the results can be extended to all communication-proof strategies).
In Appendix D.1 we show that strategies σ L and σ R are neutrally stable strategies (NSS) in the sense of Maynard Smith and Price (1973), and evolutionarily stable strategies (ESS) if |M| = 2. This implies that σ L and σ R are robust to the presence of a small proportion of experimenting agents who behave differently than the rest of the population.
We are not quite satisfied with this result for three reasons. First, neutral stability is not the strongest form of evolutionary stability, although in games with cheap talk it is typically the strongest form of stability one can expect owing to the freedom that unused messages provide mutants; see, e.g., Banerjee and Weibull (2000). 14 Second, our game, owing to the incomplete information modeled here as a continuum variable, has a continuum of strategies, especially in the action phase after messages are observed. But with a continuum of strategies the notion of even an ESS is not sufficient to imply local convergence to the equilibrium from nearby states. The reason for this, see e.g., Oechssler and Riedel (2002), is that ESS for continuum models considers only the possibly large strategy deviation of a small proportion of individuals and not the small strategy deviation of possibly a large proportion of individuals. Lastly, our cheap-talk game is a two-stage game and, hence, an extensive-form game. It is well known that extensive-form games do not admit ESSs of the entire game (unless they are strict equilibria; see Selten, 1980), and hence it seems reasonable to explore the stability of equilibrium behavior in each stage separately.
To address these issues we investigate two additional evolutionary stability properties. We inves-tigate the evolutionary stability in each induced game that is on the equilibrium path. 15 Evolution will not necessarily place huge restrictions on play in unreached induced games (see, e.g., Nachbar, 1990;Gale et al., 1995), but should do so for induced games reached with positive probability. To address this, we study the evolutionary stability properties of strategies σ L and σ R at the message level (taking as given the action functions in the second stage), and at the action level (after messages that are observed with positive probability). In Appendix D.2 we show that, when the action is fixed to be either ξ L or ξ R , the message function µ * used by σ L and σ R is weakly dominant. This is a substantially stronger property than the message function being an NSS. 16 In Appendix D.3 we investigate the evolutionary stability properties of the action choice induced by σ L and σ R after the players observe the message pair. As choosing an action as a function of a player's type is equivalent to choosing a cutoff from a continuum (the unit interval), we employ a stability concept designed for such cases. The issue is further complicated by the fact that, owing to the asymmetry after unequal messages, we need to employ a multidimensional stability concept. The literature provides one in the form of a neighborhood invader strategy developed for the double-population case by Cressman (2010), building on earlier work by Eshel and Motro (1981) and Apaloo (1997), among others. We show that the action choice induced by σ L and σ R indeed constitutes a neighborhood invader strategy after each pair of possible messages.
Remark 2 (Stability of inefficient equilibria without communication). Our analysis shows that in our setup with communication evolutionary stability lead to efficient outcome. This is not true without communication. A plausible equilibrium refinement in setups without communication is robustness to small perturbations in the behavior of the population (e.g., requiring Lyapunov stability of the best-reply dynamics, or continuous stability à la Eshel, 1983). Adapting the analysis of Sandholm (2007) to the current setup implies that an equilibrium is robust in this sense if and only if the density of the distribution of types at the relevant threshold x (with x = F(x)) is less than one. In particular, if the distribution of types satisfies f (0) , f (1) > 1, then there exists x ∈ (0, 1) satisfying x = F (x) and f (x) < 1. The corresponding equilibrium, which entails inefficient miscoordination, is then robust to small perturbations. Thus, coordination games without communication are likely to induce substantial miscoordination if the density of extreme types is high (i.e., if f (0) , f (1) > 1).

Extensions
Next, we present informally two extensions that affect some (but not all) of our results.
Coordination games with more than 2 actions In Appendix E.5 we analyze coordination games with more than two actions. In this setup we are able to prove somewhat weaker variants of our main result. First, we show that σ C remains a strongly communication-proof equilibrium strategy in this more general setup (by contrast, strategies σ L and σ R might not be equilibria in this setup). While we do not have a full characterization of the set of communication-proof equilibrium strategies, we are able to show that strongly communication-proof equilibrium strategies must satisfy mutualpreference consistency and coordination whenever both players have sent the same message.
Extreme types with dominant actions Appendix E.6 extends our analysis to a setup in which some types find that one of the actions is a dominant action for them. We show that in the presence of these extreme types there exists an essentially unique strongly communication-proof equilibrium strategy that satisfies the three key properties, where the left tendency of this strategy is equal to the share of extreme types whose dominant action is L. In this setup moderate "leftists," i.e., types u ∈ (0, 1 /2), gain if there are more extreme "leftists" than extreme "rightists," in the sense that the above essentially unique communication-proof strategy induces a higher probability of coordination on action L when two agents with different preferred outcomes meet.

Discussion
Our notion of communication-proofness adapts Blume and Sobel's (1995) notion from sender-receiver games to games in which all players have incomplete information, all can communicate, and all can choose actions. Our notion is also related to notions of renegotiation-proofness that have been applied to repeated games (e.g., Farrell and Maskin, 1989;Benoit and Krishna, 1993), and to mechanisms and contracts in the presence of asymmetric information (e.g., Forges, 1994;Neeman and Pavlov, 2013;Maestri, 2017;Strulovici, 2017).
Starting with the secret handshake argument provided in Robson (1990) (see also the earlier related notion of "green beard effect" in Hamilton, 1964;Dawkins, 1976), there is a sizable literature on the evolutionary analysis of costless pre-play communication before players engage in a complete information coordination game. This includes, e.g., Sobel (1993), Blume et al. (1993), Wärneryd (1993), Kim and Sobel (1995), Bhaskar (1998), and Hurkens and Schlag (2003). Suppose that a complete information coordination game has two Pareto-rankable equilibria. Then the Paretoinferior equilibrium is not evolutionarily stable as it can be invaded by mutants who use a previously unused message as a secret handshake: if their opponent does not use the same handshake they simply play the Pareto-inferior equilibrium (as do all incumbents), but if their opponent also uses the secret handshake both sides play the Pareto-superior equilibrium. Our notion of communicationproofness extends the secret handshake argument to games with incomplete information by requiring that a communication-proof equilibrium should not to be Pareto-dominated by another equilibrium after any observed message profile. 17 One argument that can be presented against the notion of communication-proofness is that noncommunication-proof equilibria can be sustained by the following off-the-equilibrium path behavior: if any player proposes a joint deviation, then the equilibrium specifies that the opponent rejects the offer and that both players shift their behavior to playing an equilibrium that is bad for the proposer. This kind of off-the-equilibrium path proposer punishment would indeed deter players from suggesting joint deviations. 18 Recall that we give the notion of communication-proofness two different interpretations: either we think of communication-proof equilibria as the plausible final outcomes of the deliberations of two rational and communicating agents, or we think of these equilibria as the stable outcomes of a long-run learning or evolutionary process. Under each of these two interpretations one can counter the above proposer-punishing argument. Under the two rational deliberating agents interpretation, one can argue that agents may just have to be careful and subtle in the way they phrase their proposal. Suppose both agents face a situation (after initial messages are sent) in which they are about to play a Pareto-inferior action profile (relative to some possible available equilibrium in the induced game). They should then both realize that their proposer-punishing scheme, which prevents them from renegotiation, is not in their joint best interest and be able to overcome this.
Moreover, under the evolutionary interpretation, there is a more formal counterargument against proposer-punishing schemes. Any off-the-equilibrium path behavior is subject to evolutionary drift; see, e.g., Binmore and Samuelson (1999) for a general treatment of such drift. Eventually the contingent behavior of agents off-the-equilibrium path will start to drift to alternative behavior such as simply ignoring such proposals for joint deviation, or to a willingness to consider them (without applying a punishment). After sufficient drift in this direction, it will be in the agents' interest to offer Pareto-improving joint deviations. This implies that non-communication-proof equilibria with proposer-punishment mechanisms can only be neutrally stable (which is commonly interpreted as medium-run stability), but they cannot be evolutionarily stable. By contrast, communication-proof equilibria are evolutionarily stable and, as such drift cannot take behavior away from a communicationproof equilibrium.
Another related literature deals with stable equilibria in coordination games with private values, but without pre-play communication. Sandholm (2007) (extending earlier results of Fudenberg and Kreps, 1993;Ellison and Fudenberg, 2000) shows that mixed Nash equilibria of the game with complete information can be purified in the sense of Harsanyi (1973) in an evolutionarily stable way (see also Remark 2). 19 Finally, two related papers analyze stag-hunt games with private values. Baliga and Sjöström (2004) show that introducing pre-play communication induces a new equilibrium in which the Pareto-dominant action profile is played with high probability. Jelnov et al. (2018) show that in some cases a small probability of another interaction can substantially affect the set of equilibrium outcomes in stag-hunt games with private values.

A.1 Undominated Action Strategies
In this subsection we show that our restriction to threshold action functions is without loss of generality, in the sense that each generalized action function is dominated by a threshold strategy. Let Γ(F, G) be a coordination game without communication (possibly played after a pair of messages is observed in the original game Γ, M ). A generalized strategy in this game is a measurable function η : U → ∆ ({L, R}) that describes a mixed action as a function of the player's type. A generalized strategy in Γ(F, G) corresponds to a generalized action function ξ : A pair of generalized strategies η,η are almost surely realization equivalent (abbr., equivalent), which we denote by η ≈η, if they induce the same behavior with probability one, i.e., if It is immediate that two equivalent generalized strategies always induce the same (ex-ante) payoff, i.e., that π (η, η ′ ) = π (η, η ′ ) for each generalized strategy η ′ .
A generalized strategy is a cutoff strategy if there exists a type x ∈ [0, 1] such that η(u) = L for each u < x and η(u) = R for each u > x. A generalized strategy η is strictly dominated by generalized strategyη if π (η, η ′ ) < π (η, η ′ ) for any generalized strategy η ′ of the opponent.
The following result shows that any generalized strategy is either equivalent to a cutoff strategy, or it is strictly dominated by a cutoff strategy.
Lemma 1. Let η be a generalized strategy. Then there exists a cutoff strategyη, such that either η is equivalent toη, or η is strictly dominated byη.
Assume that η andη are not equivalent, i.e., η ≈η. Let η ′ be an arbitrary generalized strategy of the opponent. By construction, strategies η andη induce the same average probability of choosing L. Strategiesη and η differ in thatη induces lower types to choose L with higher probability, and higher types to choose L with lower probability, i.e., η u (L) ≤η u (L) for any type u ≤ x and η u (L) ≥η u (L) for any type u > x. Since η ≈η and E u∼F [η u (L)] ∈ (0, 1), it follows that the inequalities are strict for a positive measure of types, i.e., The fact that lower types always gain more (less) from choosing L (R) relative to higher types, with a strict inequality unless the opponent always plays R (L), implies that π (η, η ′ ) < π (η, η ′ ).

A.2 Proof of Theorem 1
We first prove the "1 ⇒ 2" part. Suppose that σ = (µ, ξ ) ∈ Σ is mutual-preference consistent, coordinated, and has binary communication. As σ is mutual-preference consistent it must satisfy Then as σ is mutual-preference consistent we have that ξ (m, m ′ ) = ξ (m ′ , m) = L. Thus ξ describes best-reply behavior after this message pair. Moreover this behavior is the best possible outcome for any type in [0, 1 /2] and thus for any type in supp (F m Action function ξ , therefore, again describes best-reply behavior. Moreover, one player always obtains her most preferred outcome. In order for a new strategy profile to improve the opponent's outcome, this new profile must require the former player to deviate from her most preferred outcome. Thus, no equilibrium σ ′ in the game Γ(F m , F m ′ ), M Pareto dominates σ after this message pair. This shows that action function ξ is a best response to µ and to itself given µ and that, moreover, it cannot be CP trumped. It remains to show that the message function µ is optimal when the opponent chooses σ = (µ, ξ ).
Consider type u ∈ [0, 1 /2] and consider this type's choice of message. As σ has binary communication and is coordinated, different messages m ∈ M can only trigger different probabilities of coordinating on L with a highest likelihood of such coordination for any message m ∈ supp(µ u ). Therefore, type u is indifferent between any message m ∈ supp(µ u ) and weakly prefers sending any message m ∈ supp(µ u ) to sending any message m ′ ∈ supp(µ u ). An analogous statement holds for types u ∈ [ 1 /2, 1]. This concludes the proof of the "1 ⇒ 2" part of the theorem.
We prove the "3 ⇒ 1" part in three lemmas, one for each of the three properties.
Proof. We need to show that for any message pair m, m ′ ∈ supp (μ), Let m, m ′ ∈ supp (μ) and assume to the contrary that because otherwise the sender of m ′ would play L with probability one or R with probability one, in which case the the best reply of the sender of message m would be to play L (or R) regardless of her type.
There are three cases to be considered. Case 1: Suppose that x, x ′ ≤ 1 /2. We now show that in this case the equilibrium (x, x ′ ) is CP-trumped by σ R . Consider the player who sent message m.
Case 1a: Consider a type u ≤ x. Then we have where the left-hand side is type a u agent's payoff under strategy profile σ R and the right-hand side the payoff under strategy profile (x, x ′ ). The inequality follows from the fact that u (1 − F m ′ ( 1 /2)) ≥ 0, and follows from the fact that F m ′ is nondecreasing (as it is a cumulative distribution function). This inequality is strict for all u except for u = 0 in the case where x ′ = 1 /2. Case 1b: Now consider a type u with x < u ≤ 1 /2. Then we have where the left-hand side is a type u agent's payoff under strategy profile σ R and the right-hand side is the payoff under strategy profile (x, x ′ ). The inequality follows from the fact that by u ≤ 1 /2 we have that 1 − u ≥ u, and therefore (1 − u) side is a type u agent's payoff under strategy profile σ R and the right-hand side is the payoff under strategy profile (x, x ′ ).
The analysis for the player who sent message m ′ is analogous.
Case 2: Suppose that x, x ′ ≥ 1 /2. The analysis is analogous to Case 1 if we replace σ R with σ L . Case 3: Suppose, w.l.o.g. for the remaining cases, that x ≤ 1 /2 ≤ x ′ . The equilibrium (x, x ′ ) in this case is Pareto-dominated by σ C . To see this, consider the player who sent message m.
Case 3a: Consider a type u ≤ x. Then we have where the left-hand side is a type u agent's payoff under strategy profile σ C and the right-hand side the payoff under strategy profile (x, x ′ ). The inequality follows from the fact that we have F m ′ (x ′ ) = x ≤ 1 /2 due to (x, x ′ ) being an equilibrium.
Case 3b: Now consider a type u with x < u ≤ 1 /2. Then we have where the left-hand side is a type u agent's payoff under strategy profile σ C and the right-hand side the payoff under strategy profile (x, x ′ ). The inequality follows from the fact that by u ≤ 1 /2 we have Case 3c: Finally, consider a type u > 1 /2. Then we have where the left-hand side is a type u agent's payoff under strategy profile σ C and the right-hand side is the payoff under strategy profile (x, x ′ ). The inequality follows from the fact that we have F m ′ ( 1 /2) > 0 and The analysis for the player who sent message m ′ is analogous.
Lemma 3. Every weakly communication-proof equilibrium strategy σ has binary communication.
Proof. Let σ be a communication-proof equilibrium strategy. Recall that As σ is coordinated by Lemma 2, the payoff to a type u from sending message m ∈ supp(µ) is For a type u < 1 /2 the problem of choosing a message to maximize her payoffs is thus equivalent to choosing a message that maximizes β σ (m). We thus must have that there is a β σ ∈ [0, 1] such that for all u < 1 /2 and all m ∈ supp(µ u ), we have β σ (m) = β σ . Analogously, we must have a β σ ∈ [0, 1] such that for all u > 1 /2 and all m ∈ supp(µ u ), we have α σ (m) = β σ . Clearly also β σ ≤ β σ . To extend the argument to unused messages m ∈ supp(µ) we rely on the full support assumption. Assume to the contrary that there is a message m ∈ supp(µ) with β σ (m) > β σ (resp., β σ (m) < β σ ). Then any sufficiently high (resp., low) type u would strictly earn by deviating to sending message m and playing L (resp., R), which contradicts the supposition that σ is an equilibrium strategy.
Lemma 4. Every weakly communication-proof equilibrium strategy σ is mutual-preference consistent.
Proof. By Lemma 2 a communication-proof equilibrium strategy σ = (µ, ξ ) is coordinated. Suppose that it is not mutual-preference consistent. Then there is either a message pair (m, m ′ ) such that there are types u, v < 1 /2 with m ∈ supp(µ u ) and m ′ ∈ supp(µ v ) such that play after (m, m ′ ) is coordinated on R, or a message pair (m, m ′ ) such that there are types u, v > 1 /2 with m ∈ supp(µ u ) and m ′ ∈ supp(µ v ) such that play after (m, m ′ ) is coordinated on L. In the former (resp., latter) case strategy σ is CPtrumped by strategy σ R (resp., σ L ) in the game Γ(F m , F m ′ ), {m L , m R } because strategy σ R (resp., σ L ) does not affect the payoff of all types u ≥ 1 /2 (resp., u ≤ 1 /2), and it strictly improves the payoff to all types u < 1 /2 (resp., u > 1 /2).

A.3 Proofs of Section 6 (On Efficiency)
Proof of Proposition 1. By Theorem 1 and the discussion of the one-dimensional set of strategies satisfying the key properties in Section 3 a communication-proof strategy σ 's equilibrium payoff is determined by its left tendency α ≡ α σ ∈ [0, 1]. This equilibrium payoff is given by for each type u ∈ (0, 1 /2], and it is given by for each type u ∈ ( 1 /2, 1]. The payoff to a type u from a given social choice function φ is given by Now suppose that φ interim Pareto dominates σ . Then π u (φ ) ≥ π u (σ , σ ) for all u ∈ [0, 1] with a strict inequality for a positive measure of u. As π u (σ , σ ) is a convex combination of two payoffs, this implies that: with at least one of the inequalities holding strictly for a positive measure of types. We can write where, for instance, E {v> 1 /2} denotes the expectation conditional on v > 1 /2. Substituting this last equality in Eq.
(1) yields the following inequality An analogous argument (applied to Eq. (2)) implies that E {v< 1 /2} φ u,v (R, R) ≥ 1 − α, for any u > 1 /2, with at least one of these inequalities holding strictly for a positive measure of types. This implies that with at least one of the two inequalities holding strictly. By the symmetry of φ we have φ u,v (R, R) = φ v,u (R, R) and thus which contradicts φ u,v being a social choice function.
The proof of Proposition 2 uses the following lemma (which is of independent interest).
Lemma 5. Let σ ∈ E be a coordinated equilibrium strategy. Then there is a communication-proof strategy σ ′ such that either σ and σ ′ are interim payoff equivalent or σ ′ interim Pareto dominates σ .
Proof. Let σ = (µ, ξ ) ∈ E be coordinated. For each message m ∈ M, let p m ∈ [0, 1] be the probability that the players coordinate on L, conditional on the agent sending message m: As σ is coordinated, it follows that 1 − p m is the probability that the players coordinate on R, conditional on the agent sending message m. Letp = max m∈M p m be the maximal probability, and let p = min m∈M p m be the minimal probability. By definition, p ≤p. As σ is an equilibrium strategy, p <p implies that all types u < 1 /2 send a message inducing probabilityp and all types u > 1 /2 send a message inducing probability p.
Therefore, the expected payoff of a type u ≤ 1 /2 is given by π u (σ , σ ) =p (1 − u) + (1 −p) u, and the expected payoff of any type u > 1 /2 is equal to π u (σ , σ ) = p (1 − u) + 1 − p u. This is also true if p =p. Note that for types u < 1 /2, the expected payoff strictly increases inp and for types u > 1 /2 the type's expected payoff strictly decreases in p.

B More on Properties of Strategies
In this appendix we demonstrate that no single one of the three properties (mutual-preference consistency, coordination, and binary communication) is implied by the other two. Clearly a strategy that has binary communication and is coordinated must be an equilibrium. No other combination of two of the three properties implies that a strategy is an equilibrium. Finally, we also define what it means for a strategy to be ordinal preference-revealing and show that this is implied by it being mutual-preference consistent.
Consider the following strategy σ = (µ, ξ ) in the game with communication with a message set M that contains at least three elements. Let m 1 This strategy is mutual-preference consistent and coordinated but does not have binary communication. It is not an equilibrium as types u ≤ 1 /4 would strictly prefer to send message m 2 L . Consider the following strategy σ = (µ, ξ ) in the game with communication with a message set M that contains at least two elements. Let m L , m R ∈ M, let . This strategy is mutual-preference consistent, has binary communication, but is not coordinated. For almost all type distributions F this is not an equilibrium: it is only an equilibrium if F satisfies Finally, for a strategy that has binary communication and is coordinated but not mutual-preference consistent, consider the equilibrium strategy that always leads to coordination on L for any pair of messages. Note also that an equilibrium does not necessarily satisfy any of the three properties. The interior cutoff babbling equilibria mentioned in Section 3 are not coordinated and not mutual-preference consistent. The equilibrium of Example 1 does not have binary communication.
Call a strategy σ = (µ, ξ ) ∈ Σ ordinal preference-revealing if there exist two nonempty, disjoint, and exhaustive subsets of supp(μ) denoted by M L and M R (i.e., supp(μ) =Ṁ L M R ) such that if u < 1 /2, then µ u (m) = 0 for each m ∈ M R , and if u > 1 /2, then µ u (m) = 0 for each m ∈ M L . With an ordinal preference-revealing strategy a player indicates her ordinal preferences. A strategy σ that is mutual-preference consistent is also ordinal preference-revealing (but not vice versa). Suppose not. Then there is a message m and two types u < 1 /2 and v > 1 /2 such that µ u (m), µ v (m) > 0. But then no matter how we specify ξ (m, m) we get either that if two types u meet they do not coordinate on L with probability one or if two types v meet they do not coordinate on R with probability one.

C Non-binary Communication Equilibrium
We here formally present the example, which is discussed informally at the end of Section 3, of an equilibrium in which agents reveal some information about the cardinality of their preferences.
Suppose that |M| ≥ 4 and consider the game with two rounds of communication. Let e, m L , m R ∈ M and let σ = (µ 1 , µ 2 , ξ ), with µ 1 : U → ∆(M), µ 2 : M × M ×U → ∆(M), and ξ : (M × M) 2 → U be as follows. For the first round of messages there is an x ∈ [0, 1] such that The second round of messages depends on the outcome of the first round and is best described in the

Each entry in this table describes the message function that a player follows if her first-stage message
is the one indicated on the left and her opponent's first-stage message is the one indicated at the top. The message function µ * (after for instance a message pair of (e, m L )) is just as in the definition of σ L and σ R (in Section 3). The message function µ C is as in the definition of σ C with an appropriate relabeling of four messages in M. The action function is also best given in table form as a function of the result of the first round of communication (or the second round when so indicated).
Action function ξ C is as defined for σ C applied to the second round of communication only. We can complete the description of this strategy by requiring that all other messages in M be treated exactly the same as one of the messages e, m L , m R .
Proposition 3. Let F be a nondegenerate symmetric distribution around 1 /2, i.e., F( for all x ∈ [0, 1]. Then there is an x ∈ (0, 1 /2) such that the above-defined strategy of the coordination game, with two rounds of communication and with |M| ≥ 4, is a Nash equilibrium.
Proof. Consider the given strategy for an arbitrary x ∈ (0, 1 /2). First note that whenever messages lead the players to coordinate their action then clearly both players are best replying to each other with their actions. This is so in all cases except when both players send message e in the first round.
In this case players choose L if their type u ≤ 1 /2 and R otherwise. Each player, in this case, faces an opponent that either has u ≤ x or u > 1 − x. In the first (second) case the opponent plays L (R). Given that F(x) = 1 − F (1 − x) both cases are equally likely. Given this, players' actions are indeed best replies. Thus, all action choices are best responses to the given strategy. We now turn to message choices.
Consider the second round. After moderate messages in the first round messages in the second round either do not affect play at all (after (m L , m L ) and (m R , m R )) or do so as in strategy σ C . In either case players are indifferent between all messages. After message pairs (m L , e) and (m R , e) the sender of the moderate message has a strict incentive to send the same message again, while the sender of the extreme message has a strict incentive to send m L if her type u < 1 /2 or to send m R if her type u > 1 /2 as this induces coordination on her preferred outcome. After both players send message e, play will not depend on messages in the second round either and so both players will be indifferent between all messages. Thus, the behavior in the second round of communication is a best response to the given strategy. Finally, we need to consider the incentives to send messages in the first round. It is obvious that any type u < 1 /2 prefers sending message m L to sending message m R and vice versa for types u > 1 /2. The only remaining thing to show is that types u ≤ x and u > 1 − x and only these weakly prefer to send message e in the first round. Given the symmetry it is without loss of generality to consider a type u ≤ 1 /2. Given the strategy, sending message e yields to this type a payoff of where F(x) is the probability that her opponent is an extreme left type, (F( 1 /2) − F(x)) is the probability that the opponent is a moderate left type, (F(1 − x) − F( 1 /2)) is the probability that the opponent is a moderate right type, in all of which cases both players eventually play L, and where (1 −F(1 −x)) is the probability that her opponent is an extreme right type, in which case the two players miscoordinate. Sending message m L yields a payoff of A type u ≤ 1 /2 therefore weakly prefers sending message e to sending message m L if and only if Using the symmetry of F we can rewrite D(x) as D Note that D x (u) is linear and downward sloping in u if x ∈ (0, 1 /2). In an equilibrium we then must have that D For this x the given strategy is thus an equilibrium.

D Evolutionary Stability Analysis
In this appendix we analyze the stability of strategies σ L and σ R (the results can be extended to other communication-proof equilibria, but we omit the details here for brevity).

D.1 Evolutionary/Neutral Stability
We say that two strategies are almost surely realization equivalent (abbr., equivalent) if they induce the same behavior in almost all types (regardless of the opponent's behavior).
Definition 5. A condition holds for almost all types if the set of types that satisfy the conditionŨ ⊆ U has mass one (as measured by the distribution f ), i.e., u∈Ũ f (u) du = 1.
If σ andσ are equivalent strategies we denote this by σ ≈σ . It is immediate that equivalent strategies always obtain the same ex-ante expected payoff.
An equilibrium strategy σ is neutrally (evolutionarily) stable if it achieves a weakly (strictly) higher ex-ante expected payoff against any (non-equivalent) best-reply strategy, relative to the payoff that the best-reply strategy achieves against itself.
The refinement of neutral stability is arguably a necessary requirement for an equilibrium to be a stable convention in a population (see, e.g., Banerjee and Weibull, 2000). If σ is an equilibrium strategy that is not neutrally stable, then a few experimenting agents who play a best-reply strategy σ ′ can invade the population. These experimenting agents would fare the same against the incumbents, whereas they would outperform the incumbents when being matched with other experimenting agents. This implies that, on average, these experimenting agents would be more successful than the incumbents, and their frequency in the population would increase in any payoff-monotone learning dynamics. This, in turn, implies that the population will move away from σ .
Our first result shows that both σ L and σ R are neutrally stable, and, moreover, they are evolutionarily stable if there are two feasible messages. Proof. We here prove this result for σ L . The proof for σ R proceeds analogously and is omitted. In order to prove this result we first characterize all strategies σ that are best responses to σ L and thus satisfy π(σ , σ L ) = π(σ L , σ L ). Consider the message and action choice of a type u when her opponent uses strategy σ L . If our type u chooses any message other than m R , her opponent, sending message m L or m R , plays action L in either case. Our type u could then choose action L (as prescribed by σ L ), which provides a payoff of 1 − u, or action R, which provides a payoff of zero. Thus all types u < 1 are strictly better off choosing action L in this case. Also note that sending any message other than m L leads to a best possible payoff of 1 − u.
If our type u chooses to send message m R then there are two cases. First, suppose that her opponent sends message m L , in which case her opponent chooses action L. Our type u could then choose action L (as prescribed by σ L ), which provides a payoff of 1 − u, or action R which provides a payoff of zero. Thus all types u < 1 are strictly better off choosing action L in this case. Second, suppose that her opponent sends message m R , in which case her opponent chooses action R. Our type u could then choose action R (as prescribed by σ L ), which provides a payoff of u, or action L which provides a payoff of zero. Thus all types u > 0 are strictly better off choosing action R in this case. Note that sending message m R thus provides a best possible payoff of For type u it is then a strict best response to send message which is the case if and only if u > 1 /2 (as F( 1 /2) ∈ (0, 1) by assumption). For the case of |M| = 2 we then have that any best response to σ L is equivalent to σ L as only three possible types have an alternative best reply: types u = 0, u = 1 /2, and u = 1 (all zero measures under the assumption of an atomless distribution F). Any strategy that differs from σ L for a positive measure of types yields a strictly inferior payoff against σ L than σ L does. This proves that σ L is evolutionarily stable in the case of |M| = 2 simply by virtue of the fact that there are no nonequivalent strategies σ that satisfy π(σ , σ L ) = π(σ L , σ L ).
Suppose from now on that |M| > 2. Our type u then has a choice of messages m = m R when u < 1 /2. All of these messages can at best lead to a payoff of u (from playing L, L) and, therefore, all of them are equally good when playing against σ L . As her opponent never chooses any message other than m L or m R (each has probability zero under σ L ) our type u < 1 /2 when best responding can play anything after any message pair (m, m ′ ) when both m, m ′ ∈ {m L , m R }. Let σ be a strategy that satisfies all the previous restrictions, where all types u play a (in most cases unique and strict) best response against σ L . Then we have that π u (σ , σ ) = π u (σ L , σ ) for all u ≥ 1 /2 (as the behavior under σ for types u ≥ 1 /2 (except for possibly types u = 1 /2 and u = 1) is identical to that under σ L ), π u (σ , σ ) ≤ 1 − u for all u < 1 /2 (since this type can achieve at best 1 − u), and π u (σ L , σ ) = 1 − u (since σ similarly to σ L prescribes playing L in this case). We thus have for any such σ by construction π(σ , σ L ) = π(σ L , σ L ).
We also have that π(σ L , σ ) ≥ π(σ , σ L ) for any such σ . Finally any best-reply strategy to strategy σ L must be equivalent to some such strategy σ and thus σ L is neutrally stable.

D.2 Message Function is Dominant
Next we show that the first-stage behavior induced by strategy σ L (resp., σ R ), namely, the message function µ * , is weakly dominant (and strictly dominant when |M| = 2), when taking as given that the behavior in the second stage is according to the action function ξ L (resp., ξ R ). This suggests that the behavior in the first stage that is induced by σ L (resp., by σ R ) is robust to any perturbation that keeps the behavior in the second stage unchanged. Specifically, it implies that even if the message function used by the population is perturbed in an arbitrary (and possibly significant) way, then the original function µ * yields a weakly higher payoff than any other message function, which suggests that the behavior in the first stage would converge back to play µ * under any payoff-monotone learning dynamics. Proposition 5 shows that message function µ * yields a weakly higher payoff relative to any other message function when the action function is given by ξ L or ξ R . Moreover, the inequality is strict whenever the alternative message function is essentially different from µ * in the sense of inducing low types to play m R or inducing high types to play m = m R .
Proposition 5. Let µ ′ , µ ′′ be arbitrary message functions. Then for, ξ ∈ {ξ L , ξ R } and for any type This inequality is strict for ξ = ξ L if µ ′ u (m R ) > 0 for a positive measure of types u and, either µ ′′ u (m R ) > 0 for a positive measure of types u < 1 /2, or µ ′′ u (m R ) < 1 for a positive measure of types u > 1 /2. This inequality is strict for ξ = ξ R if µ ′ u (m L ) > 0 for a positive measure of types u and, either µ ′′ u (m L ) > 0 for a positive measure of types u > 1 /2, or µ ′′ u (m L ) < 1 for a positive measure of types u < 1 /2.
Proof. Consider the case of ξ = ξ L (the other case is proven analogously). Let γ denote the probability that a player following strategy (µ ′ , ξ L ) sends message m R . Then sending any message other than m R when the partner sends (µ ′ , ξ L ) yields a payoff of 1 − u, and sending message m R yields a payoff of γu + (1 − γ)(1 − u). Thus any type u > 1 /2 weakly prefers sending message m R to sending any other message (and strictly prefers this if γ > 0), while any type u < 1 /2 weakly prefers sending any message other than m R to sending message m R (and strictly prefers this if γ < 1). Thus, for every message function µ ′ of the opponent, µ * optimizes the message choice for every type u universally.

D.3 Action Function is a Neighborhood Invader Strategy
In the induced second-stage game Γ(F m , F m ′ ) (the game played after players observe a pair of messages (m, m ′ )), players choose a cutoff to determine whether to play action L (if their type is below or equal to that cutoff) or action R (otherwise). Thus, players essentially choose a number (their cutoff) from the unit interval. Note also that this induced game is asymmetric whenever the message profile is asymmetric, i.e., when m = m ′ . As argued by Eshel and Motro (1981) and Eshel (1983), when the set of strategies is a continuum, a stable convention should be robust to perturbations that slightly change the strategy played by all agents in the population. Cressman (2010) formalizes this requirement using the notion of neighborhood invader strategy (adapting the related notion of Apaloo, 1997). In what follows we show that the action function induced by σ L and σ R is a neighborhood invader strategy in any induced game Γ(F m , F m ′ ) on the path of play.
Fix a message function µ and a pair of messages m 1 , m 2 ∈ supp (μ). We identify a strategy in the induced game Γ (F m 1 , F m 2 ) with thresholds x i , which is interpreted as the maximal type for which player i ∈ {1, 2} plays L. We say that strategy x i of player i is equivalent to , which implies that both thresholds induce the same behavior with probability one. Let π m 1 ,m 2 (x 1 , x 2 ) denote the expected payoff of an agent with a random type sampled from f m 1 who uses threshold x 1 when facing a partner with a random unknown type sampled from f m 2 who uses threshold x 2 .
A strategy profile (x 1 , x 2 ) is a strict equilibrium if any best reply to x j is equivalent to We say that the strict equilibrium (x 1 , x 2 ) is a neighborhood invader strategy in the induced game Γ (F m 1 , F m 2 ) if the population converges to (x 1 , x 2 ) from any nonequivalent nearby strategy profile (x ′ 1 , x ′ 2 ) in two steps: (1) strategy x i yields a strictly higher payoff against x j relative to the payoff of , and (2) due to (x 1 , x 2 ) being a strict equilibrium, strategy x j yields a strictly higher payoff against x i relative to the payoff of x ′ j against x i (which implies the convergence from x i , x ′ j to x i , x j ).
Definition 8 (Adaptation of Cressman, 2010, Def. 5). Fix a message function µ and a pair of messages m 1 , m 2 ∈ supp (μ). A strict Nash equilibrium (x 1 , x 2 ) is a neighborhood invader strategy profile in . Proposition 6 shows that the profile of action functions induced by σ L (or, similarly, by σ R ) is a neighborhood invader strategy in any induced game.

D.4 Remark on Evolutionary Robustness
Oechssler and Riedel (2002) present a strong notion of stability, called evolutionary robustness, that refines both evolutionary stability and the neighborhood invader strategy. An evolutionary robust strategy σ * is required to be robust against small perturbation in the strategy played by the population, which may comprise both (1) a few experimenting agents who follow arbitrary strategies, and (2) many agents who follow strategies that are only slightly different than σ * . Specifically, if σ is a distribution of strategies that is sufficiently close to σ * (in the L 1 norm induced by the weak topology), evolutionary robustness à la Oechssler and Riedel requires that π (σ * , σ ) > (σ , σ ).

E Analysis of the Extensions E.1 Multiple Rounds of Communication
For any message protocol m ∈ M, let β σ (m) denote the expected probability of a player's opponent playing L conditional on the player following message protocol m ∈ M and the opponent following strategy σ = (µ, ξ ) ∈ Σ. We say that strategy σ has binary communication if there are two numbers 0 ≤ β σ ≤ β σ ≤ 1 such that for all message protocols m ∈ M we have β σ (m) ∈ [β σ , β σ ], for all message protocols m ∈ M such that there is a type u < 1 /2 with µ u (m) > 0 we have β σ (m) = β σ , and for all message protocols m ∈ M such that there is a type u > 1 /2 with µ u (m) > 0 we have β σ (m) = β σ . That is, binary communication implies that players use just two kinds of message protocols: any message protocol used by types u < 1 /2 induces the consequence of maximizing the probability of the opponent to play L, and any message protocol used by types u > 1 /2 induces the opposite consequence of maximizing the probability of the opponent to play R. Theorem 1, together with Propositions 1 and 2, holds in this setting with minor adaptations to the proof (omitted for brevity). Thus, regardless of the length of the pre-play communication, agents can reveal only their preferred outcome (but not the strength of their preference), and, regardless of having access to additional rounds of communication, they cannot improve the ex-ante expected payoff relative to the payoff induced by a single round of communication with a binary message.

E.2 Multidimensional Sets of Types
In our model we made the simplifying assumption that miscoordination provides the same payoff (normalized to zero) to both players. This is not completely innocuous. In this section we explore which results are still true in this more general setting. Consider the following multidimensional set of types. LetÛ, a subset of R 4 , be the set of payoff matrices of binary coordination games, with u ab being the payoff if a player chooses action a ∈ {L, R} while her opponent chooses action b ∈ {L, R}: Thus, all types strictly prefer coordination on the same action as the partner to miscoordination. Note that any affine transformation of all payoffs neither changes the player's incentives nor changes how she compares any two outcome distributions ∈ ∆ ({L, R}). We can thus subtract min {u RL , u LR } from all payoffs and then divide all payoffs by some number such that the sum of the diagonal entries is equal to one. This leaves two parameters to describe a payoff vector inÛ . This means that for our purposes the setÛ is two-dimensional. LetΓ =Γ (G) denote the coordination game with the twodimensional type spaceÛ , endowed with an atomless CDF G overÛ with a density g. Similarly, let Γ , M be the corresponding game with communication.
Given a type u = (u LL , u LR , u RL , u RR ), let ϕ u ∈ [0, 1] denote type u's indifference threshold, which is the probability of the opponent playing L that induces an agent of type u to be indifferent: Observe that an agent with indifference threshold ϕ u , where ϕ u is a number always between 0 and 1, prefers to play L (R) if her partner plays L with probability larger (smaller) than ϕ u . In other words, for a given probability of her partner playing L, a type u prefers to play L if and only if ϕ u is less than that probability. Thus, the indifference threshold ϕ u replaces what we denoted by u in the main model. In particular, in this setting we can also restrict attention to cutoff action functions. These are now applied to ϕ u instead of to u. Thus, under a strategy σ = (µ, ξ ) a player plays action L after observing a message pair (m, m ′ ) if and only if ϕ u ≤ ξ (m, m ′ ).
Recall, that action L is risk-dominant (Harsanyi and Selten, 1988) if it is a best reply against the opponent randomizing equally over the two actions, i.e., if ϕ u ≤ 1 /2 ⇔ u LL − u LR ≥ u RR − u RL .
The crucial assumption that we implicitly made in our (one-dimensional) main model is that for any type of player the action that she prefers to coordinate on is also risk-dominant for her.
Definition 9. An atomless distribution over the payoff space U with density function g : U → R satisfies unambiguous coordination preferences if for any u ∈ U with g(u) > 0 we have u LL ≥ u RR ⇔ ϕ u ≤ 1 /2.
Under a distribution over types with unambiguous coordination preferences, every type in its support prefers coordinating on action L iff that type finds action L risk dominant. Under the assumption that the distribution satisfies unambiguous coordination preferences, Thm. 1 goes through unchanged if we set to be the implied distribution over the players' indifference threshold induced by density g. As in the baseline model, we assume that F(ϕ) has full support on the interval [0, 1].
Theorem 2 (Theorem 1 adapted to a multidimensional set of types). Let σ be a strategy of a game Γ , M that satisfies unambiguous coordination preferences. Then the following three statements are equivalent: 1. σ is mutual-preference consistent, coordinated, and has binary communication.
2. σ is a strongly communication-proof equilibrium strategy.

σ is a weakly communication-proof equilibrium strategy.
The proof is presented in Appendix E.7.1. The intuition is the same as in Theorem 1. The adaptation of Lemma 2, to the current setup relies on having unambiguous coordination preferences. Example 2 demonstrates that the restriction of unambiguous coordination preferences is necessary for the "3 ⇒ 1" part of the result.
Example 2. There are four possible preference types as follows: The distribution of types F is such that 20 P (u L 1 ) = P (u R 1 ) = 1 /18 and P (u L 2 ) = P (u R 2 ) = 8 /18. 20 This distribution is discrete, but could be modified to a nearby atomless distribution without changing the result.
Proposition 7. The equilibrium given in Example 2 is not strongly communication proof, but it is weakly communication proof.
We prove Proposition 7 through a series of claims. Note that, given the equilibrium in question, after message pairs (m L , m L ) and (m R , m R ) no Pareto improvement is possible. It remains to be shown that, while there is a Pareto-improving equilibrium (with new communication) after message pair (m L , m R ), all Pareto-improving equilibria after message pair (m L , m R ) are themselves CP-trumped.
The following claims refer to the situation after observed message pair (m L , m R ).
Claim 3. In any equilibrium of this game with or without additional communication, type L 1 (R 1 ) receives a payoff that is at least as high as that of type L 2 (R 2 ).
Proof. The stage game payoff matrix for L 1 weakly exceeds that of L 2 . Suppose there is an equilibrium in which L 2 expects a strictly higher payoff that L 1 . Then L 1 can imitate L 2 and get at least the same payoff, a contradiction.
Claim 4. Consider an equilibrium of this game with communication that CP trumps the considered equilibrium ((L,R),(R,L)) with respect to (m R , m L ) and that is not itself CP trumped by another strategy. If there is a message m that only type L 1 (R 1 ) sends, then play after this message must be fully coordinated (against all opponent messages).
Proof. A message m that only L 1 sends reveals L 1 (leads to an updated belief that m sender is of type L 1 with probability α = 1). Then only coordinated equilibria are possible as undominated equilibria -see Claim 2 above for cases with α = 1. An analogous argument can be made for type R 1 .
Claim 5. In any equilibrium of this game with communication that CP trumps the considered equilibrium ((L,R),(R,L)) and that is not itself CP trumped by another strategy, there can be no message sent with positive probability by type L 1 (R 1 ) that leads to coordinated play against all opponent messages.
Proof. Suppose there is a message m that type L 1 sends with positive probability that leads to coordinated play (for all opponent messages). Then to Pareto-dominate the original equilibrium L 1 must expect a payoff of at least 16 9 . Then type L 2 could imitate L 1 and also obtain the same payoff that L 1 obtains (because when play is coordinated both types receive the same payoff). Any other message m ′ that type L 2 sends must also provide the same payoff. Suppose play after message m ′ is not fully coordinated. Then type L 1 can send message m ′ and imitate L 2 's behavior and receive a strictly higher payoff than L 2 does. Thus, message m ′ must also lead to fully coordinated play against all opponent 7 18 < 2 5 and analogously 1 9 β ≤ 2 3 . In this equilibrium L 1 and R 1 types have a payoff of 2(1 − ν) and 2(1 − µ), respectively, which is the same payoff they get in the original (L,R),(R,L) equilibrium. Types L 2 and R 2 receive a payoff of more than 1, which is more than they receive in the original (L,R),(R,L) equilibrium. Thus the new strategy CP trumps the original one.
Claims 7 and 8 combine to prove that any strategy that CP trumps ((L,R),(R,L)) in the given game is itself CP trumped. This proves that ((L,R),(R,L)) is weakly communication proof. By Lemma 8 we also have that ((L,R),(R,L)) is not strongly communication proof. This proves Proposition 7.
Note, however, that any strategy that is coordinated and mutual-preference consistent and has binary communication is strongly communication-proof also in the general setting, and that only the "3 ⇒ 1" part of the main result fails without the assumption of unambiguous coordination preferences. One can show that any communication-proof equilibrium strategy must satisfy mutual-preference consistency, but, possibly, need not satisfy the other two properties (namely, coordination and binary communication).

E.3 More Than Two Players
Consider a variant of the coordination game in which there are n ≥ 2 players who play a symmetric coordination game (with private values) with pre-play communication. The action set is {L, R} for every player and the payoff to player i is equal to u i if every player chooses action R, equal to 1 − u i if every player chooses L, and equal to zero otherwise. The payoff to type u i is independent and identically drawn from some given distribution F with support in the unit interval [0, 1]. Before players choose actions, they simultaneously send messages from a finite set of messages M and observe all these messages. Let Γ n , M denote this n-player coordination game with pre-play communication.
In this setting the appropriate version of Theorem 1 still holds.
Theorem 3 (Theorem 1 adapted to more than two players). Let σ be a strategy of the n-player coordination game Γ n , M . Then the following three statements are equivalent: 1. σ is mutual-preference consistent, coordinated, and has binary communication.

σ is a strongly communication-proof equilibrium strategy.
3. σ is a weakly communication-proof equilibrium strategy.
Sketch of proof; for the formal proof see Appendix E.7.2. The proof of the "3 ⇒ 1" direction has to be adapted (the proof of the "1 ⇒ 2" direction remains, essentially, the same). In this setting it is not generally true that any play that involves miscoordination is CP-trumped by σ L , σ R ,or σ C . The proof instead first establishes that miscoordination after all players send the same message must be Paretodominated by either σ L or σ R (Lemma 7). This is then used to show that a weakly communicationproof equilibrium strategy must be mutual-preference consistent (Lemma 8). Then one can show that a weakly communication-proof strategy must be coordinated and must have binary communication (Lemma 9).
Prop. 1 and Cor. 1 also hold in the multi-player setting: communication-proof equilibrium strategies are interim Pareto-undominated and Pareto-improving relative to all symmetric equilibria of the game without communication. By contrast, Prop. 2 does not extend to this setting: with three players, for instance, for some distributions of values F, the strategy that determines the fallback option by majority vote (in the case of messages that indicate different preferred actions) is an ex-ante payoff improvement over a simple fallback norm of choosing, say, action L in every case of disagreement.

E.4 Asymmetric Coordination Games
Adapted Model Consider a setup similar to our baseline model except that the distributions of the types of the two players' positions differ: the type of player 1 is distributed according to F 1 and the type of player 2 is distributed according to F 2 . As in the baseline model, both distributions are assumed to be atomless with full support in [0, 1]. Let Γ (F 1 , F 2 ) , M denote the asymmetric coordination game with communication (to ease notation, we assume that both players have the same set of messages at their disposal). Let Σ i denote the set of all strategies of player i ∈ {1, 2}. We let i denote the index of one player and j denote the index of the opponent.
Adapted Properties We adapt the three key properties of Section 3 as follows. Let µ i u (m i ) denote the probability, given message function µ i , that player i sends message m i if she is of type u i . Let µ i (m i ) = E u∼F i µ i u (m i ) be the average (ex-ante) probability of player i sending message m i . A strategy profile (σ 1 , σ 2 ) is mutual-preference consistent if whenever u 1 , u 2 < 1 /2 then ξ 1 (m 1 , m 2 ) = ξ 2 (m 1 , m 2 ) = L for all m 1 ∈ supp µ 1 u and m 2 ∈ supp µ 2 u , and whenever u 1 , u 2 > 1 /2 then ξ 1 (m 1 , m 2 ) = ξ 2 (m 1 , m 2 ) = R for all m 1 ∈ supp µ 1 u and m 2 ∈ supp µ 2 u .
For any strategy profile σ = (µ 1 , ξ 1 ), (µ 2 , ξ 2 ) ∈ Σ 1 × Σ 2 and any message m j ∈ M, define as the expected probability of player i playing L conditional on player j sending message m j ∈ M. We say that strategy profile σ = (σ 1 , σ 2 ) has (essentially) binary communication if there are two pairs of numbers 0 ≤ β σ 1 ≤ β σ 1 ≤ 1 and 0 ≤ β σ 2 ≤ β σ 2 ≤ 1 such that for all messages m ∈ M and each player for all messages m ∈ M such that there is a type u < 1 /2 with µ j u (m) > 0 we have β σ i (m) = β σ i ; and for all messages m ∈ M such that there is a type u > 1 /2 with µ u (m) > 0 we have β σ i (m) = β σ i . Consider a strategy profile σ = (σ 1 , σ 2 ) that is coordinated and mutual-preference consistent and has binary communication. Then there are α σ 1 , α σ 2 ∈ [0, 1] such that, for each i ∈ {1, 2}, where α σ i is the probability of coordination on L conditional on player i having type u i < 1 /2 and player j having type u i > 1 /2. We refer to α σ = α σ 1 , α σ 2 as the left-tendency profile of a strategy profile σ that is coordinated and mutual-preference consistent and has binary communication. It is simple to see that the set of strategies satisfying the above three properties (coordination, mutualpreference consistency, and binary communication) is essentially two-dimensional because the lefttendency profile α σ = α σ 1 , α σ 2 of such a strategy profile σ describes all payoff-relevant aspects. Two such strategy profiles σ and σ ′ with the same left-tendency profile (i.e., with α σ = α σ ′ ) can only differ in the way in which the players implement the joint lottery when they have different preferred outcomes, but these implementation differences are not payoff-relevant, as the probability of the joint lottery inducing the players to play L remains the same.
Adaptation of communication-proofness Given a strategy profile of the game Γ, M we denote the induced "renegotiation" game after a positive probability message pair m 1 , m 2 ∈ M is sent by Γ(F m 1 , F m 2 ),M . For a strategy profile σ ′ of such a renegotiation game Γ(G 1 , G 2 ),M , define the post-communication expected payoffs for a player i of type u by Define E (G 1 , G 2 ) as the set of all (possibly asymmetric) equilibrium profiles of the coordination game with communication Γ(G 1 , G 2 ),M for some finite message setM.
pair of actions a i , a j there are also equilibria in which players send only one of two messages, one message indicating a preference for a i and another for not a i with play coordinated on a i if both players send the appropriate message and play coordinated on a j otherwise. None of these equilibria are communication-proof as they are not mutual-preference consistent and mutual-preference consistency is a necessary condition for a strategy to be communication-proof also in the present context, as we shall see below.
It is more difficult to find equilibria that are mutual-preference consistent, that is equilibria in which each player indicates her most preferred action out of all k actions and play is coordinated on that action if both players indicate a preference for it. Simple adaptations of σ L and σ R are not equilibria in the present context. To see this, consider a strategy in which there is a "fallback" action, say action a 1 , in which players indicate their most preferred action (the action with the highest u i ), and in which play is coordinated on either action a i if both players indicate a preference for it, or coordinated on action a 1 otherwise. Suppose that the distribution of types is such that there are two actions a i and a j (unequal to each other and unequal to a 1 ) with p j > p i . But then there is a player type u = (u 1 , u 2 , . . . , u k ) with u i = max{u 1 , . . ., u k }, u j very close to u i , and u 1 < u j , who would prefer to indicate a preference for action a j . Indicating a preference for action a i , under the given strategy, provides her with a payoff of p i u i + (1 − p i )u 1 . Indicating a preference for a j yields a payoff of p j u j + (1 − p j )u 1 . But then for a suitably chosen vector u = (u 1 , u 2 , . . ., u k ) the latter expression is greater than the former, which contradicts the supposition that the given strategy is an equilibrium.
Next we show that a simple adaptation of σ C remains a strongly communication-proof equilibrium strategy also in this setup. Let m 0 1 , m 0 2 , . . . , m 0 k , m 1 1 , m 1 2 , . . . , m 1 k ∈ M be 2k distinct messages, where the index i of message m b i is interpreted as denoting that the agent's preferred outcome is the i-th outcome, and the index b ∈ {0, 1} is interpreted as a random binary number. Let σ C = (µ C , ξ C ) be extended to the current setup as follows. Define µ C (u) = 1 /2m 0 i ⊕ 1 /2m 1 i , where i = argmin j u j | u j = max {u 1 , .., u k } . Thus, the message function µ C induces each agent to reveal her preferred outcome, and to uniformly choose a binary number (either, zero or one). In the second stage, if both agents share the same preferred outcome they play it. Otherwise, they coordinate on the preferred action with the smaller index if both agents have chosen the same random number, and they coordinate on the preferred outcome with the larger index if both agents have chosen different random numbers, i.e., We then have the following proposition.
Proposition 8. Strategy σ C is a strongly communication-proof equilibrium strategy in the game Proof. Observe that an agent who sends message m b i obtains an expected payoff of 1 /2u i + 1 /2 ∑ k j=1 p j u j when facing a partner who follows strategy σ C . As the second term in this sum is the same for all messages, an agent of type u sends this message only if u i = max{u 1 , . . . , u k }, as required. The remaining arguments as to why the second-stage behavior is a best reply and why σ C is strongly communicationproof are analogous to the proof of the "if" part of Theorem 1 and are omitted for brevity.
A strategy σ = (µ, ξ ) is same-message coordinated if for all messages m ∈ supp(μ) there is an action a i such that for all u with µ u (m) > 0 we have ξ (u, m, m) = a i . In what follows we show that a necessary condition for a strategy to be a communication-proof equilibrium strategy is that this strategy is same-message coordinated and mutual-preference consistent.
Proposition 9. If strategy σ of the game Γ A , M with action set A is strongly communication-proof, then it is same-message coordinated and mutual-preference consistent.
Sketch of proof; for the formal proof see Appendix E.7.3. To show that a communication-proof equilibrium strategy is same-message coordinated we cannot, in fact, use the proof of the main theorem because Lemma 2 crucially depends on the game having only two actions. Instead, we suppose to the contrary that there is a communication-proof equilibrium strategy in which play is not coordinated after both players have sent the same message m. This strategy thus induces some nondegenerate probability distribution over actions after both players send message m. We then construct a CPtrumping equilibrium that is fully coordinated and has a probability of coordination on every action exactly equal to the probability of this action being played under the original strategy conditional on observing (m, m), which contradicts the supposition. The construction is achieved by players sending random messages in such a way that they are indifferent between all messages and this joint lottery is implemented. 21 The proof that a strongly communication-proof equilibrium strategy must be mutualpreference consistent is then achieved straightforward (by a simple adaptation of Lemma 8).
We are able neither to show nor to provide a counterexample that a strongly communication-proof strategy must be coordinated after observing a pair of different messages, and that it must have binary communication.

E.6 Extreme Types with Dominant Actions
In this subsection we show how to extend our analysis to a setup in which some types have an extreme preference for one of the actions such that it becomes a dominant action for them.
Let a < 0 and b > 1. We extend the set of types to be the interval [a, b]. Observe that action L (R) is a dominant action for any type u < 0 (u > 1) as coordinating on R (L) yields to such a type a negative payoff of u < 0 (1 − u < 0). We call types with a dominant action (i.e., u < 0 or u > 1) extreme, and types that do not have a strictly dominant action (i.e., u ∈ [0, 1]) moderate. We assume that the cumulative distribution of types F is continuous (atomless) and has full support in the interval [a, b].
We further assume that the extreme types are a minority both among the agents who prefer action R and among the agents who prefer L, i.e., F (0) < 1 /2F ( 1 /2) and 1 − F (1) < 1 /2 (1 − F ( 1 /2)). Next, we adapt the definitions of coordination and binary communication to the current setup. The original definition of coordination is too strong in the current setup, as, clearly, when extreme types with different preferred outcomes meet they must miscoordinate. Thus, we present a milder notion. A strategy is weakly coordinated if whenever two moderate types meet they never miscoordinate. Note that the definition does not impose any restriction on what happens when an extreme type meets a moderate type.
The original definition of binariness is too weak in the current setup. This is because coordinated strategies must allow for some miscoordination between extreme types, which implies that an agent cares not only about the average probability of the opponent playing left (i.e., β σ (m)), but also about the total probability of miscoordination. Thus, we strengthen binariness by requiring that there exist two distributions of messages, which are used by all types below 1 /2 and all types above 1 /2, respectively. Formally, a strategy σ = (µ, ξ ) has strongly binary communication if µ (u) = µ (u ′ ) if either u, u ′ ≤ 1 /2 or u, u ′ > 1 /2. It is easy to see that the strategies σ L , σ R , σ C defined in Section 3 all satisfy strongly binary communication. Moreover, one can show, for any α ∈ [0, 1], that if there exists a strategy σ that is coordinated, mutual-preference consistent, and has binary communication with left tendency α, then there also exists strategyσ with the same properties that is strongly binary communication.
Our next result shows that there exists, essentially, a unique communication-proof equilibrium strategy that is coordinated, mutual-preference consistent, and has strongly binary communication.

Proposition 10. In a coordination game with communication and with dominant action types, a strategy σ that is coordinated, mutual-preference consistent, and has strongly binary communication is a strongly communication-proof equilibrium strategy if and only if it has a left tendency of
The formal proof is presented in Appendix E.7.4. The key intuition is that given the frequency of dominant action types F(0) > 0 (of L-dominant action types) and 1 − F(1) > 0 (of R-dominant action types) to make the agent of type u = 1 /2 indifferent between signaling a lower than half or higher than half type we must have a strategy that counterbalances these frequencies of dominant action types. To see this, consider an adaptation of σ L = (µ * , ξ L ) to this setting by having extreme types follow their dominant action in the second stage (and moderate types play in the same way as in the baseline model). Note that σ L is no longer an equilibrium with extreme types. Observe that having a moderate type send message m R leads to coordination with probability one (sometimes on R and sometimes on L depending on the opponent's message), while having a moderate type send message m L leads to coordination (on L only) with probability F (1) < 1. This implies that agents of type u < 1 /2 sufficiently close to 1 /2 strictly prefer sending message m R to sending message m L (as the former induces a higher probability of coordination on the same action as the partner), which contradicts the supposition that σ L is an equilibrium strategy.
Appendix E.7.4 also shows that a left tendency α communication-proof strategy that is coordinated and has strongly binary communication can be implemented whenever α is a rational number and the set of messages M is sufficiently large (and irrational α-s can be approximately implemented by ε-equilibria).
Observe that in the symmetric case (F (0) = 1 − F (1)), strategy σ C is the essentially unique strongly communication-proof strategy with the above two properties. Further observe that in the asymmetric case, the moderate types gain if the extreme types with the same preferred outcome are more frequent than the extreme types of the opposite preferred outcome. Specifically, if there are more extreme "leftists" than extreme "rightists" (i.e., F (0) > 1 − F (1)), then the essentially unique strongly communication-proof strategy with properties of coordination and strongly binary communication induces higher probability to coordinate on action L (rather than on action R) whenever two moderate agents with different preferred outcomes meet. E.7 Formal Proofs of Extensions E.7.1 Proof of Theorem 2 (Multidimensional types, Section E.2) The proof of Thm. 2 mimics the proof of Thm. 1 except that Lemma 2 has to be adapted somewhat as follows (this is the only place where one uses the assumption of unambiguous coordination preferences).
Lemma 6. Assume that the atomless distribution of types have unambiguous coordination preferences. Let σ = (µ, ξ ) be a weakly communication-proof equilibrium strategy. Then it is coordinated.
Proof. We need to show that for any message pair m, m ′ ∈ supp (μ), Let m, m ′ ∈ supp (μ) and assume to the contrary that As σ is an equilibrium, we must have inf (Otherwise the m ′ message sender would play L with probability one or R with probability one, in which case the m message sender's best response would be to play L (or R) regardless of her type). m). In what follows we will show that the equilibrium (x, x ′ ) of the game without communication Γ (F m , F m ′ ) is Pareto-dominated by either σ L , σ R , or σ C (all based on ϕ u instead of u).
There are three cases to be considered. Case 1: Suppose that x, x ′ ≤ 1 /2. We now show that in this case the equilibrium (x, x ′ ) is Pareto-dominated by σ R . Consider the player who sent message m.
Case 1a: Consider a type u with ϕ u ≤ x. Then we have where the first expression is the type u agent's payoff under strategy profile (x, x ′ ) and the last expression is her payoff under strategy profile σ R . The first inequality follows from u LL ≥ u LR and by the fact that F m ′ is nondecreasing (as it is a CDF), and the second inequality follows from u RR ≥ u LR . This inequality is strict when u LL > u LR and F m ′ ( 1 /2) > F m ′ (x ′ ) or when u RR > u LR . Case 1b: Now consider a type u with x < ϕ u ≤ 1 /2. Then we have where the first expression is the type u agent's payoff under strategy profile (x, x ′ ) and the last expression is her payoff under strategy profile σ R . The first inequality follows from u LL ≥ u RL and the second one from F m ′ ( 1 /2) ≥ F m ′ (x ′ ) and u LL ≥ u RR . Note also that the second inequality follows from the assumption of unambiguous coordination preferences and ϕ u ≤ 1 /2. This inequality is strict when Case 1c: Finally, consider a type u with ϕ u > 1 /2. Then we have u RR > u RL F m ′ (x ′ )+u RR (1 − F m ′ (x ′ )), where the right-hand side is the type u agent's payoff under (x, x ′ ) and the left-hand side is her payoff under σ R . The inequality follows from the observation that u RR > u RL because u RR > u LL by the assumption of unambiguous coordination preferences, and u LL ≥ u RL by the fact that it is a coordination game.
The analysis for the player who sent message m ′ is analogous. Case 2: Suppose that x, x ′ ≥ 1 /2. The analysis is analogous to Case 1 if we replace σ R with σ L .
Case 3: Suppose, without loss of generality for the remaining cases, that x ≤ 1 /2 ≤ x ′ . We show that the equilibrium (x, x ′ ) in this case is Pareto-dominated by σ C . Consider the player who sent message m.
Case 3a: Consider a type u such that ϕ u ≤ x. Then we have where the right-hand side is the type u agent's payoff under strategy profile (x, x ′ ) and the left-hand side is her payoff under strategy profile σ C . The inequality follows from the observation that u RR ≥ u LR and F m ′ (x ′ ) ≤ 1 /2 by the fact that F m ′ (x ′ ) = x when (x, x ′ ) is an equilibrium. Case 3b: Now consider a type u with x < ϕ u ≤ 1 /2. Then we have where the first expression is the type u agent's payoff under strategy profile (x, x ′ ) and the last expression is her payoff under strategy profile σ C . The first inequality follows from u LL ≥ u RL and the second one from u LL ≥ u RR by the assumption of unambiguous coordination preferences given ϕ u ≤ 1 /2 and F m ′ (x ′ ) = x by (x, x ′ ) being an equilibrium and x < 1 /2. The inequality is strict if u LL > u RL or u LL > u RR . Case 3c: Finally, consider a type u with ϕ u > 1 /2. Then we have where the first expression is a u type's payoff under strategy profile (x, x ′ ) and the last expression is her payoff under strategy profile σ C . The first inequality follows from u RR > u LL ≥ u RL by the assumption of unambiguous coordination preferences and from The analysis for the player who sent message m ′ is analogous.

E.7.2 Proof of Theorem 3 (Multiple Players, Section E.3)
The "1 ⇒ 2" part is analogous to the proof of the "1 ⇒ 2" part of Theorem 1. The proof of the "3 ⇒ 1" part does not extend directly and has to be adapted as follows. The following lemma states that play is coordinated whenever all players send the same message. Proof. Let m ∈ supp (μ) and assume to the contrary that inf {u | µ u (m) > 0} < ξ (m) < sup{u | µ u (m) > 0}. Let x = ξ (m). We now show that the symmetric equilibrium in which all players use cutoff x after sending the identical message m, denoted by x = (x, . . . , x), is Pareto-dominated by σ L or σ R . There are two cases to be considered. Case 1: Suppose that x ≤ 1 /2. We now show that in this case the equilibrium x is Pareto-dominated by σ R .
Case 1a: Consider a type u ≤ x. Then we have where the left-hand side is the type u agent's payoff under strategy profile σ R and the right-hand side is her payoff under strategy profile x. The inequality follows from u 1 − (F m ( 1 /2)) n−1 ≥ 0 and F m ( 1 /2) ≥ F m (x) by the fact that F m is nondecreasing (as it is a cumulative distribution function). Note also that this inequality is strict for all u except for u = 0 in the case of x = 1 /2. Case 1b: Now consider a type u with x < u ≤ 1 /2. Then we have where the left-hand side is the type u agent's payoff under strategy profile σ R and the right-hand side is her payoff under strategy profile x. The inequality follows from the fact that given u ≤ 1 /2 we have that 1 − u ≥ u and therefore Note that this inequality actually holds strictly for all u. Case 1c: Finally, consider a type u > 1 /2. Then we have u > u (1 − F m (x)) n−1 , where the left-hand side is the type u agent's payoff under strategy profile σ R and the right-hand side is her payoff under x.
Case 2: Suppose that x ≥ 1 /2. The analysis is analogous to Case 1 if we replace σ R with σ L .
Proof. The proof of this lemma involves two steps. In the first step we show that a communicationproof equilibrium strategy σ is ordinal preference revealing, i.e., such that for any message m ∈ supp(μ), F m ( 1 /2) ∈ {0, 1}. We then use this to show that σ is mutual-preference consistent. Assume, first, that σ is a communication-proof but not ordinal preference-revealing equilibrium strategy. That is, suppose to the contrary that F m ( 1 /2) ∈ (0, 1). Then there are types u < 1 /2 as well as types u > 1 /2 who both send message m with positive probability. By Lemma 7 play after message pair (m, m) must be either L or R. If it is L then the equilibrium strategy σ L Pareto-dominates playing L, with a strict payoff improvement for all types u > 1 /2 (and unchanged payoffs for all types u ≤ 1 /2). If it is R then the equilibrium strategy σ R Pareto-dominates playing R, with a strict payoff improvement for all types u < 1 /2 (and unchanged payoffs for all types u ≥ 1 /2).
Given a communication-proof equilibrium strategy σ = (µ, ξ ), we can classify messages in the support of µ into two distinct sets, To show that a communication-proof equilibrium strategy σ = (µ, ξ ) is mutual-preference consistent, then consider any profile of types (u 1 , u 2 , . . . , u n ) such that u i < 1 /2 for all i ∈ {1, . . ., n}. They must each send a message in M L , which we denote by the profile m = (m 1 , . . . , m n ). Any play after message profile m that is not coordinated on L is now clearly Pareto-dominated (given that all types ≤ 1 /2) by playing the equilibrium strategy L. The case for a profile of types u i > 1 /2 for all players is proven analogously.
The following lemma shows that, in a communication-proof equilibrium strategy, agents never miscoordinate after observing any message profile.
Lemma 9. Every weakly communication-proof equilibrium strategy σ is coordinated.
Proof. Suppose that σ = (µ, ξ ) is a communication-proof equilibrium strategy. Given Lemmas 7 and 8 it only remains to prove that play under σ is coordinated even after mixed messages are sent, i.e., when there is at least one player who sends a message in M L and another player who sends a message in M R , where M L and M R are as defined in the proof of Lemma 8. Suppose that this is the case. Then let I ⊂ {1, . . ., n} be the set of all players who send a message m i ∈ M L . Let I c denote its complement. By Lemma 8 all i ∈ I c satisfy m i ∈ M R . Let x i = ξ (m i , m −i ) be the cutoff used by player i after observing message profile (m 1 , m 2 , . . ., m n ). Then by Lemma 8 we have x i ≤ 1 /2 for all i ∈ I and x i ≥ 1 /2 for all i ∈ I c . For this profile x = (x 1 , . . . , x n ) to be an equilibrium after the players observe message profile (m 1 , m 2 , . . . , m n ), we must have that for each i = 1, 2, . . ., n, the probability that player i's opponents coordinate their action on L conditional on them coordinating (on either L or R) is But then, all types of all players, after observing message profile (m 1 , m 2 , . . . , m n ), weakly (and some strictly) prefer to play σ C , which is a payoff identical in this case to a public fair coin toss to determine whether coordination should be on L or R. To see this, consider a player i who sent a message in M L (i.e., u i ≤ 1 /2, which implies that x i ≤ 1 /2) and consider the following two cases.
Case 1: Suppose that u i ≤ x i . Under the given strategy, this type's payoff is (1 − u i ) ∏ j =i F m j (x j ) with ∏ j =i F m j (x j ) ≤ 1 /2. The equilibrium strategy σ C yields to this type a payoff of 1 /2(1 − u i ) + 1 /2u i , which exceeds the former payoff, which contradicts the supposition that σ is communication-proof.
Case 2: Suppose that x i < u i ≤ 1 /2. Then, under the given strategy, this type's payoff is u i ∏ j =i 1 − F m j (x j ) . The equilibrium σ C yields to this type a payoff of 1 /2(1 − u i ) + 1 /2u i , which, by virtue of 1 − u i ≥ u i , again exceeds the former payoff, which contradicts the supposition that σ is communication-proof.
The analysis for a player who sent a message in M R is proven analogously.
To complete the proof of Theorem 1 for the case of many players, we need to prove that any communication-proof equilibrium strategy also has binary communication. The proof of this statement is analogous to the proof of Lemma 3 and therefore omitted.

E.7.3 Proof of Proposition 9 (Multiple Actions, Section E.2)
For the proof, two lemmas about approximating real numbers by rational numbers will be useful. The first lemma shows that any discrete distribution with at least three elements in its support can be approximated from below by a vector of rational numbers, such that the profile of differences (between the irrational exact probability and its rational approximation from below) is roughly uniform in the sense that no difference is larger than the half the sum of all the differences.
Lemma 10. Let p ∈ ∆(A) be a distribution satisfying |supp(p)| ≥ 3. Then there exists a function q : A → R + such that, for each 1 ≤ i ≤ k, q (a i ) is a rational number, q (a i ) ≤ p (a i ), and Proof. Let δ < min {p(a)/2 | a ∈ supp(p)}. As the rational numbers are dense in the reals, for each real numberp > δ , there exists a rational numberq ∈ (0,p) such thatp −q ∈ (( 9 /10)δ , δ ). Call thiŝ q a rational approximation ofp. For each a ∈ suppp, let q(a) be a rational approximation of p(a).
For each a ∈ supp(p) let q (a) = q (a) = 0. Then it follows that, for each 1 ≤ i ≤ k, q (a i ) is a rational number, and q (a i ) ≤ p (a i ). Finally we get, for each 1 ≤ i ≤ k, that where the first inequality follows directly from the definition of a rational approximation, the second one follows from the assumption that |supp(p)| ≥ 3, and the last one from the assumption that, for each a j ∈ supp(p), p(a j ) − q(a j ) > ( 9 /10)δ by the definition of a rational approximation.
Note that the closer δ is to zero, the better the rational approximation constructed in this proof. Note, however, that this does not matter in the proof of Proposition 9 below, which simply uses any (possibly quite rough) rational approximation.
The second lemma is utilized in the proof of Proposition 9 for the case where the distribution in question has exactly two elements in its support.
We now turn to the proof of Proposition 9. Let σ = (µ, ξ ) be a communication-proof equilibrium strategy of Γ A , M . We begin by showing that σ is same-message coordinated. Let m ∈ supp (μ) let and p ∈ ∆(A) be the distribution of play under σ conditional on message pair (m, m) being observed. Assume to the contrary that p (a) < 1 for each a ∈ A (i.e., that there is miscoordination).
Case I: Assume that |supp(p) ≥ 3|. Let q : A → R + be a rational approximation of p satisfying the requirements of Lemma 10. The fact that all q (a i )-s are rational numbers implies that there are l 1 , . . . , l k , n ∈ N, such that q (a i ) = l i /n for each i and l 1 + . . . + l k ≤ n. Consider the following equilibrium strategyσ = μ,ξ of the game induced after players observe message pair (m, m) with an additional communication round with the set of messagesM = m B,i,b | 1 ≤ B ≤ n, 1 ≤ i ≤ k, b ∈ {0, 1} . We let 1 ≤ B ≤ n denote a random integer used for a joint lottery, 1 ≤ i ≤ k denote the index of the player's preferred outcome (i.e., u i = max u j | 1 ≤ j ≤ k , and b ∈ {0, 1} denotes a random bit).
The message functionμ induces each agent to choose the indexes B and b randomly (uniformly, and independently of each other), and to choose i such that u i = max u j | 1 ≤ j ≤ k is her preferred outcome.
The action functionξ m B,i,b , m B ′ ,i ′ ,b ′ is defined as follows. LetB = (B + B ′ ) mod n be the sum of the random B-s sent by the players. Both players play action a j if l 1 + . . . + l j−1 ≤B < l 1 + . . . + l j .
IfB ≥ l 1 + . . . + l k , then both players play the action in {a i , a i ′ } with the smaller index if action if b = b ′ and the action with the larger index if b = b ′ . Strategyσ induces both players to coordinate on a random action with probabilityq ≡ q (a 1 ) + . . . + q (a k ) (and, conditional on that, the random action is chosen to be a j with probability q a j /q), and to coordinate on the preferred action of one of the two players (chosen uniformly at random) with probability 1 −q, which can be written as 1 −q = ∑ 1≤ j≤k p a j − q a j , by the fact that p is a probability distribution and, thus, ∑ 1≤ j≤k p a j = 1.
The proof thatσ is an equilibrium is analogous to the proof of Prop. 8 and thus omitted. The expected payoff that the original equilibrium σ yields to each type u = (u 1 , . . . , u k ) ∈ U in the game induced after observing (m, m) is max j p a j u j . The expected payoff thatσ induces for each type u is at least ∑ j q a j u j + 1 2 (1 −q) max j u j ≥ max j {q a j u j } + 1 2 max j u j ∑ j p a j − q a j .
Thus, the difference between the payoff ofσ and the payoff of σ for a type u is at least 1 2 max j u j ∑ j p a j − q a j − max j p a j u j − max j q a j u j ≥ 1 2 max j u j ∑ j p a j − q a j − 1 2 ∑ 1≤ j≤k p a j − q a j u j ≥ 0, where the first inequality is due to max j p a j u j − max j q a j u j = p (a l ) u l − max j q a j u j ≤ p (a l ) u l − q (a l ) u l , where l = argmax j p a j u j ; and the second inequality is due to q being a rational approximation of p as given by Lemma 10. This then implies that σ is CP-trumped byσ, which contradicts the supposition that σ is a communication-proof equilibrium.
Case II: We are left with the case of |supp(p)| = 2. Let supp(p) = a i , a j . Let q ∈ (0, 1) be the posterior probability of a player having a type u with u i ≥ u j , conditional on sending m. Let p ≡ p (a i ). By Lemma 11, there exists a rational number α ≡ k /n ∈ (0, 1) satisfying p − q /1 − q < α < p /q. Consider the following symmetric equilibriumσ = μ,ξ of the game induced after players observe message pair (m, m) with an additional communication round with the set of messagesM = {i, j} × {1, . . . , n}.
The first component of the message of each player is interpreted as her preferred coordinated outcome of a i and a j , and the second component is a random number between 1 and n. When following strategyσ the players send message component i if and only if u i ≥ u j , send a random number between 1 and n according to the uniform distribution, play a i after observing ((i, a) , (i, b)) for any numbers a and b, play a j after observing (( j, a) , ( j, b)) for any numbers a and b, play a i after observing ((i, a) , ( j, b)) if a + b < k mod n, and play a j after observing (a i , a) , a j , b if a + b ≥ k mod n.
Observe thatσ is indeed an equilibrium of the induced game, because following any pair of messages the players coordinate for sure, each agent with u i > u j (resp., u j > u i ) strictly prefers to report that her preferred outcome is a i (resp., a j ) as this induces her to coordinate on a i (resp., a j ) with a high probability of q + α (1 − q) (resp., 1 − q + (1 − α) q) instead of with a low probability of αq (resp., (1 − q) (1 − α)), and each agent is indifferent between sending any random number, as this has no effect on the probability of coordinating on a i (which is equal to α = k /n), given that her opponent chooses his random number uniformly as well.
Recall that the payoff of each type who follows σ in the game induced after observing (m, m) is equal to max u i p, u j (1 − p) . The payoff of each type u with u i ≥ u j in equilibriumσ is given by (q + α (1 − q)) u i + (1 − (q + α (1 − q))) u j > pu i + (1 − p) u j ≥ max u i p, u j (1 − p) , where the first inequality is implied by u i ≥ u j and p−q 1−q < α ⇔ p < q + α (1 − q). The payoff of each type u with u i < u j in equilibriumσ is given by where the first inequality is implied by q p > α ⇔ 1 − α > q−p q ⇔ (1 − q) + (1 − α) q > 1 − p and u i < u j . This implies that all types obtain a strictly larger payoff inσ (relative to the expected payoff of σ in the game induced after players observe message pair m, m), which implies thatσ Paretodominates σ , which contradicts the supposition that σ is communication-proof.
Next, we show that σ = (µ, ξ ) is mutual-preference consistent. For each i ∈ {1, . . . , k}, let U i ⊂ [0, 1] k be the set of types such that u i ≥ max j =i u j . Assume, first, that σ is not ordinal preferencerevealing. That is, suppose that there is a message m ∈ supp(μ) such that there are action indices i, j with i = j and µ u (m) > 0 for some u ∈ U i and some u ∈ U j . We have shown above that the play after players observe (m, m) must be coordinated on some action a l ∈ A. Now consider the following strategy with new message spaceM = {m i , m ¬i } in which players of type u ∈ U i send message m i , while all others send m ¬i and play is a l unless both players send message m i , in which case it is a i . This is an equilibrium strategy of the induced game after players observe (m, m) and it Paretodominates σ , a contradiction. This proves that a communication-proof equilibrium strategy σ must be ordinal preference-revealing.
Given a communication-proof equilibrium strategy σ = (µ, ξ ), we can classify messages in the support of µ into k distinct sets M i = M i (σ ) = {m ∈ supp (μ) | u ∈ U i } for each i = 1, . . . , k, where for each i, j with i = j M i ∩ M j = / 0 and k i=1 M i = supp(μ). To show that a communication-proof equilibrium strategy σ is mutual-preference consistent, consider a message pair (m, m ′ ) with m, m ′ ∈ M i for some i = 1, . . . , k. Since σ is ordinal preferencerevealing, the updated support of types who observe either m or m ′ is then in U i . But then any joint action distribution that the two players could play after (m, m ′ ) is Pareto-dominated by the equilibrium of playing action a i . E.7.4 Proof of Proposition 10 (Extreme Types, Section E.6) Proof of Proposition 10. Any strategy σ that is coordinated, mutual-preference consistent, and has strongly binary communication can be characterized by its left tendency (see Section 3) as follows. Under such a mutual-preference consistent strategy players indicate whether their type is below or above 1 /2. This means that there are two disjoint sets of messages, M L and M R , such that players of type u ≤ 1 /2 send a message in M L and players of type u > 1 /2 send a message in M R . Also whenever two players both send messages in M L they then play L and if both send messages in M R they both play R. The left tendency α = α σ then describes how moderate players coordinate if one of them sends a message from M L and the other sends a message from M R . The left tendency α is then the probability that the two players coordinate on L (through random message selection within the respective sets of messages), while 1 − α is then the remaining probability that they coordinate on R.
To prove the "only if" part, consider an arbitrary left tendency of α ∈ [0, 1]. Then consider a player of type 1 /2 who needs to be indifferent between sending a message in M L and sending a message in M R for this strategy to be an equilibrium strategy. If she sends a message in M L she coordinates on L whenever either her opponent sends a message in M L (which happens with probability F( 1 /2)), or her moderate opponent sends a message in M R (which happens with probability F(1) − F( 1 /2)) and the joint lottery yields the outcome L (which happens with probability α). By contrast, she coordinates on R whenever her opponent sends a message in M R and the joint lottery yields the outcome R (which happens with probability 1 − α). Therefore, her expected payoff from sending a message in M L is given by 1 2 F 1 2 + 1 2 α F(1) − F 1 2 + 1 2 (1 − α) 1 − F 1 2 . Similarly, her expected payoff from sending a message in M R is given by 1 2 αF 1 2 + 1 2 (1 − α) F 1 2 − F (0) + 1 2 1 − F 1 2 . Clearly, her expected payoff from sending a message in M L is equal to her expected payoff from sending a message in M R iff α = F(0)/ (F(0) + (1 − F(1))), as required. This proves the "only if" direction. To prove the "if" direction, we need to show that a coordinated and mutual-preference consistent strategy with strongly binary communication and with a left tendency of α = F(0)/ (F(0) + (1 − F(1))) is both an equilibrium and a communication-proof strategy. To prove the latter condition the same arguments as in the relevant parts of the proof of the "if" direction of Theorem 1 apply directly. It remains to show that such a strategy is an equilibrium strategy. We have already shown that the message function is a best reply to itself and the action function. All that remains to prove is that the action function is a best reply to the given strategy. It is easy to see that playing L is the optimal strategy when both players send a message in M L and thus are of type u < 1 /2. In doing so, they coordinate on their most preferred outcome with probability one. Similarly, playing R after two messages in M R is clearly optimal. Now suppose that one player sends a message in M L and the other player sends a message in M R . There are two possibilities. Either they are now supposed to both play L (unless they are an extreme R type) or they are now supposed to both play R (unless they are an extreme L type). Consider first the person who sends a message in M L and therefore be of type u < 1 /2. Suppose that the two players are expected to coordinate on R. Since her opponent sent a message in M R , our M L sender expects R with a probability of one (as all M R senders are of type u > 1 /2, which excludes L-dominant action types). But then our M L sender of any type u > 0 has a strict incentive to play R as well. Now suppose that the two players are expected to coordinate on L. Then our M L sender expects her opponent to play L with a probability of (F(1) − F( 1 /2)) / (1 − F( 1 /2)), which is the conditional probability of an R-type to be moderate, which by assumption is greater than or equal to 1 /2. Playing L in this case is therefore optimal for all M L senders. That the M R sender has the correct incentives in her choice of action after any mixed-message pair (one in M R and one in M L ) is proven analogously and requires the assumption that F(0)/F( 1 /2) ≤ 1 /2.
We now show when one can implement a coordinated, mutual-preference consistent strategy with binary communication with the required left tendency of α = F(0)/ (F(0) + (1 − F(1))). This implementation requires two things. First, α needs to be a rational number, and second, the message space needs to be sufficiently large. 22 Note that in the case of a symmetric distribution F (i.e., F (0) = 1 − F (1)) the required left tendency is exactly α = 1 /2 and the required strategy is σ C , as described in Section 3. More generally, let α = k/n, and assume that |M| ≥ 2n. Denote 2n distinct messages as m L,1 , . . . , m L,n , m R,1 , . . ., m R,n ∈ M, where we interpret sending messages m L,i as expressing a preference for L and sending messages m R,i as expressing a preference for R and choosing at random the number i from the set of numbers {1, . . ., n} in the joint lottery described below. We arbitrarily interpret any message m ∈ M \ m L,1 , . . ., m L,n , m R,1 , . . . , m R,n as equivalent to Thus, µ α induces each agent to reveal whether her preferred outcome is L or R, and to uniformly choose a number between 1 and n. In the second stage, if both agents share the same preferred outcome they play it. Otherwise, moderate types coordinate on L if the sum of their random numbers modulo n is at most k, and coordinate on R otherwise. Extreme types play their strictly dominant action.