Random utility coordination games on networks

Peski, Marcin Article Random utility coordination games on networks Theoretical Economics Provided in Cooperation with: The Econometric Society Suggested Citation: Peski, Marcin (2025) : Random utility coordination games on networks, Theoretical Economics, ISSN 1555-7561, The Econometric Society, New Haven, CT, Vol. 20, Iss. 2, pp. 583-622, https://doi.org/10.3982/TE5653 This Version is available at: https://hdl.handle.net/10419/320294 Standard-Nutzungsbedingungen: Die Dokumente auf EconStor dürfen zu eigenen wissenschaftlichen Zwecken und zum Privatgebrauch gespeichert und kopiert werden. Sie dürfen die Dokumente nicht für öffentliche oder kommerzielle Zwecke vervielfältigen, öffentlich ausstellen, öffentlich zugänglich machen, vertreiben oder anderweitig nutzen. Sofern die Verfasser die Dokumente unter Open-Content-Lizenzen (insbesondere CC-Lizenzen) zur Verfügung gestellt haben sollten, gelten abweichend von diesen Nutzungsbedingungen die in der dort genannten Lizenz gewährten Nutzungsrechte. Terms of use: Documents in EconStor may be saved and copied for your personal and scholarly purposes. You are not to copy documents for public or commercial purposes, to exhibit the documents publicly, to make them publicly available on the internet, or to distribute or otherwise use the documents in public. If the documents have been made available under an Open Content Licence (especially Creative Commons Licences), you may exercise further usage rights as specified in the indicated licence. https://creativecommons.org/licenses/by-nc/4.0/ Theoretical Economics 20 (2025), 583–622 1555-7561/20250583 Random utility coordination games on networks Marcin P˛eski Department of Economics, University of Toronto We study static binary coordination games with random utility played on networks. In equilibrium, each agent chooses an action only if a fraction of her neighbors choosing the same action is higher than an agent-specific i.i.d. threshold. Afuzzy convention xis a profile where (almost) all agents choose the high action if their threshold is smaller than xand the low action otherwise. The randomutility (RU) dominant outcome x∗is a maximizer of an integral of the distribution of thresholds. The definition generalizes Harsanyi–Selten’s risk dominance to coordination games with random utility. We show that, on each sufficiently large and fine network, there is an equilibrium that is a fuzzy convention x∗.Onsome networks, including a city network, all equilibria are fuzzy conventions x∗. Finally, fuzzy conventions x∗are the only behavior that is robust to misspecification of the network structure. Keywords. Random utility, coordination games, networks. JEL classification.C7. 1. Introduction An individual’s behavior in social or economic situations is often positively influenced by similar decisions made by their friends, acquaintances, or neighbors. An important recent example is the post-Covid era mask-wearing: some people wear masks to protect themselves or others, others do not wear them because of inconvenience or personal beliefs, and many, including the author of this paper, are positively affected by how many people around them wear masks. Other examples include the decision to maintain a neat front yard, to obey speed limits or tax laws, to engage in criminal activity, or to adopt a technology with network externalities. A large literature has established conditions under which a particular behavior becomes a convention: it is adopted by everyone (see Young (1993), Ellison (1993), Morris (2000), among many others). These results typically assume that agents have almost identical preferences, and show that a contagion-like process, possibly initiated by a small perturbation to the preferences, leads to uniformity. Marcin P˛eski: [email protected] The paper has previously been circulated under the title “Fuzzy conventions.” I am very grateful to Stephen Morris and Philip Neary for detailed comments, Jacopo Perego for discussion, Denise Cruz for the main example, and an anonymous referee for insightful suggestions. S. Morris’s comments greatly influenced the proof of Theorem 1. I gratefully acknowledge financial support from the Insight Grant of the Social Sciences and Humanities Research Council of Canada. ©2025 The Author. Licensed under the Creative Commons Attribution-NonCommercial License 4.0. Available at https://econtheory.org.https://doi.org/10.3982/TE5653 584 Marcin P˛eski Theoretical Economics 20 (2025) At the same time, completely uniform behavior is rarely observed in the real world. Even in situations which clearly involve positive externalities, there will often be interactions in which neighbors make opposite choices. An obvious reason is that individuals are different and their tastes and unique circumstances play just as important role in determining their decisions as the behavior of their neighbors. The goal of this paper is to study coordination games with heterogeneous payoffs with the following questions in mind. Is there a useful and coherent way in which heterogeneous-behavior equilibria can be understood as conventions? Can we explain how people coordinate on a convention? Are some conventions more natural than others? For this purpose, we study a random utility binary coordination game played in a network. Each network node contains a single agent who interacts with her neighbors. We are interested in the asymptotic of equilibrium behavior as the network becomes arbitrarily large, and importantly, as the graph becomes sufficiently fine, that is, the weight of the largest neighbor in the neighborhood of each agent becomes sufficiently small. The latter ensures that no single individual has a disproportionate impact on another, and it is the first key assumption in our model. Each agent chooses a binary (high or low) action, and the relative gain from the action is increasing in the fraction of neighbors who make the same choice. Each agent has an individual threshold τi, with the interpretation that the high action is the agent’s best response if and only if more than fraction τiof her neighbors do the same. Thresholds are distributed i.i.d., with distribution given by cdf P(.). The independence assumption is the second key assumption of our model and it is appropriate for some but not all applications. An example of cdf P(.)is drawn on Figure 1; for each x,P(x)is the fraction of the population with a threshold equal to or smaller than x. Importantly, unlike in the coordination literature mentioned above, the level of preference heterogeneity captured by P(.)is nonzero and nondisappearing. A conceptual contribution of this paper is a definition of a convention appropriate for large random utility coordination games. Define a fuzzy convention xas an action profile where almost all agents choose the high action if τi<xand the low action if τi>x.Ifxis an atom of distribution P(.), the definition allows for randomization at τi=x. Our assumptions on networks imply that, in a fuzzy convention, almost all agents observe approximately P(x)fraction of their neighbors choosing the high action. This definition captures individual heterogeneity of actions, with two types of uniformity: (a) almost all agents choose their action as the same function of their threshold and (b) almost all agents experience almost the same average behavior of their neighbors. For a fuzzy convention xto be an equilibrium, the choice in (a) must be a best response, which implies that it is an intersection with 45◦line, x=P(x). Figure 1illustrates with multiple candidate solutions. Next, we define a particular fixed point. Let random utility-dominant,orRUdominant,outcomex∗be a solution to the maximization problem x∗∈argmax x x  0y−P−1(y)dy.(1) Theoretical Economics 20 (2025) Random utility coordination games 585 Figure 1. Threshold cdf P. The definition implies that P(x∗)=x∗. Geometrically, the maximized objective on the right-hand side is equal to the area above the 45◦line and below function P(blue area on Figure 1) minus the area below the 45◦line and above P(red area). The RU-dominant outcome depends on the threshold distribution, and generically, it is unique. Two observations about special cases of our model motivate this definition further. First, (1)is equivalent to a formula from Morris and Shin (2006), where it is derived as a potential function for the continuum population version of the model where agents treat the entire population as their neighbors. Second, if the threshold distribution is concentrated on a single outcome (i.e., all agents’ preferences are identical), then the RU-dominant outcome is equivalent to the standard risk-dominant outcome of a 2 ×2 coordination game (Harsanyi and Selten (1988)). The results of the paper show that fuzzy convention x∗is the “right” solution: Informally, all networks have an equilibrium that is a fuzzy convention x∗, and on some networks, there are no other equilibria. More precisely, first, we show that for each network that is sufficiently large and fine, with a probability close to 1 (i.e., for almost all realizations of thresholds), there is an equilibrium that is a fuzzy convention x∗. The proof relies on a characterization of coordination games as potential games. (For an arbitrary network, a potential function is necessarily different than the one in (1).) Such games are introduced in Monderer and Shapley (1996), where it is shown that any profile that is a local maximizer of the potential function is an equilibrium of the underlying game. In the proof, we show that, regardless of the structure of the network, with a probability close to 1, the global maximizer of the potential function is a fuzzy convention x∗.The difficult part of the proof is to derive a version of a uniform law of large numbers and to show that it guarantees that action profiles that are not fuzzy conventions x∗cannot maximize the potential. 586 Marcin P˛eski Theoretical Economics 20 (2025) Second, we show there exist networks, where with a large probability, all equilibria are fuzzy conventions x∗. An example of such a network is a city-like network, where agents live on a 2-dimensional grid lattice and they interact with agents in a sufficiently large neighborhood. The idea of the proof is to show that, for each profile with an average behavior that is not RU-dominant, contagion-like best response dynamics would bring the behavior close to x∗. The proof uses an idea from Blume (1995a)andLee and Valentinyi (2000)(seealsoMorris (2000)) to show how a contagion wave spreads across lattice networks. There are two novel difficulties relative to earlier literature. First, unlike in the earlier literature, the agent preferences are random and heterogeneous. Instead of a binary wave (where there is a sharp separation between risk-dominated and risk-dominant regions), the contagion wave here has multiple values as it describes the fraction of agents that adopt the high action. Second, we must compare the likelihood that a favorable configuration of payoff shocks may initiate such a wave, with the likelihood that such a wave would not be stopped by an unfavorable configuration of payoff shocks. The problem with the latter is the reason why the 1-dimensional network of Ellison (1993) is not a good example for the result and a 2- (or more) dimensional lattice is needed. The two results together suggest that RU-dominant outcome x∗is the only prediction of aggregate equilibrium behavior that is network-independent. We formalize this through a definition that is inspired by Kajii and Morris (1997): Consider an analyst who predicts agents’ behavior but she is not certain whether her model correctly specifies the network interactions, or whether the agents know the entire network. We say that the behavior is robust to misspecifications if, even if she or the agents are wrong, her prediction is close to some equilibrium of the true model. Our results imply that fuzzy convention x∗is the only robust prediction. 1.1 Literature review This is the first paper with predictions about behavior in static complete-information random-utility games on networks. The model and techniques used draw from two strands of the literature: random utility games on networks and models of learning (or evolution) in games. The first random-utility coordination model was introduced in Granovetter (1978). Granovetter works with a complete (continuum) network, where the agents’ payoffs depend on the average behavior in the entire population. A large literature generalized Granovetter’s model to networks. Typically, each agent is a single node on a network and adopts the new behavior (e.g., wears a mask) only if the fraction of her neighbors doing the same is larger than her threshold. Many papers, like Watts (2002)orLópez-Pintado (2008) (among many others) study Granovetter’s model on an Erd˝ os–Renyi style of a random graph with heterogeneous degree distribution. The limitation of such models is that they do not capture many important aspects of real-world networks, like clustering, or overlapping neighborhoods, which are known to play important role in coordination or contagion phenomena. Theoretical Economics 20 (2025) Random utility coordination games 587 Jackson and Yariv (2007) (see also Galeotti, Goyal, Jackson, Vega-Redondo, and Yariv (2010)) analyzes a Bayesian equilibrium, where the agents choose their action without knowing the thresholds of their neighbors. This assumption improves the model’s tractability as the agent’s behavior does not depend on the individual thresholds of her neighbors. At the same time, this assumption is not satisfactory if the equilibrium is to be interpreted as a long-term process as each agent may change her behavior when she observes the actions of her neighbors. This is the first key difference from our model, where an equilibrium is a steady-state behavior after the thresholds are realized and actions are chosen. Because our model is a static, complete information equilibrium for a given realization of thresholds, it is also much more difficult to analyze. Further, because the neighbors in the Bayesian equilibrium of Jackson and Yariv (2007)areselected at random, the neighborhood structure looks like a random graph. Like other random-graph-based models, there are typically multiple equilibria. In contrast, in this paper, we are serious about the topology of the network and explain an important role of overlapping neighborhoods that cannot be captured in random graphs models. The results of this paper are closely related to the literature on evolutionary learning and contagion in networks. Evolutionary game theory (Kandori, Mailath, and Rob (1993), Young (1993), Blume (1993), Newton (2021), and many others) studies the longrun behavior of perturbed best response processes, where agents commit mistakes with a small probability, and instead of choosing a best response, take some other action. A major contribution of this literature is a demonstration of a contagion phenomenon. Ellison (1993)(seealsoEllison (2000)) shows that a best response may spread a risk-dominant action from a small initial set of deviators to the rest of a 1-dimensional lattice network. Blume (1995b)andLee and Valentinyi (2000) extend this observation to higher-dimensional lattices. Morris (2000) describes general properties of networks for which Ellison’s contagion wave exists. Morris (2000) also shows that risk-dominated actions cannot spread through a best response process regardless of the geometry of the network. A strand of the literature studies evolutionary equilibrium selection in games with heterogeneous populations. For instance, Friedman (1991) describes a general framework with multiple continuum populations choosing actions and receiving payoffs and studies evolutionary steady states of continuous time adjustment dynamics. More closely related to this paper is Neary (2012), which studies a similar model to ours but with two payoff shocks (more precisely, two subpopulations of deterministic size) and agents located on a complete graph. The paper presents conditions under which the evolutionary dynamics of Kandori, Mailath, and Rob (1993) selects a fuzzy convention, that is, an equilibrium where members of different subpopulations play different actions. Neary and Newton (2017) study general payoff shocks and presents a sufficient condition under which the logit dynamics of Blume (1993) select a fuzzy convention. Our current results (specifically, Theorems 1and 2) are related, but with some key differences. First, here, we are interested in static equilibria instead of a dynamic adjustment process. The evolutionary literature is subject to the criticism that one may need to wait for a very long time before reaching a stochastically stable outcome (Ellison (1993)). That criticism does not apply to our static model. Second, the previous 588 Marcin P˛eski Theoretical Economics 20 (2025) papers study games with homogeneous payoffs and a behavior that is subject to small and disappearing perturbations: small and disappearing shocks in the case of Ellison (1993)orBlume (1995b), and a finite and small fraction of society modifying their actions in Lee and Valentinyi (2000)orMorris (2000). Instead, the payoff shocks in our model are significant, and as a result, we are serious about heterogeneity. The nontrivial payoff shocks make our model more difficult to analyze, but they also render it closer to reality. Third, the evolutionary literature results show convergence to Harsanyi and Selten (1988)’s risk-dominance. Here, due to payoff heterogeneity, we need a new solution concept in the form of the RU-dominance. We show that the RU-dominance becomes equivalent to the risk-dominance when payoffs are homogeneous. Finally, the network topology plays an important role in both evolutionary models and in the current paper. In evolutionary models, the network affects the time for the coordination on the riskdominant outcome. However, it does not affect the final outcome: one of the key results of this literature is that risk-dominant coordination is (uniquely) stochastically stable on all networks (Peski (2010)). In our case, similarly to Lee and Valentinyi (2000)andMorris (2000), the network topology affects the equilibrium outcome. In a recent contribution, Leister, Zenou, and Zhou (2022) study coordination games with a fixed network and a fixed (not random) threshold distribution. The paper works with arbitrary networks. To deal with a possible multiplicity of equilibria, they use global games as an equilibrium selection device. The authors develop an algorithm to compute the equilibrium adoption. The outcome of the algorithm depends on the details of payoff heterogeneity and how they interact with the topology of the network. In contrast, in our paper, the assumption that thresholds are randomly and independently drawn from the same distributions allows us to separate the effects of the payoff distributions and the topology of the network. 2. Numerical example Although our results are asymptotic, the coordination on RU-dominant outcome as well as the role of the networks can be demonstrated through simulations in a numerical example. We compare the behavior under two threshold distributions. In both cases, the high action is strictly dominant for 30% of the population and the low action is strictly dominant for another 30%. Under P1, the remaining 40% plays the high action only if at least 0.55 of their neighbors do the same. Under P2, the remaining 40% plays the high action only if at least 0.4 of their neighbors do the same. The distributions are drawn in the top row of Figure 2. If, like in Granovetter (1978), the population is a continuum, and all agents play against the entire population, the equilibrium average behavior can be found as a fixed point of P(.), that is, an intersection of P(.)with the 45◦line. In both cases, there are two stable equilibria: Awith 0.3 and Bwith 0.7 fractions playing high. (In each case, there is also an unstable equilibrium in between.) For each distribution, only one of these outcomes is RU-dominant—Ain the case of distribution P1and BinthecaseofP2. Instead, consider a population of agents living on one of two networks. Both networks have ∼60,000 agents and each agent has, on average, ∼120 neighbors. Theoretical Economics 20 (2025) Random utility coordination games 589 Figure 2. Monte-Carlo simulations of average equilibrium behavior in the lowest (blue, “\” hatch areas) and the highest equilibria (yellow, “/” hatch areas). The distributions substantially overlap (brown color) in the last row, corresponding to the city network. •In a random graph (Erd˝ os and Rényi (1959)), neighbors are randomly selected from the population. •In a “city” network, people are located on a two-dimensional grid. Each agent neighborhood is a square of agents with a side equal to 11, centered at the agent. We use Monte Carlo simulations to estimate the probability distributions of average equilibrium behavior. In each simulation, we draw i.i.d. thresholds for all agents. For each realization of thresholds, we find the highest and lowest equilibria. Such equilibria are well-defined for binary coordination games. For example, to find the highest equilibrium, we start with a profile where all agents play the high action, and then run the best response process until none of the agents wants to change their action. Next, for each equilibrium, we compute the average equilibrium behavior. By combining average behaviors in two equilibria across different threshold realizations, we obtain the Monte Carlo estimates. These distributions for each network, each threshold distribution, and each equilibrium type (the lowest is marked with blue, “\” hatch areas and the highest with yellow, “/” hatch areas) are plotted in the two bottom rows of Figure 2. Because both distributions are highly concentrated around 0.3 (i.e., A) and 0.7 (i.e., B) values, for clarity, we only show regions around these two values. 590 Marcin P˛eski Theoretical Economics 20 (2025) There is a significant difference between random and city networks. In the random graph, the lowest and the highest equilibria correspond to the lowest (A)andhighest(B) equilibria from the population model of Granovetter (1978), regardless of the threshold distribution. This is not unexpected as a random graph with a relatively large number of agents is a good approximation of the continuum model. On the city network, the range of equilibrium behaviors is much smaller and it depends on a threshold distribution. Under P1, the lowest and the majority of realizations of the highest equilibria are concentrated around A.UnderP2, the average behavior in the highest and lowest equilibria is essentially equal to B. In other words, for a significant majority of threshold realizations, all equilibria on the city network have aggregate behavior consistent with the RU-dominant prediction. The goal of the rest of the paper is to explain this pattern. 3. Model 3.1 Model We are studying agents living in the nodes of a network. The network is defined as an undirected weighted graph with weights gij =gji ≥0fori,j≤Ng,whereNgis the size of the network. The weights can be interpreted as a frequency of interactions between two agents and we assume that gii =0. Let gi=jgij >0 for each agent i.Eachagenti has a threshold τidrawn i.i.d. from probability distribution P. Each network g, and each realization of thresholds τdefines a complete information static game G(g,τ). Each agent chooses a binary action ai∈{0, 1}and uses it in each interaction. The payoff in interaction with agent jis equal to ui(ai,aj,τi)=aiaj−aiτi,andthetotalpayoff of agent iin all (weighted) interactions is equal to jgij ui(ai,aj,τi). For each action profile a,letβa=(βa i)be a profile of average neighborhood fractions of agents who play action 1, that is, βa i=1 gijgij aj. An action profile is a Nash equilibrium if all agents best respond, or alternatively, if each agent plays action 1 (resp., 0) if the average action in their neighborhood is strictly larger (resp., smaller) than their threshold, that is, for each i, 1τi<β a i≤ai≤1τi≤βa i.(2) The model is strategically equivalent to general random-utility binary-action coordination games on networks.1The notion of equilibrium is a standard, static equilibrium of a complete information game. Although it is convenient to assume that agents know the thresholds and the network structure of the entire society, this assumption is neither realistic nor necessary. For the interpretation of the equilibrium, it is sufficient that agents observe the actions of their neighbors. Because ours is a coordination game, we 1A general model is as follows: For each agent iand j,i’s payoff from interaction with agent jis equal to u(ai,aj,εi),whereai,aj∈{0, 1}are actions and εiis a random shock to agent i’s utility drawn from some distribution F. Assume that, for each ε, (ε):=u(1, 1, ε)+u(0, 0, ε)−u(1, 0, ε)−u(0, 1, ε)>0. To translate this model to the threshold model, for each x,letτi=1 (ε)(u(1, 0, εi)−u(0, 0, εi)). Theoretical Economics 20 (2025) Random utility coordination games 597 (Because 1{.≤x∗}is not Lipschitz, the lemma is applied to a Lipschitz approximation— the details are left for the Appendix.) Second, take an arbitrary equilibrium profile that is not ε-fuzzy convention of x∗. Because of (2)and(3), we get ε≤1 Ngai−1τi≤x∗ ≤1 Ng i1βa i≤x∗1τi∈βa i,x∗+1βa i≥x∗1τi∈βa i,x∗. By Lemma 1, with a large probability, the following bound holds: 1 Ng iPβa i−Px∗≥1 2ε. (11) Third, we estimate the potential for such a profile a. Applying Lemma 1once more, we obtain V(a;τ)=1 2 i,j gij aiaj−giaiτi =1 2 i,j gi1τi≤βa i1τj≤βa j−gi1τi≤βa iτi ≈1 2 i,j gij Pβa iPβa j−gi βa i  0 ydP(y). Because 2P(βa i)P(βa j)≤P(βa i)2+P(βa j)2, the potential of ais not larger than ≤1 2 i,j gij Pβa i2−gi βa i  0 ydP(y)= i giνβa i. By the remark at the end of Section 3.3,unlessβa i=x∗, the above is strictly smaller than the potential of a∗. Hence, together with the estimate of potential for profile a∗,the bound (11) implies that an arbitrary equilibrium profile that is not ε-fuzzy convention of x∗cannot maximize potential. Finally, recall that any potential maximizer must be an equilibrium. It follows that the potential maximizer must be ε-fuzzy convention of x∗. 5. RU-dominant selection In the previous section, we showed that all sufficiently fine networks have equilibria that are fuzzy conventions x∗. Here, we show that there are networks where, with a large probability, all equilibria are fuzzy conventions x∗: 598 Marcin P˛eski Theoretical Economics 20 (2025) For each η>0, the proof constructs a “city” network, where agents live on a twodimensional grid and interact with other agents who live around them. The network is parameterized with Mand m.ThereareM2agents living on square [0, M m]2⊆R2at fractional points (k m,l m)for k,l=1, ,M. Any two agents iand jare connected, gij =1, if the (Euclidean) distance between them is no larger than 1. To avoid separately dealing with border cases, we assume that all distance calculations are done mod M m,which transforms the square [0, M m]2into a torus. Theorem 2. Suppose that x∗is the strictly RU-dominant outcome and that either (a) x∗∈(0, 1)and 0<P (0)≤P(1)<1,(b)x∗=1and P(0)>0,or(c)x∗=0and P(1)< 1.Foreachη>0,ifmand M mare sufficiently large, then with probability 1−η, each equilibrium on (M,m)city network is η-fuzzy convention x∗. The theorem says that there exist networks where all equilibria are fuzzy conventions x∗, or that all equilibria have a form identified by Theorem 1. We emphasize that the theorem makes a statement about static,complete information game equilibria. At the same time, the proof relies on a dynamic technique of contagion waves (Ellison (1993), Morris (2000)). We show that if an action profile is, in some sense, higher (resp., lower) than fuzzy convention x∗, then best response dynamics will push the profile below (resp., above) x∗. This shows that the original profile could not have been an equilibrium. We describe the intuition behind the proof, including the relation to the maximization problem, below. If P(0)>0(resp.,P(1)<1), then with a positive probability, there are agents for whom action 1 (resp., 0) is strictly dominant and it is played in any equilibrium. The only assumption of the theorem is that there is a positive probability of such agents. The role of such agents is similar to the role of initial infectors in Lee and Valentinyi (2000) and Morris (2000) or the role of small probability mistakes in evolutionary models. The city network is an example of a two-dimensional lattice. The proof could easily extend to K>2 dimensional lattices (but, as we explain below, not to K=1). After we describe the proof, we point to the properties of multidimensional lattices that are important for the proof. Extending the theorem to other networks is beyond the goals of this paper. 5.1 Contagion on line Next,wedescribetheintuitionfortheproof.Weassumethatx∗=0andP(1)<1. We start with the intuition behind the contagion argument. It is useful initially to work with a toy version of the line network from Ellison (1993) (the general argument does not work on a line and it requires at least two-dimensional lattices). Suppose that agents are distributed uniformly along a line at discrete and equally spaced locations. Each location contains a continuum population of mass 1. The populations in locations iand jare connected with each other, with weights that depend only on the distance gij =gi−j=:gj−i. We assume there are no connections between agents in the same location, that is, g0=0, and the weights are normalized so that gd=1. Finally, we assume that there are no connections between agents at distance larger than d:gi−j=0 for |i−j|>d. Theoretical Economics 20 (2025) Random utility coordination games 599 Figure 4. Contagion wave. Take an action profile a0such that agents in locations i∈[−2d,0 ]play action 0 and all other agents play 1. In our model (but not its continuum toy version), assumption P(1)<1 implies that there is a positive probability that a contiguous group of agents have 0 as a strictly dominant action. If the line network is long enough, the existence of agroupof2dagents who play 0 for sure can be guaranteed with a probability arbitrarily close to 1. Going back to the toy line with a continuum of agents in each location, consider a revision process in which agents in all locations apart from i≥0 switch to their myopic best responses. Complementarities imply that they can switch at most once, and if they do, they switch from action 1 to 0. Figure 4illustrates the first two stages of such a process. In the first stage, actions are changed by agents in locations i>0 for whom action 0 is strictly dominant, as well as high-threshold agents in locations i∈[0, d]for whom 0 is a best response given a0. In the second stage, additional agents in locations i≤2dmay change actions, and so on. The process will continue until a stable point where no more agents i≥0 want to switch to 0. Denote the fraction of agents who play 1 in location iin stage nas an iand the limit fraction as limnan i=ai. Due to the payoff complementarities, profiles an ifor each nand aimust be increasing in i. In this toy version, the continuum law of large numbers allows us to express the fraction of agents for whom 1 is a best response given profile aas P(dgdai+d).Given that ais the limit of the best response dynamics, we have, for each location i≥−2d, ai≤P d gdai+d. Taking the inverse, we obtain P−1(ai)≤ d gdai+d= j d≥j−i gd(aj+1−aj), where the equality is due to a discrete version of the integration-by-parts formula and the fact that ai≥0 for each i. After multiplying by ai+1−ai≥0, and summing up across all locations i,weget  i P−1(ai)(ai+1−ai)≤ i,j d≥j−i gd(ai+1−ai)(aj+1−aj). (12) 600 Marcin P˛eski Theoretical Economics 20 (2025) The left-hand side of the inequality is approximately equal to a 0P−1(y)dy when the distance between locations is small and for large m. To compute the right-hand side, notice that we can switch the roles of iand jin the summation without affecting its value. Together with the fact that d≥j−igd+d≥i−jgd=gd=1, we get  i,j d≥j−i gd(ai+1−ai)(aj+1−aj) =1 2 i,j d≥j−i gd+ d≥i−j gd(ai+1−ai)(aj+1−aj) =1 2 i,j (ai+1−ai)(aj+1−aj)=1 2a2 =1 2a2= a  0 ydy. Putting the two sides together, inequality (12) implies that a  0y−P−1(y)dy ≥0. If a>0, this contradicts the fact that x∗=0 is the unique maximizer of the integral on the right-hand side of (4). Thus, in the limit of best response revision process, it must be that all locations play ai=0. The contagion argument extends from a line to higher-dimensional lattices due to an elegant argument from Blume (1995b)(seealsoLee and Valentinyi (2000)andMorris (2000)). The idea is that if the initial group is sufficiently large, we can approximate it using a set with a smooth (i.e., low curvature) boundary. Then we can analyze the spread of the contagion wave behavior in the direction that is normal to the boundary. This trick turns the problem into a one-dimensional one, and the above argument applies. 5.2 Obstacles Although the continuum assumption is useful in explaining the intuition, the argument needs to be modified for our model. For example, the assumption ignores a positive probability of a contiguous group of “bad” agents for whom 1 is the strictly dominant action. If sufficiently large, such a group of “bad” agents will stop the best response revisions towards action 0 and block the contagion wave (see the left panel of Figure 5). “Bad” sets cannot be eliminated or avoided in the one-dimensional “line” network. However, “bad” sets are intuitively less likely to block the contagion wave on higherdimensional lattices (see the right panel of Figure 5). The reason is that to block the wave, the “bad” sets would have to be arranged so as to surround it. We show that, on a two-dimensional lattice, if mand M mare sufficiently large, the likelihood of “bad” sets surrounding the initial infectors is very small. Theoretical Economics 20 (2025) Random utility coordination games 601 Figure 5. Obstacles to the contagion wave. 5.3 Proof summary More generally, without the continuum assumption, the argument behind contagion waves must work with finite laws of large numbers. Below, we sketch the main ideas of howwedoit.ThedetailsoftheproofcanbefoundinAppendixB. The lattice is divided into large and small cubes so that the number of large cubes in the lattice is very large, each large cube contains a very large number of disjoint neighborhoods, each neighborhood contains a very large number of small cubes, and each small cube contains a very large number of agents (see Figure 6). These numbers are chosen so that the following series of claims holds: (1) The number of agents in a small cube and the number of small cubes in a neighborhood are sufficiently large, so that the fraction of shared agents and the fraction of shared small cubes in the neighborhoods of any two agents iand jis well approximated by the area of the intersection of two 1-radius circles with centers at iand j(Lemma 3). (2) The size of each small cube is sufficiently large so that, for each small cube, with a probability close to 1, the empirical distribution of payoff shocks within the cube is close to the true distribution. We say that a small cube is (γ-)bad if, for some fraction x, the average best response action of the agents within the cube is (γ- )larger than P(x). Agents in bad cubes may tilt toward higher best responses than a statistical agent. Agents in a small cube that is not bad are well approximated by the continuum assumption in the following sense: the average best response in the small cube is not higher than P(β),whereβis the average “belief” (i.e., the average neighborhood action) for members of the cube. (3) A large cube is good if it contains no bad small cubes. The ratio of the size of a small cube (i.e., the number of agents within each small cube) to the number of small cubes in a large cube is sufficiently large, so that the probability pthat the large cube is good is arbitrarily close to 1. Alargecubeisextraordinary if it contains only agents for whom 0 is the strictly dominant action. Extraordinary cubes play the role of initial infectors. The number of large cubes is sufficiently large, so that the probability that an extraordinary largecubeexistsisarbitrarilycloseto1. 602 Marcin P˛eski Theoretical Economics 20 (2025) Figure 6. Lattice division. (4) Two large cubes are connected if they share a wall. The number of large cubes is sufficiently large, and the probability pthat a large cube is not good is sufficiently small, so that there exists a giant component of good large cubes—a set of good large cubes that contains almost all large cubes on the lattice and such that all of its elements are connected with each other by paths of good large cubes that share a wall. This argument is the content of Lemma 7and it relies on definitions and results from the percolation theory (Bollobás and Riordan (2006)). (a) First, we show that each connected set Scan be surrounded by a connected “boundary” ∂S that isolates set S(and, possibly, some other large cubes) from the remaining large cubes. The total number of large cubes isolated away from set Sis not larger than |S|2. (On a two-dimensional lattice, the worst-case scenario bound comes from elements of set Sarranged in a way that surrounds an interior proportional in size to the square of its perimeter.) (b) For a collection of connected sets S1,,SJthat are not connected with each other, the giant connected component that omits all sets Sjcontains all but at most |Sj|2large cubes. (c) Let S1,,SJbe the collection of all maximally connected collections of large bad cubes. We estimate the expected value of |Sj|2as proportional to the number of all large cubes multiplied by the probability pthat a single large cube is bad (Lemma 5). An application of the Markov inequality shows that, if pis sufficiently small, the giant connected component that contains only good cubes contains a fraction of all large cubes that is arbitrarily close to 1. Theoretical Economics 20 (2025) Random utility coordination games 603 (5) Using the ideas from Blume (1995b), we show that if the curvature of the twodimensional contagion wave is sufficiently small relative to the curvature of an individual neighborhood, the contagion wave will spread, as long as its path contains only good small cubes (Lemma 9). Putting it together, the contagion wave is going to spread through a vast majority of the giant connected component of good large cubes, and thus a vast majority of the lattice. Hence, with a large probability, the average action in the largest equilibrium on a sufficiently large two-dimensional lattice is close to x∗. 5.4 Key properties of the city network We summarize the above discussion by identifying four properties of (M,m)-city network that play key roles in the proof. (1) Large number of connections mallows us to approximate the empirical distribution of thresholds in an agent’s neighborhood by the model distribution P.This approximation forms a basis for the continuum model discussed in Section 5.1. (2) Large network: The population must be sufficiently large to ensure that, for each action, with a high probability, there is a sufficiently large number of agents for whom this action is strictly dominant. Such agents start the contagion argument and they play a similar role as initial infectors in Lee and Valentinyi (2000)orMorris (2000). In the city network, we require that M mis sufficiently large. (3) Slow neighborhood growth: For the contagion argument of Section 5.1 to hold, the size of neighborhoods must grow sufficiently slowly (see Morris (2000)forthe definition and properties). (4) Percolation property: The contagion cannot be obstructed by the obstacle phenomenon described in Section 5.2. Using the language introduced above, the good set of cubes must contain a large connected component of the graph. It is not immediately obvious how to formalize the last property in a simple way. (A nonsimple way is to assume that the thesis of Lemma 4from the Appendix must hold.) We leave this task for future research. 6. Equilibrium selection In this section, we point out two equilibrium selection theories that select fuzzy convention x∗as the unique solution for random utility coordination games on networks. 6.1 Evolutionary stability The proof of Theorem 1shows that fuzzy convention x∗is, with a large probability, a global maximizer of a potential function for the coordination game. Recall that global maximizers of the potential function are selected in complete information static coordination games by two different equilibrium selection theories: robustness to incomplete 604 Marcin P˛eski Theoretical Economics 20 (2025) information (Ui (2001)) and stochastic stability under logistic dynamics (Blume (1993), Blume (2018)). 6.2 Robust behavior Next, we explain that fuzzy convention x∗is the only behavior that is robust to incomplete information about the network. The idea is parallel to the definition of robustness to incomplete information from Kajii and Morris (1997). We take a perspective of a researcher/analyst who observes a large population of agents and attempts to predict individual behavior αi(τi)∈[0, 1],whereαi(τ)is the probability of playing action 1, as a function of individual thresholds τi. The researcher understands that the agents play a coordination game with their neighbors on some large and fine network and she understands the parameters of the game, but she does not necessarily understand the details of the network topology. She would like her prediction to be robust to a misspecification of the network. Definition 1. A threshold behavior (αi(.))iis robust to the misspecification of the network if and only if, for each η,thereexistsd>0, such that for each network g,ifd(g)<d, with probability at least 1 −η(over the realization of thresholds τi), there exists an equilibrium ai∈{0, 1}of the network game G(g,τ)such that 1 Ng i≤Ngai−αi(τi)≤η. To interpret the definition, notice that threshold behavior (αi(.))iis networkindependent: each agent’s action depends on their own threshold and not to whom they are connected and what their neighbors are doing. If the behavior is robust to misspecification, it prescribes a best response behavior for a great majority of agents, whatever is the true network of interactions, and whether the agents know the network or not. In other words, the behavior is approximately an equilibrium on the true network regardless of whether the researcher or the agents know the true network. Recall that the 0-fuzzy convention of x∗is a network-independent profile where agents play 1 if and only if their threshold is smaller than x,a∗(τi)=1(τi≤x∗). Theorem 3. Suppose that x∗is the strictly RU-dominant outcome. Then a threshold behavior αis robust to misspecification of the network if and only if it is the 0-fuzzy convention of x∗. The above result shows that playing a∗is the only profile that is robust to misspecification of the network. Proof. The “if” direction follows from Theorem 1. The “only if” direction follows from Theorem 2. Theoretical Economics 20 (2025) Random utility coordination games 605 7. Conclusions This paper presented a theory of behavior in random utility binary coordination games on large networks. We showed that on some networks, with a large probability, large coordination games have essentially a unique equilibrium. Because this equilibrium exhibits micro-, but not macro-level heterogeneity of behavior, we refer to it as a fuzzy convention. The average behavior in such a convention corresponds to a natural extension of risk-dominance from deterministic to random-utility coordination games. We also showed that, with a large probability, all sufficiently fine networks (i.e., networks where each agent has sufficiently many neighbors), coordination on the special fuzzy convention of RU-dominant outcome is always an approximate equilibrium, regardless of the network structure. The paper leaves many important questions unanswered. First, how do the results extend to small-degree networks? Second, in real applications, both macroand microlevel heterogeneity are observed. Likely, the latter is due to systematic differences in preferences (perhaps differences in the threshold distributions) across different parts of the network. Can the two idiosyncratic and systematic differences be combined in a single model? Third, and related, can real-world data be used to estimate parameters of the model, like the threshold distribution function P(.)? We leave these questions for future research. Appendix A: Proof of Theorem 1 A.1 Proof of Lemma 1 Define a distance on the space of (mixed) profiles: For any a,b∈[0, 1]N,let d(a,b)=    1 g2 ig2 i(ai−bi)2. Recall that B={βa:ais action profile}is the space of neighborhood fractions. For each δ>0, let N(δ,B)be the covering number of B, that is, the smallest cardinality nof a list of profiles b1,,bn∈Bsuch that, for each b∈B,thereisl≤nso that d(b,bl)≤δ. Lemma 2. There exists a universal constant c<∞such that, for each δ>0,andeach network g, N(δ,B)≤exp1 δ2cw∗2d(g)N. Proof. We will use Sudakov’s minoration inequality (Theorem 7.4.1 from Vershynin (2018)), which provides an upper bound on the covering number via the expectation of a certain Gaussian process. For this, let Zifor each agent ibe an i.i.d. standard normal random variable. For each (possibly mixed) profile a∈A, define Xa=1  i g2 i i giaiZi. 606 Marcin P˛eski Theoretical Economics 20 (2025) For any two profiles a,b∈A, E(Xa−Xb)2=    1 g2 i E i gi(ai−bi)Zi2 =    1 g2 i i gi(ai−bi)2=d(a,b). Given the definition and the above property, Sudakov’s minoration inequality implies that, for some universal constant c1>0 (i.e., a constant that is independent of parameters and the current problem), logN(δ,B)≤c1Esup b∈B Xb2 δ2. We compute Esup b∈B Xb=Esup a∈A Xβa=E⎛ ⎜ ⎜ ⎜ ⎜ ⎝ sup a∈A 1  i g2 i i giZi1 gigij aj⎞ ⎟ ⎟ ⎟ ⎟ ⎠ =1  i g2 i Esup a∈A i ai j gij Zj≤1  i g2 i E i j gij Zj ≤2 π 1  i g2 i i j g2 ij , where the last inequality is due to a bound on the expectation of the absolute value of the normal variable gij Zjvia its standard deviation σi=jg2 ij . Because jg2 ij ≤d(g)g2 i and (igi)2≤N2w∗2g2 min ≤Nw∗2g2 i,wehave logN(δ,B)≤2 πc1 1 δ2 1  i g2 i id(g)gi2 d(g)≤1 δ22 πc1w∗2d(g)N. We proceed with the proof of Lemma 1. For the first inequality, suppose fis KLipschitz. Fix ε>0andδ>0sothatδ=1 12K√w∗ε. Find δ-cover b1,,bnof B. Because n≤N(δ,B), Lemma 2implies that Probsup l≤n i gifτi,bl i− i giEf., bl i≥1 2εgi Theoretical Economics 20 (2025) Random utility coordination games 613 (a) Wcontains at least a fraction (1−γ)of cubes, |W|≥(1−γ)|Gb|, (b) Wis connected as a subset of the cube network, (c) if c∈Gbis γ-bad, then db(c,c)>3Rfor each c∈W(in particular, each cube in W is γ-good), and (d) Wcontains a cube c0such that each cube csuch that d(c,c0)≤Ris extraordinary. We show that large good sets of cubes exist with high probability. Lemma 4. For each γ,ρ>0,andR<∞,thereexistmγ,ρ,R>0, and for each m>m γ,ρ,R, there exist Mγ,ρ,R(m)such that, if m≥mγ,ρ,Rand M≥Mγ,ρ,R(m)then, if Gis an (M,m)- lattice, b=ρm,andGbis the associated cube network, then Pthere exists (γ,R)-good set W⊆Gb≥1−γ. B.2.1 Intermediate results We need two intermediate results. The first result provides a bound on the size of the largest connected component of the graph obtained from the network of cubes after removing a group of smaller and connected sets of cubes. Lemma 5. Suppose that {S1,,SJ}is a collection of connected subsets of Gbsuch that Si∪Sjare not 2-connected for any i= j. Then there is a connected subset V⊆Gb\!Sj such that |Gb\V|≤j|Sj|2. Proof. First, observe that for each connected set Ssuch that |S|2<|Gb|there is a set Sand a loop (i.e., a path with the same beginning and ending) cS 0,,cS n=c0of cubes cS l/∈Ssuch that •S⊇Sand |S|≤|S|2,and •loop cS 0,,cS ntightly surrounds set Sand separates it from the rest of the graph: |{c:d(c,S)=1}|⊆{cS l}⊆|{c:d(c,S)≤2}|. This observation follows from the Jordan curve theorem and from the fact that each connected set Ssuch that |S|2<|Gb|can be contained in a |S2|-element “square” of cubes such that the set outside the square is connected. For each set Sifrom the hypothesis of the lemma, find loop ciand set S ias in the observation above. We will show that set Gb\!S jis connected, which will conclude the proof of the lemma. Take any two cubes c,c∈Gb\!S j, and an arbitrary path c= c0,,cn=cbetween them. We will modify this path so that it avoids each set Si.For each i, either the existing path avoids set S i, or it intersects it. Find li 0=min{l:d(cl,Si)= 1}and li 1=max{l:d(cl,Si)=1}. Then replace the interval cli 0,,cli 1of the path with the path from cli 0to cli 0along path ci. The new path avoids set S i. Because the modified part of the path stays within 2-distance of set S i, the modification does not create new intersections with other sets S j. After possibly modifying the path for any i,weobtaina path between cand cthat avoids each set S i.Thus,setGb\!S jis connected. 614 Marcin P˛eski Theoretical Economics 20 (2025) The second result provides an upper bound on the number of different r-connected sets of cubes. Lemma 6. The number of r-connected sets in Gbof cardinality nisnotlargerthan22n(2r+ 1)n|Gb|. Proof. We first find an encoding for each r-connected tuple. Let mrbe the size of the r-neighborhood of an element of Gb.Thenmr≤(2r+1)2.Considertuples (s1,(l2,,ln),(k2,,kn)) such that s1∈Gb,ki∈{1, .., mr},andli≤iand li≤ljfor each 2 ≤i≤j. We show that each r-connected set can be encoded as one of the above tuples in such a way that any two different r-connected sets must have a different encoding. Let e:Gb→{1, ,|Gb|}be an enumeration of set Gb. For each s∈Gb,letes:{s:d(s,s)= 1}→{1, ,4 }be the enumeration of the immediate neighborhood of sthat has the same ranking in the neighborhood as enumeration e. Choose s1=argmins∈Se(s).Suppose that s1,si−1are chosen for 1 <i<n. For each x∈S\{s1,,si−1},letl(x)= mind(x,sl)=1land let it equal ∞if the set is empty. Then l(x)<iforatleastonex.Let k(x)=esl(x)(x). Choose si=arg min lexicograpically,x∈Sl(x),k(x), so as to minimize lexicographically (l(x),k(x)) among all x∈S\{s1,,si−1}.Letli= l(si)and ki=k(si). We derive an upper bound on the number of encoding tuples. Say that a sequence li,,lnis (i,m)-sequence if it is increasing, lj<jfor each j,andli=i−m−1. Let S(i,m)denote the number of different (i,m)-sequences. It is easy to see that S(i,m)= m+1  p=0 S(i+1, p), where S(n,m)=1. We check by induction on ithat S(i,n)≤22(n−i)+m. The number of choices for s1is not larger than |Gb|.Bytheabove,thenumberof (2, 0)-sequences is not larger than 22(n−2). The number of choices of k2,,knis not larger than (2r+1)n−1. It follows that the total number of encodings, and hence the number of connected sets is not larger than 22n(2r+1)n|Gb|. B.2.2 Proof of Lemma 4Lemma 4follows from the following two results. The first result establishes the existence of a large connected component that is far from bad cubes. Let Bγ={c∈Gb:cis γ-bad}be the (random) set of γ-bad cubes. Lemma 7. For each γ>0and R<∞,thereexistsbγ,R>0such that if b>b γ,R,then P∃W0⊆Gb,st.W0is connected, W0≥(1−γ)Gb,dbW0,Bγ≥5R≥1−1 4γ. Theoretical Economics 20 (2025) Random utility coordination games 615 Proof.Letpγ>0 be the probability that a cube is γ-bad. Due to the Dvoretzky– Kiefer–Wolfowitz–Massart inequality, the probability that a cube cis γ-bad is bounded by pγ≤Ce−2b2γ2 for some universal constant C. Let S0 1,,S0 nbe the smallest division of the set of bad cubes Bγ=!S0 iinto sets that are 11R-connected and such that S0 i∪S0 jare not 11R-connected for i=j.LetX= |S0 i|2. We compute the expected value of X.Letmn=(22n(11R+1)n|Gb|)be an upper bound on the cardinality of all 11R-connected sets (obtained from Lemma 6). Then EX≤ n≥1 n2mnpn γ≤|Gb| n≥1 2n22n(6R+1)npn γ =|Gb|8(11R+1)pγ 1−8(11R+1)pγ . Let S1 i⊇S0 ibe the smallest connected set such that sets S1 i∪S1 jare not 11Rconnected for i= jandsuchthat|S1 i|≤11R|S0 i|. Such sets can be constructed by connecting elements of S0 iby a path inside the intersection of the 11R-neighborhood of the two sets. Let Sibe the 5R-neighborhood of set S1 i. Clearly, sets Siare disjoint (and separated by R). Because each 5R-neighborhood of an element of a set S1 ihas no more than (11R+ 1)2|S1 i|cubes, the cardinality of Siis at most (11R+1)2|S1 i|≤(11R+1)3|S0 i|. Let W0be the largest connected component of Gbthat does not contain elements of sets Si. By construction, each set Siis connected, but sets Si∪Sjare not 2-connected. By Lemma 5, the cardinality of W0is at least |Gb|−4(11R+1)6X. By Markov’s inequality, PW0≥(1−γ)Gb≤P4(11R+1)6X≤γGb ≤4(11R+1)6EX γGb≤1 γ 32(11R+1)7pγ 1−8(11R+1)pγ . Assume that bγ,R>0 is large enough so that for each b>b γ,R,1 γ 32(11R+1)7Ce−2b2γ2 1−8(11R+1)Ce−2b2γ2≤ 1 4γ. Say that cube c∈GRis an extraordinary center if all cubes in U(c,R)are extraordinary. Lemma 8. There exists Kγ,R<0large enough so that if M b>K γ,R,then P"∃W⊆Gb,st.W⊇W0,Wis connected, db(W,Bγ)≥3R and Wcontains an extraordinary center #≥1−γ, where W0inside the probability satisfies the conditions from Lemma 7. 616 Marcin P˛eski Theoretical Economics 20 (2025) Proof. Recall that K=M bis the number of cubes. If Kis divisible by (2R+1),we can find a grid of cubes GR⊆Gbsuch that any two c,c∈G,d(c,c)=2Rand Gb= !c∈GRU(c,R). Because the U(c,R)neighborhoods are disjoint, |Gb|=|GR|(2R+1)2, where (2R+1)2is the size of each neighborhood. For simplicity, the rest of the arguments rely on the divisibility assumption. The argument is easily modified for the case when the divisibility does not hold (and band M bare sufficiently large). Let W0be the (random) set from Lemma 7.LetW1=!cU(c,R+1)and W= !cU(c,2R+1).Thend(W,Bγ)>2R. Because for each c∈U(c,r)there is a path between cand cthat is inside set U(c,r),Wis connected. We show that |GR∩W1|≥(1−γ)|GR|. On the contrary, suppose that |GR\W1|> γ|GR|.ThenA=!c∈GR\WU(c,R)⊆Gb\W0.Moreover,|A|>γ|GR|(2R+1)2=γ|Gb|. However, this contradicts |Gb\W0|≤γ|Gb|. Let q>0 be the probability that a cube cis an extraordinary center. Then q≥ P(0)(2R+1)2b2.Letq∗be the probability that cube cis an extraordinary center, conditional on c∈W1. Because being in c∈W1provides no other information about the distribution of taste shocks apart from cis not γ-bad and γ-bad cubes are not extraordinary,itmustbethatq∗≥q. Similarly, conditional on c,c∈W1,ifcand care separated by 2R+1, the events that the two are extraordinary centers are independent. Hence, the probability that none of the cubes in c∈GR∩W1is an extraordinary center is at most 1−q∗|GR∩W1|≤1−P(0)(2R+1)2b2(1−γ)K2(2R+1)−2 ≤e−(1−γ)Kγ,R(2R+1)−2P(0)(2R+1)2b2 . If Kis sufficiently large, the above is smaller than 1 4γ. To conclude the proof of the lemma, we set mγ,ρ,R>1 ρbγ,Rand then Mγ,ρ,R(m)≥ ρmKγ,R. B.3 Proof of Theorem 2 Below, we will show the following lemma. Lemma 9. For each ε>0, there exists sufficiently small γ,ρ>0, and sufficiently large R>0so that if b=ρm,Wis a (γ,R)-good set in the network of cubes Gb,andais an equilibrium profile, then for each i∈c∈W,βa i≤x∗+ε. Together with Lemma 4, Lemma 9shows that for each ε>0, if mand M mare sufficiently large, with probability of at least 1 −ε,ifais an equilibrium profile, then βa i≤x∗+εfor all agents ibut a ε-fraction of the population (i.e., all members of the “good” set W). A similar argument shows that βa i≥x∗−εfor elements of an analogously defined “good” set (with the appropriate modification of what good and extraordinary cubes are). Together, the two arguments show that, with probability of at least 1 −2ε, for each agent in the good set, the agent’s average neighborhood behavior is within εof x∗.All Theoretical Economics 20 (2025) Random utility coordination games 617 such agents, if they have a threshold outside interval [x∗−ε,x∗+ε], will choose the best response as in 0-fuzzy convention x∗profile ax∗. Finally, choose εsmall enough so that P(x∗+ε)−P(x∗−ε)≤1 4η. Then, if the network is sufficiently large, the probability that the fraction of agents with threshold τi∈[x∗−ε,x∗+ε]is larger than 1 2ηis smaller than ε. Take ε=1 4η. Then, with a probability of at least 1 −η,atmostη 2agents have thresholds in the ε−interval, and at most 2ε=η 2agents observe equilibrium neighborhood behavior that is outside the ε−interval. All the other agents choose the same behavior as in profile ax∗. Proof. We divide the proof of the lemma into two steps. Preparation. Find ε0>0, such that σ∗=max a≥x∗+ε 2 a  x∗+ε0P−1(y)−ydy > 0. The existence of such ε0∈(0, ε 2)comes from the definition of x∗as the unique maximizer of a x∗(y−P−1(y))dy.Letδρbe a fraction of neighbors of iwho are not members of a cube that is fully contained in the neighborhood of i. It is easy to see that δρ→0as ρ→0. Let abe an equilibrium profile. For each cube c, define ac=1 |c| j∈c ajand βc=1 |c| j∈c βa j. Then |βc−βa i|≤δρ,and βc≤δρ+|c| B(i,1 ) c⊆B(i,1) ac. (16) If cube cis γ-good, then ac=1 |c| i∈c 1τi<β a i≤1 |c| i∈c 1{τi<β c+δρ}≤P(βc+δρ)+γ. (17) From now on, assume that W⊆Gbis (γ,R)-good. If db(c,W)≤3R,thencubecis γ-good. Define C0=c:∀cdc,c≤R=⇒ ac≤x∗+ε0. For each i∈C0, the average behavior in all the cubes fully contained in the neighborhood of iis ≤x∗+ε0, which, together with (16), implies that βa i≤x∗+ε0(1−δρ)+δρ≤x∗+ε. The last inequality holds when ρis sufficiently small so that δρ≤ε 2. Hence, to establish our claim, it is enough to show that W⊆C0. 618 Marcin P˛eski Theoretical Economics 20 (2025) Notice that C0cannot be empty as it contains at least one extraordinary cube. For each a>x ∗+ε 2, define d(a)=min c∈W:ac≥adb(c,C0)≥R, where the value is ∞if the set over which the distance is minimized is empty. On the contrary to our claim, suppose that there is a cube c∈W0such that ac>a> x∗+ε 2. Then there exists a>x ∗+ε 2such that d(a)<∞. Find a∗≥x∗+ε0such that d(a∗)≤2Rand d(a∗+1 R)≥d(a∗)+1. Such a∗exists: otherwise, if for each asuch that d(a)≤2R,d(a+1 R)≤d(a)+1, then d(a+1)≤2R, which is impossible (as there is no cube with the action average strictly larger than 1). Contagion wave.Noticethatactakes discrete values a∈A={0, 1 |c|,,1 },where|c| is the size of a cube. Let ak=k |c|be the enumeration of set A∩{a:a≥x∗+ε 2}. For each such cube c, and each i∈c,(16)implies βc≤δρ+|c| B(i,1 ) c⊆B(i,1) ac ≤δρ+ a∈A ac⊆B(i,1 ):ac=a B(i,1 )/c ≤δρ+x∗+ε0+ k (ak+1−ak)c⊆B(i,1 ):ac≥a B(i,1 )/c ≤δρ+δR,ρ+x∗+ε0+ k (ak+1−ak)1−fd(ak)−db(c,C0), where the third inequality is a consequence of a discrete version of the integration by parts (i.e., xi(yi−yi+1)=(xi+1−xi)yi+1), and the fourth one is due to Lemma 3, where δR,ρ→0asRis sufficiently large and ρis sufficiently small. Let δ1 R,ρ=δρ+δR,ρ. Additionally, for each al∈A,al≤a∗, find a cube csuch that db(c,C0)=dR(al)<2R and ac≥al. Using the above inequality and (17), we obtain P−1(al−γ)≤P−1(ac−γ)≤βc+δρ ≤δ1 R,ρ+x∗+ε0+ k (ak+1−ak)1−fd(ak)−d(al). Let k∗=max{k:ak≤a∗}. Then the right-hand side is not larger than ≤δ1 R,ρ+x∗+ε0+ k≤k∗ (ak+1−ak)1−fd(ak)−d(al) + k>k∗:ak≤a∗+ε 10 (ak+1−ak)1−fd(ak)−d(al) + k:ak>a∗+ε 10 (ak+1−ak)1−fd(ak)−d(al) Theoretical Economics 20 (2025) Random utility coordination games 619 ≤δ1 R,ρ+x∗+ε0+1 R+ k≤k∗ (ak+1−ak)1−fd(ak)−d(al), due to the second term in the first line being not larger than ε 10 , and the third term being equal to 0 (as f(d(ak)−d(al)) ≥f(1)=1). Let =a∗−(x∗+ε0). Multiplying by (al+1−al)and summing across l≤k∗,we obtain  l≤K∗ P−1(al−γ)(al+1−al) ≤δ1 R,ρ+1 R+x∗+ l≤K∗ k≤K∗ (ak+1−ak)(al+1−al)1−fdR(al)−dR(ak) =δ1 R,ρ+1 R+x∗+1 2 l,k≤K∗ (ak+1−ak)(al+1−al) =δ1 R,ρ+1 R+x∗+ε0+1 22 ≤δ1 R,ρ+1 R+ a∗  x∗+ε0 ydy. To obtain the equality, we use the fact that fis balanced. Because P−1(.−γ)∈[0, 1]and al+1−al=1 |c|, the left-hand side of the above inequality is smaller than a∗  x∗+ε0 P−1y−γ−1 |c|dy ≥ a∗−γ−1 |c|  x∗+ε0−γ−1 |c| P−1(y)dy. Assuming that bis large enough so that 1 |c|≤γ, the above is not smaller than a∗ x∗+ε0(P−1(y)−y)dy −2γ. Putting it back into the main inequality, we obtain a∗  x∗+ε0P−1(y)−ydy ≤δ1 R,ρ+1 R+2γ. If γ,ρ>0 are sufficiently small and Rsufficiently large, δ1 R,ρ+1 R+2γ<σ ∗.Thecontradiction shows that W⊆C0, which concludes the proof of the lemma. Appendix C: Proof of Theorem 3 For each η>0, define Pη=P(x:|x−x∗|≤η)as the probability that the threshold realization is within ηof x∗.IfPdoes not have an atom at x∗, then we can choose ηδsuch 620 Marcin P˛eski Theoretical Economics 20 (2025) that Pηδ≤1 30 δ. Assume w.l.o.g. that ηδ≤δ.Let Tδ=$τ:1 Nτi:τi−x∗≤ηδ≤1 3δ%. The law of large numbers implies that for sufficiently high N,Prob(Tδ)≥1−δ. Fix threshold profile τ∈Tδ.LetI0={i:|τi−x∗|≤ηδ}. Suppose that ais 1 3ηδ-fuzzy convention x∗.LetI(g)={i:|βa i−x∗|>1 3ηδ}be the set of agents that is an equilibrium in game G(g,τ).LetI=I0∩I(g).Then 1 N|I|≤2 3δ. For each i/∈I,either •τi>x ∗+ηδand βa i≤x∗+1 3ηδ, which implies ai=a∗ i=0, or –τi<x ∗−ηδand βa i≥x∗−1 3ηδ, which implies ai=a∗ i=1. Hence, for any i/∈I,ai=a∗ i. This concludes the proof of the theorem. References Blume, Lawrence E. (1993), “The statistical mechanics of strategic interaction.” In Games and Economic Behavior, volume 5, 387–424, Elsevier. [0587,0591,0604] Blume, Lawrence E. (1995a), “The statistical-mechanics of best-response strategy revision.” Games and Economic Behavior, 11, 111–145. [0586] Blume, Lawrence E. (1995b), “The statistical mechanics of best-response strategy revision.” In Games and Economic Behavior, volume 11, 111–145, Elsevier. [0587,0588,0600, 0603] Blume, Lawrence E. (2018), “Population games.” In The Economy as an Evolving Complex System II, 425–460, CRC Press. [0604] Bollobás, Béla and Oliver Riordan (2006), Percolation. Cambridge University Press. [0602] Ellison, Glenn (1993), “Learning, local interaction, and coordination.” Econometrica: Journal of the Econometric Society, 1047–1071. [0583,0586,0587,0588,0591,0598] Ellison, Glenn (2000), “Basins of attraction, long-run stochastic stability, and the speed of step-by-step evolution.” In The Review of Economic Studies, volume 67, 17–45, WileyBlackwell. [0587] Erd˝ os, Paul and Alfréd Rényi (1959), “On random graphs. I.” Publicationes Mathematicae, 6, 290–297. [0589] Friedman, Daniel (1991), “Evolutionary games in economics.” Econometrica: Journal of the Econometric Society, 637–666. [0587] Galeotti, Andrea, Sanjeev Goyal, Matthew O. Jackson, Fernando Vega-Redondo, and Leeat Yariv (2010), “Network games.” In The Review of Economic Studies, volume 77, 218–244, Wiley-Blackwell. [0587,0591] Granovetter, Mark (1978), “Threshold models of collective behavior.” American Journal of Sociology, 83, 1420–1443. [0586,0588,0590,0591,0593] Theoretical Economics 20 (2025) Random utility coordination games 621 Harsanyi, John C. and Reinhard Selten (1988), “A general theory of equilibrium selection in games.” In MIT Press Books,volume1.TheMITPress.[0585,0588,0592] Jackson, Matthew O. (2010), Social and Economic Networks. Princeton University Press, Princeton, NJ. [0594] Jackson, Matthew O. and Leeat Yariv (2007), “Diffusion of behavior and equilibrium properties in network games.” American Economic Review, 97, 92–98. [0586,0587,0591] Kajii, Atsushi and Stephen Morris (1997), “The robustness of equilibria to incomplete information.” Econometrica, 65, 1283–1309. [0586,0604] Kandori, Michihiro, George J. Mailath, and Rafael Rob (1993), “Learning, mutation, and long run equilibria in games.” Econometrica: Journal of the Econometric Society, 29–56. [0587] Lee, In Ho and Akos Valentinyi (2000), “Noisy contagion without mutation.” In The Review of Economic Studies, volume 67, 47–56, Wiley-Blackwell. [0586,0587,0588,0591, 0598,0600,0603] Leister, C. Matthew, Yves Zenou, and Junjie Zhou (2022), “Social connectedness and local contagion.” In The Review of Economic Studies, volume 89, 372–410, Oxford University Press. [0588] López-Pintado, Dunia (2008), “Diffusion in complex social networks.” In Games and Economic Behavior, volume 62, 573–590, Elsevier. [0586] Monderer, Dov and Lloyd S. Shapley (1996), “Potential games.” Games and Economic Behavior, 14, 124–143. [0585,0594] Morris, Stephen (2000), “Contagion.” In The Review of Economic Studies, volume 67, 57–78, Wiley-Blackwell. [0583,0586,0587,0588,0598,0600,0603] Morris, Stephen and Hyun Song Shin (2006), “Heterogeneity and uniqueness in interaction.” In The Economy as an Evolving Complex System, III: Current Perspectives and Future Directions, volume 3, 207, Oxford University Press, London. [0585] Mossel, Elchanan, Allan Sly, and Omer Tamuz (2015), “Strategic learning and the topology of social networks.” Econometrica, 83, 1755–1794. [0594] Neary, Philip R. (2012), “Competing conventions.” Games and Economic Behavior, 76, 301–328. [0587] Neary, Philip Ruane and Jonathan Newton (2017), “Heterogeneity in preferences and behavior in threshold models.” Available at SSRN 3035289. [0587] Newton, Jonathan (2021), “Conventions under heterogeneous behavioural rules.” The Review of Economic Studies, 88, 2094–2118. [0587] Peski, Marcin (2010), “Generalized risk-dominance and asymmetric dynamics.” In Journal of Economic Theory, volume 145, 216–248, Elsevier. [0588,0591] 622 Marcin P˛eski Theoretical Economics 20 (2025) Ui, Takashi (2001), “Robust equilibria of potential games.” Econometrica, 69, 1373–1380. [0604] Vershynin, Roman (2018), High-Dimensional Probability: An Introduction With Applications in Data Science. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge. [0605,0607] Watts, Duncan J. (2002), “A simple model of global cascades on random networks.” In Proceedings of the National Academy of Sciences, volume 99, 5766–5771, National Acad Sciences. [0586] Young, H. Peyton (1993), “The evolution of conventions.” Econometrica: Journal of the Econometric Society, 57–84. [0583,0587] Co-editor Simon Board handled this manuscript. Manuscript received 29 March, 2023; final version accepted 30 September, 2024; available online 1 October, 2024.