The Role of Compatibility in the Diffusion of Technologies  Through Social Networks  Nicole Immorlica  Microsoft Research  Redmond WA  nickle@microsoft.com  Jon Kleinberg  Dept. of Computer Science  Cornell University, Ithaca NY  kleinber@cs.cornell.edu  Mohammad Mahdian  Yahoo! Research  Santa Clara CA  mahdian@yahoo-inc.com  Tom Wexler  Dept. of Computer Science  Cornell University, Ithaca NY  wexler@cs.cornell.edu  ABSTRACT  In many settings, competing technologies - for example,   operating systems, instant messenger systems, or document   formatscan be seen adopting a limited amount of compatibility with one   another; in other words, the difficulty in using multiple technologies  is balanced somewhere between the two extremes of impossibility  and effortless interoperability. There are a range of reasons why  this phenomenon occurs, many of which - based on legal, social,  or business considerations - seem to defy concise mathematical  models. Despite this, we show that the advantages of limited   compatibility can arise in a very simple model of diffusion in social  networks, thus offering a basic explanation for this phenomenon in  purely strategic terms.  Our approach builds on work on the diffusion of innovations in  the economics literature, which seeks to model how a new   technology A might spread through a social network of individuals who  are currently users of technology B. We consider several ways of  capturing the compatibility of A and B, focusing primarily on a  model in which users can choose to adopt A, adopt B, or - at an  extra cost - adopt both A and B. We characterize how the   ability of A to spread depends on both its quality relative to B, and  also this additional cost of adopting both, and find some surprising  non-monotonicity properties in the dependence on these   parameters: in some cases, for one technology to survive the introduction  of another, the cost of adopting both technologies must be balanced  within a narrow, intermediate range. We also extend the framework  to the case of multiple technologies, where we find that a simple  This work has been supported in part by NSF grants   CCF0325453, IIS-0329064, CNS-0403340, and BCS-0537606, a  Google Research Grant, a Yahoo! Research Alliance Grant, the  Institute for the Social Sciences at Cornell, and the John D. and  Catherine T. MacArthur Foundation.  model captures the phenomenon of two firms adopting a limited  strategic alliance to defend against a new, third technology.  Categories and Subject Descriptors  J.4 [Social and Behavioral Sciences]: Economics    1. INTRODUCTION  Diffusion and Networked Coordination Games. A fundamental  question in the social sciences is to understand the ways in which  new ideas, behaviors, and practices diffuse through populations.  Such issues arise, for example, in the adoption of new technologies,  the emergence of new social norms or organizational conventions,  or the spread of human languages [2, 14, 15, 16, 17]. An active line  of research in economics and mathematical sociology is concerned  with modeling these types of diffusion processes as a coordination  game played on a social network [1, 5, 7, 13, 19].  We begin by discussing one of the most basic game-theoretic  diffusion models, proposed in an influential paper of Morris [13],  which will form the starting point for our work here. We describe  it in terms of the following technology adoption scenario, though  there are many other examples that would serve the same purpose.  Suppose there are two instant messenger (IM) systems A and B,  which are not interoperable - users must be on the same system  in order to communicate. There is a social network G on the users,  indicating who wants to talk to whom, and the endpoints of each  edge (v, w) play a coordination game with possible strategies A  or B: if v and w each choose IM system B, then they they each  receive a payoff of q (since they can talk to each other using system  B); if they each choose IM system A, then they they each receive  a payoff of 1 − q; and if they choose opposite systems, then they  each receive a payoff of 0 (reflecting the lack of interoperability).  Note that A is the better technology if q < 1  2  , in the sense that  A-A payoffs would then exceed B-B payoffs, while A is the worse  technology if q > 1  2  .  75  A number of qualitative insights can be derived from a diffusion  model even at this level of simplicity. Specifically, consider a   network G, and let all nodes initially play B. Now suppose a small  number of nodes begin adopting strategy A instead. If we apply  best-response updates to nodes in the network, then nodes in effect  will be repeatedly applying the following simple rule: switch to A  if enough of your network neighbors have already adopted A. (E.g.  you begin using a particular IM system - or social-networking  site, or electronic document format - if enough of your friends  are users of it.) As this unfolds, there can be a cascading sequence  of nodes switching to A, such that a network-wide equilibrium is  reached in the limit: this equilibrium may involve uniformity, with  all nodes adopting A; or it may involve coexistence, with the nodes  partitioned into a set adopting A and a set adopting B, and edges  yielding zero payoff connecting the two sets. Morris [13] provides  a set of elegant graph-theoretic characterizations for when these  qualitatively different types of equilibria arise, in terms of the   underlying network topology and the quality of A relative to B (i.e.  the relative sizes of 1 − q and q).  Compatibility, Interoperability, and Bilinguality. In most of the  settings that form the motivation for diffusion models, coexistence  (however unbalanced) is the typical outcome: for example, human  languages and social conventions coexist along geographic   boundaries; it is a stable outcome for the financial industry to use   Windows while the entertainment industry uses Mac OS. An important  piece that is arguably missing from the basic game-theoretic   models of diffusion, however, is a more detailed picture of what is   happening at the coexistence boundary, where the basic form of the  model posits nodes that adopt A linked to nodes that adopt B.  In these motivating settings for the models, of course, one very  often sees interface regions in which individuals essentially become  bilingual. In the case of human language diffusion, this   bilinguality is meant literally: geographic regions where there is substantial  interaction with speakers of two different languages tend to have  inhabitants who speak both. But bilinguality is also an essential  feature of technological interaction: in the end, many people have  accounts on multiple IM systems, for example, and more   generally many maintain the ability to work within multiple computer  systems so as to collaborate with people embedded in each.  Taking this view, it is natural to ask how diffusion models   behave when extended so that certain nodes can be bilingual in this  very general sense, adopting both strategies at some cost to   themselves. What might we learn from such an extension? To begin  with, it has the potential to provide a valuable perspective on the  question of compatibility and incompatibility that underpins   competition among technology companies. There is a large literature  on how compatibility among technologies affects competition   between firms, and in particular how incompatibility may be a   beneficial strategic decision for certain participants in a market [3, 4, 8, 9,  12]. Whinston [18] provides an interesting taxonomy of different  kinds of strategic incompatibility; and specific industry case studies  (including theoretical perspectives) have recently been carried out  for commercial banks [10], copying and imaging technology [11]  and instant messenger systems [6].  While these existing models of compatibility capture network  effects in the sense that the users in the market prefer to use   technology that is more widespread, they do not capture the more   finegrained network phenomenon represented by diffusion - that each  user is including its local view in the decision, based on what its  own social network neighbors are doing. A diffusion model that   incorporated such extensions could provide insight into the structure  of boundaries in the network between technologies; it could   potentially offer a graph-theoretic basis for how incompatibility may  benefit an existing technology, by strengthening these boundaries  and preventing the incursion of a new, better technology.  The present work: Diffusion with bilingual behavior. In this  paper, we develop a set of diffusion models that incorporate notions  of compatibility and bilinguality, and we find that some unexpected  phenomena emerge even from very simple versions of the models.  We begin with perhaps the simplest way of extending Morris"s  model discussed above to incorporate bilingual behavior. Consider  again the example of IM systems A and B, with the payoff   structure as before, but now suppose that each node can adopt a third  strategy, denoted AB, in which it decides to use both A and B. An  adopter of AB gets to use, on an edge-by-edge basis, whichever  of A or B yields higher payoffs in each interaction, and the payoff  structure is defined according to this principle: if an adopter of AB  interacts with an adopter of B, both receive q; with an adopter of  A, both receive 1 − q; and with another adopter of AB, both   receive max(q, 1 − q). Finally, an adopter of AB pays a fixed-cost  penalty of c (i.e. −c is added to its total payoff) to represent the  cost of having to maintain both technologies.  Thus, in this model, there are two parameters that can be varied:  the relative qualities of the two technologies (encoded by q), and  the cost of being bilingual, which reflects a type of incompatibility  (encoded by c).  Following [13] we assume the underlying graph G is infinite;  we further assume that for some natural number Δ, each node has  degree Δ.1  We are interested in the question posed at the outset, of  whether a new technology A can spread through a network where  almost everyone is initially using B. Formally, we say that strategy  A can become epidemic if the following holds: starting from a state  in which all nodes in a finite set S adopt A, and all other nodes  adopt B, a sequence of best-response updates (potentially with   tiebreaking) in G − S causes every node to eventually adopt A. We  also introduce one additional bit of notation that will be useful in  the subsequent sections: we define r = c/Δ, the fixed penalty for  adopting AB, scaled so that it is a per-edge cost.  In the Morris model, where the only strategic options are A and  B, a key parameter is the contagion threshold of G, denoted q∗  (G):  this is the supremum of q for which A can become epidemic in  G with parameter q in the payoff structure. A central result of  [13] is that 1  2  is the maximum possible contagion threshold for any  graph: supG q∗  (G) = 1  2  . Indeed, there exist graphs in which the  contagion threshold is as large as 1  2  (including the infinite line - the  unique infinite connected 2-regular graph); on the other hand, one  can show there is no graph with a contagion threshold greater than  1  2  .  In our model where the bilingual strategy AB is possible, we  have a two-dimensional parameter space, so instead of a   contagion threshold q∗  (G) we have an epidemic region Ω(G), which  is the subset of the (q, r) plane for which A can become epidemic  in G. And in place of the maximum possible contagion   threshold supG q∗  (G), we must consider the general epidemic region  Ω = ∪GΩ(G), where the union is taken over all infinite Δ-regular  graphs; this is the set of all (q, r) values for which A can become  epidemic in some Δ-regular network.  1  We can obtain strictly analogous results by taking a sequence of  finite graphs and expressing results asymptotically, but the use of  an infinite bounded-degree graph G makes it conceptually much  cleaner to express the results (as it does in Morris"s paper [13]): less  intricate quantification is needed to express the diffusion properties,  and the qualitative phenomena remain the same.  76  1/20 1  r  q  0  1/2  1  Figure 1: The region of the (q, r) plane for which technology A  can become epidemic on the infinite line.  Our Results. We find, first of all, that the epidemic region Ω(G)  can be unexpectedly complex, even for very simple graphs G.   Figure 1 shows the epidemic region for the infinite line; one observes  that neither the region Ω(G) nor its complement is convex in the  positive quadrant, due to the triangular cut-out shape. (We find  analogous shapes that become even more complex for other   simple infinite graph structures; see for example Figures 3 and 4.) In  particular, this means that for values of q close to but less than 1  2  ,  strategy A can become epidemic on the infinite line if r is   sufficiently small or sufficiently large, but not if r takes values in some  intermediate interval. In other words, strategy B (which represents  the worse technology, since q < 1  2  ) will survive if and only if the  cost of being bilingual is calibrated to lie in this middle interval.  This is a reflection of limited compatibility - that it may be in  the interest of an incumbent technology to make it difficult but not  too difficult to use a new technology - and we find it surprising  that it should emerge from a basic model on such a simple network  structure. It is natural to ask whether there is a qualitative   interpretation of how this arises from the model, and in fact it is not hard to  give such an interpretation, as follows.  When r is very small, it is cheap for nodes to adopt AB as  a strategy, and so AB spreads through the whole network.  Once AB is everywhere, the best-response updates cause all  nodes to switch to A, since they get the same interaction   benefits without paying the penalty of r.  When r is very large, nodes at the interface, with one A   neighbor and one B neighbor, will find it too expensive to choose  AB, so they will choose A (the better technology), and hence  A will spread step-by-step through the network.  When r takes an intermediate value, a node v at the   interface, with one A neighbor and one B neighbor, will find it  most beneficial to adopt AB as a strategy. Once this happens,  the neighbor of v who is playing B will not have sufficient  incentive to switch, and the best-response updates make no  further progress. Hence, this intermediate value of r allows  a boundary of AB to form between the adopters of A and  the adopters of B.  In short, the situation facing B is this: if it is too permissive, it gets  invaded by AB followed by A; if it is too inflexible, forcing nodes  to choose just one of A or B, it gets destroyed by a cascade of  direct conversions to A. But if it has the right balance in the value  of r, then the adoptions of A come to a stop at a bilingual boundary  where nodes adopt AB.  Moving beyond specific graphs G, we find that this non-convexity  holds in a much more general sense as well, by considering the   general epidemic region Ω = ∪GΩ(G). For any given value of Δ, the  region Ω is a complicated union of bounded and unbounded   polygons, and we do not have a simple closed-form description for it.  However, we can show via a potential function argument that no  point (q, r) with q > 1  2  belongs to Ω. Moreover, we can show the  existence of a point (q, r) ∈ Ω for which q < 1  2  . On the other hand,  consideration of the epidemic region for the infinite line shows that  (1  2  , r) ∈ Ω for r = 0 and for r sufficiently large. Hence, neither Ω  nor its complement is convex in the positive quadrant.  Finally, we also extend a characterization that Morris gave for  the contagion threshold [13], producing a somewhat more intricate  characterization of the region Ω(G). In Morris"s setting, without an  AB strategy, he showed that A cannot become epidemic with   parameter q if and only if every cofinite set of nodes contains a subset  S that functions as a well-connected community: every node in  S has at least a (1 − q) fraction of its neighbors in S. In other  words, tightly-knit communities are the natural obstacles to   diffusion in his setting. With the AB strategy as a further option, a more  complex structure becomes the obstacle: we show that A cannot   become epidemic with parameters (q, r) if and only if every cofinite  set contains a structure consisting of a tightly-knit community with  a particular kind of interface of neighboring nodes. We show that  such a structure allows nodes to adopt AB at the interface and B  inside the community itself, preventing the further spread of A; and  conversely, this is the only way for the spread of A to be blocked.  The analysis underlying the characterization theorem yields a  number of other consequences; a basic one is, roughly speaking,  that the outcome of best-response updates is independent of the   order in which the updates are sequenced (provided only that each  node attempts to update itself infinitely often).  Further Extensions. Another way to model compatibility and   interoperability in diffusion models is through the off-diagonal terms  representing the payoff for interactions between a node adopting A  and a node adopting B. Rather than setting these to 0, we can   consider setting them to a value x ≤ min(q, 1 − q). We find that  for the case of two technologies, the model does not become more  general, in that any such instance is equivalent, by a re-scaling of  q and r, to one where x = 0. Moreover, using our   characterization of the region Ω(G) in terms of communities and interfaces, we  show a monotonicty result: if A can become epidemic on a graph  G with parameters (q, r, x), and then x is increased, then A can  still become epidemic with the new parameters.  We also consider the effect of these off-diagonal terms in an   extension to k > 2 competing technologies; for technologies X and  Y , let qX denote the payoff from an X-X interaction on an edge  and qXY denote the payoff from an X-Y interaction on an edge.  We consider a setting in which two technologies B and C, which  initially coexist with qBC = 0, face the introduction of a third,  better technology A at a finite set of nodes. We show an example  in which B and C both survive in equilibrium if they set qBC in  a particular range of values, but not if they set qBC too low or too  high to lie in this range. Thus, in even in a basic diffusion model  with three technologies, one finds cases in which two firms have an  incentive to adopt a limited strategic alliance, partially increasing  their interoperability to defend against a new entrant in the market.  2. MODEL  We now develop some further notation and definitions that will  be useful for expressing the model. Recall that we have an infinite  Δ-regular graph G, and strategies A, B, and AB that are used in  a coordination game on each edge. For edge (v, w), the payoff  77  to each endpoint is 0 if one of the two nodes chooses strategy A  and the other chooses strategy B; 1 − q if one chooses strategy A  and the other chooses either A or AB; q if one chooses strategy B  and the other chooses either B or AB; and max(q, 1 − q) if both  choose strategy AB. The overall payoff of an agent v is the sum of  the above values over all neighbors w of v, minus a cost which is 0  if v chooses A or B and c = rΔ if she chooses AB. We refer to  the overall game, played by all nodes in G, as a contagion game,  and denote it using the tuple (G, q, r).  This game can have many Nash equilibria. In particular, the  two states where everybody uses technology A or everybody uses  technology B are both equilibria of this game. As discussed in  the previous section, we are interested in the dynamics of reaching  an equilibrium in this game; in particular, we would like to know  whether it is possible to move from an all-B equilibrium to an all-A  equilibrium by changing the strategy of a finite number of agents,  and following a sequence of best-response moves.  We provide a formal description of this question via the   following two definitions.  DEFINITION 2.1. Consider a contagion game (G, q, r). A state  in this game is a strategy profile s : V (G) → {A, B, AB}. For  two states s and s and a vertex v ∈ V (G), if starting from state s  and letting v play her best-response move (breaking ties in favor of  A and then AB) we get to the state s , we write s  v  → s . Similarly,  for two states s and s and a finite sequence S = v1, v2, . . . , vk of  vertices of G (where vi"s are not necessarily distinct), we say s  S  →  s if there is a sequence of states s1, . . . , sk−1 such that s  v1  → s1  v2  →  s2  v3  → · · · sk−1  vk  → s . For an infinite sequence S = v1, v2, . . . of  vertices of G, we denote the subsequence v1, v2, . . . , vk by Sk. We  say s  S  → s for two states s and s if for every vertex v ∈ V (G)  there exists a k0(v) such that for every k > k0(v), s  Sk  → sk for a  state sk with sk(v) = s (v).  DEFINITION 2.2. For T ⊆ V (G), we denote by sT the strategy  profile that assigns A to every agent in T and B to every agent in  V (G) \ T. We say that technology A can become an epidemic in  the game (G, q, r) if there is a finite set T of nodes in G (called the  seed set) and a sequence S of vertices in V (G) \ T (where each  vertex can appear more than once) such that sT  S  → sV (G), i.e.,  endowing agents in T with technology A and letting other agents  play their best response according to schedule S would lead every  agent to eventually adopt strategy A.2  The above definition requires that the all-A equilibrium be   reachable from the initial state by at least one schedule S of best-response  moves. In fact, we will show in Section 4 that if A can become  an epidemic in a game, then for every schedule of best-response  moves of the nodes in V (G) \ T in which each node is scheduled  an infinite number of times, eventually all nodes adopt strategy A.3  3. EXAMPLES  We begin by considering some basic examples that yield   epidemic regions with the kinds of non-convexity properties discussed  2  Note that in our definition we assume that agents in T are endowed  with the strategy A at the beginning. Alternatively, one can define  the notion of epidemic by allowing agents in T to be endowed with  any combination of AB and A, or with just AB. However, the  difference between these definitions is rather minor and our results  carry over with little or no change to these alternative models.  3  Note that we assume agents in the seed set T cannot change their  strategy.  0−1 1 2  Figure 2: The thick line graph  in Section 1. We first discuss a natural Δ-regular generalization of  the infinite line graph, and for this one we work out the complete  analysis that describes the region Ω(G), the set of all pairs (q, r)  for which the technology A can become an epidemic. We then   describe, without the accompanying detailed analysis, the epidemic  regions for the infinite Δ-regular tree and for the two-dimensional  grid.  The infinite line and the thick line graph. For a given even   integer Δ, we define the thick line graph LΔ as follows: the vertex  set of this graph is Z × {1, 2, . . . , Δ/2}, where Z is the set of all  integers. There is an edge between vertices (x, i) and (x , i ) if and  only if |x − x | = 1. For each x ∈ Z, we call the set of vertices  {(x, i) : i ∈ {1, . . . , Δ/2} the x"th group of vertices. Figure 2  shows a picture of L6  Now, assume that starting from a position where every node uses  the strategy B, we endow all agents in a group (say, group 0) with  the strategy A. Consider the decision faced by the agents in group  1, who have their right-hand neighbors using B and their left-hand  neighbors using A. For these agents, the payoffs of strategies A,  B, and AB are (1 − q)Δ/2, qΔ/2, and Δ/2 − rΔ, respectively.  Therefore, if  q ≤  1  2  and q ≤ 2r,  the best response of such an agent is A. Hence, if the above   inequality holds and we let agents in groups 1, −1, 2, −2, . . . play  their best response in this order, then A will become an epidemic.  Also, if we have q > 2r and q ≤ 1 − 2r, the best response of  an agent with her neighbors on one side playing A and neighbors  on the other side playing B is the strategy AB. Therefore, if we  let agents in groups 1 and −1 change to their best response, they  would switch their strategy to AB. After this, agents in group 2  will see AB on their left and B on their right. For these agents  (and similarly for the agents in group −2), the payoff of strategies  A, B, and AB are (1−q)Δ/2, qΔ, and (q+max(q, 1−q))Δ/2−  rΔ, respectively. Therefore, if max(1, 2q) − 2r ≥ 1 − q and  max(1, 2q) − 2r ≥ 2q, or equivalently, if  2r ≤ q and q + r ≤  1  2  ,  the best response of such an agent is AB. Hence, if the above  inequality holds and we let agents in groups 2, −2, 3, −3 . . . play  their best response in this order, then every agent (except for agents  in group 0) switches to AB. Next, if we let agents in groups  1, −1, 2, −2, . . . change their strategy again, for q ≤ 1/2,   every agent will switch to strategy A, and hence A becomes an   epidemic.4  4  Strictly speaking, since we defined a schedule of moves as  a single infinite sequence of vertices in V (G) \ T, the order  1, −1, 2, −2, . . . , 1, −1, 2, −2, . . . is not a valid schedule.   However, since vertices of G have finite degree, it is not hard to see  that any ordering of a multiset containing any (possibly infinite)  78  1/20  r  q  0  1/4  3/16  1/12  1/4  Figure 3: Epidemic regions for the infinite grid  1/20 1/Δ  r  q  0  1/Δ  Figure 4: Epidemic regions for the infinite Δ-regular tree  The above argument shows that for any combination of (q, r)  parameters in the marked region in Figure 1, technology A can  become an epidemic. It is not hard to see that for points outside  this region, A cannot become epidemic.  Further examples: trees and grids. Figures 3 and 4 show the  epidemic regions for the infinite grid and the infinite Δ-regular tree.  Note they also exhibit non-convexities.  4. CHARACTERIZATION  In this section, we characterize equilibrium properties of   contagion games. To this end, we must first argue that contagion games  in fact have well-defined and stable equilibria. We then discuss  some respects in which the equilibrium reached from an initial state  is essentially independent of the order in which best-response   updates are performed.  We begin with the following lemma, which proves that agents  eventually converge to a fixed strategy, and so the final state of a  game is well-defined by its initial state and an infinite sequence of  moves. Specifically, we prove that once an agent decides to adopt  technology A, she never discards it, and once she decides to discard  technology B, she never re-adopts it. Thus, after an infinite number  of best-response moves, each agent converges to a single strategy.  LEMMA 4.1. Consider a contagion game (G, q, r) and a   (possibly infinite) subset T ⊆ V (G) of agents. Let sT be the strategy  profile assigning A to every agent in T and B to every agent in  V (G) \ T. Let S = v1, v2, . . . be a (possibly infinite) sequence of  number of copies of each vertex of V (G) \ T can be turned  into an equivalent schedule of moves. For example, the sequence  1, −1, 2, −2, 1, −1, 3, −3, 2, −2, . . . gives the same outcome as  1, −1, 2, −2, . . . , 1, −1, 2, −2, . . . in the thick line example.  agents in V (G) \ T and consider the sequence of states s1, s2, . . .  obtained by allowing agents to play their best-response in the order  defined by S (i.e., s  v1  → s1  v2  → s2  v3  → · · · ). Then for every i, one of  the following holds:  • si(vi+1) = B and si+1(vi+1) = A,  • si(vi+1) = B and si+1(vi+1) = AB,  • si(vi+1) = AB and si+1(vi+1) = A,  • si(vi+1) = si+1(vi+1).  PROOF. Let X >k  v Y indicate that agent v (weakly) prefers  strategy X to strategy Y in state sk. For any k let zk  A, zk  B, and zk  AB  be the number of neighbors of v with strategies A, B, and AB in  state sk, respectively. Thus, for agent v in state sk,  1. A >k  v B if (1 − q)(zk  A + zk  AB) is greater than q(zk  B + zk  AB),  2. A >k  v AB if (1− q)(zk  A + zk  AB) is greater than (1− q)zk  A +  qzk  B + max(q, 1 − q)zk  AB − Δr,  3. and AB >k  v B if (1−q)zk  A +qzk  B +max(q, 1−q)zk  AB −Δr  is greater than q(zk  B + zk  AB).  Suppose the lemma is false and consider the smallest i such that the  lemma is violated. Let v = vi+1 be the agent who played her best  response at time i. Thus, either 1. si(v) = A and si+1(v) = B,  or 2. si(v) = A and si+1(v) = AB, or 3. si(v) = AB and  si+1(v) = B. We show that in the third case, agent v could not  have been playing a best response. The other cases are similar.  In the third case, we have si(v) = AB and si+1(v) = B. As  si(v) = AB, there must be a time j < i where sj  v  → sj+1 and  sj+1(v) = AB. Since this was a best-response move for v,   inequality 3 implies that (1 − q)zj  A + max(0, 1 − 2q)zj  AB ≥ Δr.  Furthermore, as i is the earliest time at which the lemma is   violated, zi  A ≥ zj  A and zj  AB − zi  AB ≤ zi  A − zj  A. Thus, the change Q  in payoff between AB and B (plus Δr) is  Q ≡ (1 − q)zi  A + max(0, 1 − 2q)zi  AB  ≥ (1 − q)(zi  A − zj  A + zj  A)  + max(0, 1 − 2q)(zj  AB − zi  A + zj  A)  = (1 − q)zj  A + max(0, 1 − 2q)zj  AB  + max(q, 1 − q)(zi  A − zj  A)  ≥ (1 − q)zj  A + max(0, 1 − 2q)zj  AB  ≥ Δr,  and so, by inequality 3, B can not be a better response than AB for  v in state si.  COROLLARY 4.2. For every infinite sequence S of vertices in  V (G) \ T, there is a unique state s such that s0  S  → s, where s0  denotes the initial state where every vertex in T plays A and every  vertex in V (G) \ T plays B.  Such a state s is called the outcome of the game (G, q, r) starting  from T and using the schedule S.  Equivalence of best-response schedules. Lemma 4.1 shows that  the outcome of a game is well-defined and unique. The following  theorems show that the outcome is also invariant to the dynamics,  or sequence of best-response moves, under certain mild conditions.  The first theorem states that if the all-A equilibrium is the outcome  of a game for some (unconstrained) schedule, then it is the outcome  for any schedule in which each vertex is allowed to move infinitely  many times. The second theorem states that the outcome of a game  is the same for any schedule of moves in which every vertex moves  infinitely many times.  79  THEOREM 4.3. Consider a contagion game (G, q, r), a subset  T ⊆ V (G), and a schedule S of vertices in V (G) \ T such that  the outcome of the game is the all-A equilibrium. Then for any  schedule S of vertices in V (G) \ T such that every vertex in this  set occurs infinitely many times, the outcome of the game using the  schedule S is also the all-A equilibrium.  PROOF. Note that S is a subsequence of S . Let π : S → S be  the injection mapping S to its subsequence in S . We show for any  vi ∈ S, if vi switches to AB, then π(vi) switches to AB or A, and  if vi switches to A, then π(vi) switches to A (here v switches to  X means that after the best-response move, the strategy of v is X).  Suppose not and let i be the smallest integer such that the statement  doesn"t hold. Let zA, zB, and zAB be the number of neighbors of  vi with strategies A, B, and AB in the current state defined by S.  Define zA,zB, and zAB similarly for S . Then, by Lemma 4.1 and  the choice of i, zA ≥ zA, zB ≤ zB, zAB − zAB ≤ zB − zB, and  zAB − zAB ≤ zA − zA. Now suppose vi switches to AB. Then  the same sequence of inequalities as in Lemma 4.1 show that AB  is a better response than B for π(vi) (although A might be the best  response) and so π(vi) switches to either AB or A. The other case  (vi switches to A) is similar.  THEOREM 4.4. Consider a contagion game (G, q, r) and a   subset T ⊆ V (G). Then for every two schedules S and S of vertices  in V (G)\T such that every vertex in this set occurs infinitely many  times in each of these schedules, the outcomes of the game using  these schedules are the same.  PROOF. The proof of this theorem is similar to that of   theorem 4.3 and is deferred to the full version of the paper.  Blocking structures. Finally, we prove the characterization   mentioned in the introduction: A cannot become epidemic if and only  if (G, q, r) possesses a certain kind of blocking structure. This   result generalizes Morris"s theorem on the contagion threshold for  his model; in his case without AB as a possible strategy, a simpler  kind of community structure was the obstacle to A becoming  epidemic.  We begin by defining the blocking structures.  DEFINITION 4.5. Consider a contagion game (G, q, r). A pair  (SAB, SB) of disjoint subsets of V (G) is called a blocking   structure for this game if for every vertex v ∈ SAB,  degSB  (v) >  r  q  Δ,  and for every vertex v ∈ SB,  (1 − q) degSB  (v) + min(q, 1 − q) degSAB  (v) > (1 − q − r)Δ,  and  degSB  (v) + q degSAB  (v) > (1 − q)Δ,  where degS(v) denotes the number of neighbors of v in the set S.  THEOREM 4.6. For every contagion game (G, q, r),   technology A cannot become epidemic in this game if and only if every  co-finite set of vertices of G contains a blocking structure.  PROOF. We first show that if every co-finite set of vertices of  G contains a blocking structure, then technology A cannot become  epidemic. Let T be any finite set of vertices endowed with   technology A, and let (SAB, SB) be the blocking structure contained  in V (G) \ T. We claim that in the outcome of the game for any   sequence S of moves, the vertices in SAB have strategy B or AB and  the vertices in SB have strategy B. Suppose not and let v be the first  vertex in sequence S to violate this (i.e., v ∈ SAB switches to A or  v ∈ SB switches to A or AB). Suppose v ∈ SAB (the other cases  are similar). Let zA, zB, and zAB denote the number of neighbors  of v with strategies A, B, and AB respectively. As v is the first  vertex violating the claim, zA ≤ Δ− degSB  (v)− degSAB  (v) and  zB ≥ degSB  (v). We show AB is a better strategy than A for v.  To show this, we must prove that (1 − q)zA + qzB + max(q, 1 −  q)zAB − Δr > (1 − q)(zA + zAB) or, equivalently, the quantity  Q ≡ qzB + max(2q − 1, 0)zAB − Δr > 0:  Q = (max(2q − 1, 0) − r)Δ − max(2q − 1, 0)zA  +(q − max(2q − 1, 0))zB  ≥ (max(2q − 1, 0) − r)Δ + min(q, 1 − q) degSB  (v)  − max(2q − 1, 0)(Δ − degSB  (v) − degSAB  (v))  ≥ [min(q, 1 − q) + max(2q − 1, 0)] degSB  (v) − rΔ  = q degSB  (v) − rΔ  > 0,  where the last inequality holds by the definition of the blocking  structure.  We next show that A cannot become epidemic if and only if   every co-finite set of vertices contains a blocking structure. To   construct a blocking structure for the complement of a finite set T of  vertices, endow T with strategy A and consider the outcome of  the game for any sequence S which schedules each vertex an   infinite number of times. Let SAB be the set of vertices with   strategy AB and SB be the set of vertices with strategy B in this  outcome. Note for any v ∈ SAB, AB is a best-response and so  is strictly better than strategy A, i.e. q degSB  (v) + max(q, 1 −  q) degSAB  −Δr > (1− q) degSAB  (v), from where it follows that  degSB  (v) > (rΔ)/q. The inequalities for the vertices v ∈ SB can  be derived in a similar manner.  A corollary to the above theorem is that for every infinite graph  G, the epidemic regions in the q-r plane for this graph is a finite  union of bounded and unbounded polygons. This is because the  inequalities defining blocking structures are linear inequalities in  q and r, and the coefficients of these inequalities can take only  finitely many values.  5. NON-EPIDEMIC REGIONS IN GENERAL  GRAPHS  The characterization theorem in the previous section provides  one way of thinking about the region Ω(G), the set of all (q, r)  pairs for which A can become epidemic in the game (G, q, r). We  now consider the region Ω = ∪GΩ(G), where the union is taken  over all infinite Δ-regular graphs; this is the set of all (q, r)   values for which A can become epidemic in some Δ-regular network.  The analysis here uses Lemma 4.1 and an argument based on an  appropriately defined potential function.  The first theorem shows that no point (q, r) with q > 1  2  belongs  to Ω. Since q > 1  2  implies that the incumbent technology B is  superior, it implies that in any network, a superior incumbent will  survive for any level of compatibility.  THEOREM 5.1. For every Δ-regular graph G and parameters  q and r, the technology A cannot become an epidemic in the game  (G, q, r) if q > 1/2.  PROOF. Assume, for contradiction, that there is a Δ-regular  graph G and values q > 1/2 and r, a set T of vertices of G that are  initially endowed with the strategy A, and a schedule S of moves  for vertices in V (G) \ T such that this sequence leads to an all-A  equilibrium. We derive a contradiction by defining a non-negative  80  potential function that starts with a finite value and showing that  after each best response by some vertex the value of this function  decreases by some positive amount bounded away from zero. At  any state in the game, let XA,B denote the number of edges in G  that have one endpoint using strategy A and the other endpoint   using strategy B. Furthermore, let nAB denote the number of agents  using the strategy AB. The potential function is the following:  qXA,B + cnAB  (recall c = Δr is the cost of adopting two technologies). Since G  has bounded degree and the initial set T is finite, the initial value  of this potential function is finite. We now show that every best  response move decreases the value of this function by some positive  amount bounded away from zero. By Lemma 4.1, we only need to  analyze the effect on the potential function for moves of the sort  described by the lemma. Therefore we have three cases: a node u  switches from strategy B to AB, a node u switches from strategy  AB to A, or a node u switches from strategy B to A. We consider  the first case here; the proofs for the other cases are similar.  Suppose a node u with strategy B switches to strategy AB. Let  zAB, zA, and zB denote the number of neighbors of u in partition  piece AB, A, and B respectively. Thus, recalling that q > 1/2, we  see u"s payoff with strategy B is q(zAB + zB) whereas his payoff  with strategy AB is q(zAB + zB) + (1 − q)zA − c. In order for  this strategic change to improve u"s payoff, it must be the case that  (1 − q)zA ≥ c. (1)  Now, notice that such a strategic change on the part of u induces  a change in the potential function of −qzA + c as zA edges are  removed from the XA,B edges between A and B and the size of  partition piece AB is increased by one. This change will be   negative so long as zA > c/q which holds by inequality 1 as q > (1−q)  for q > 1/2. Furthermore, as zA can take only finitely many values  (zA ∈ {0, 1, . . . , Δ}), this change is bounded away from zero.  This next theorem shows that for any Δ, there is a point (q, r) ∈  Ω for which q < 1  2  . This means that there is a setting of the   parameters q and r for which the new technology A is superior, but for  which the incumbent technology is guaranteed to survive regardless  of the underlying network.  THEOREM 5.2. There exist q < 1/2 and r such that for every  contagion game (G, q, r), A cannot become epidemic.  PROOF. The proof is based on the potential function from   Theorem 5.1:  qXA,B + cnAB.  We first show that if q is close enough to 1/2 and r is chosen   appropriately, this potential function is non-increasing. Specifically,  let  q =  1  2  −  1  64Δ  and c = rΔ = α,  where α is any irrational number strictly between 3/64 and q.  Again, there are three cases corresponding to the three possible  strategy changes for a node u. Let zAB, zA, and zB denote the  number of neighbors of node u in partition piece AB, A, and B  respectively.  Case 1: B → AB. Recalling that q < 1/2, we see u"s payoff  with strategy B is q(zAB + zB) whereas his payoff with strategy  AB is (1 − q)(zAB + zA) + qzB − c. In order for this strategic  change to improve u"s payoff, it must be the case that  (1 − 2q)zAB + (1 − q)zA ≥ c. (2)  Now, notice that such a strategic change on the part of u induces  a change in the potential function of −qzA + c as zA edges are  removed from the XA,B edges between A and B and the size of  partition piece AB is increased by one. This change will be   nonpositive so long as zA ≥ c/q. By inequality 2 and the fact that zA  is an integer,  zA ≥  ‰  c  1 − q  −  (1 − 2q)zAB  1 − q  ı  .  Substituting our choice of parameters, (and noting that q ∈ [1/4, 1/2]  and zAB ≤ Δ), we see that the term inside the ceiling is less than  1 and at least 3/64  3/4  − 1/32  1/2  > 0. Thus, the ceiling is one, which is  larger than c/q.  Case 2: AB → A. Recalling that q < 1/2, we see u"s payoff  with strategy AB is (1 − q)(zAB + zA) + qzB − c whereas her  payoff with strategy A is (1 − q)(zAB + zA). In order for this  strategic change to improve u"s payoff, it must be the case that  qzB ≤ c. (3)  Such a strategic change on the part of u induces a change in the   potential function of qzB −c as zB edges are added to the XA,B edges  between A and B and the size of partition piece AB is decreased  by one. This change will be non-positive so long as zB ≤ c/q,  which holds by inequality 3.  Case 3: B → A. Note u"s payoff with strategy B is q(zAB +  zB) whereas his payoff with strategy A is (1 − q)(zAB + zA). In  order for this strategic change to improve u"s payoff, it must be the  case that  (1 − 2q)zAB ≥ qzB − (1 − q)zA. (4)  Such a strategic change on the part of u induces a change in the  potential function of q(zB − zA) as zA edges are removed and zB  edges are added to the XA,B edges between A and B. This change  will be negative so long as zB < zA. By inequality 4 and the fact  that zA is an integer,  zA ≥    qzB  1 − q  +  (1 − 2q)zAB  1 − q  .  Substituting our choice of parameters, it is easy to see that the term  inside the floor is at most zB + 1/4, and so the floor is at most  zB as zB is an integer. We have shown the potential function is  non-increasing for our choice of q and c. This implies the potential  function is eventually constant. As c is irrational and the   remaining terms are always rational, both nAB and XA,B must remain  constant for the potential function as a whole to remain constant.  Suppose A is epidemic in this region. As nAB is constant and  A is epidemic, it must be that nAB = 0. Thus, the only moves  involve a node u switching from strategy B to strategy A. In order  for XA,B to be constant for such moves, it must be that zA (the  number of neighbors of u in A) equals zB (the number of neighbors  of u in B) and, as nAB = 0, we have that zA = zB = Δ/2. Thus,  the payoff of u for strategy A is (1 − q)zA < Δ/4 whereas her  payoff for strategy AB is (1−q)zA +qzB −c > Δ/2−q ≥ Δ/4.  This contradicts the assumption that u is playing her best response  by switching to A.  6. LIMITED COMPATIBILITY  We now consider some further ways of modeling compatibility  and interoperability. We first consider two technologies, as in the  previous sections, and introduce off-diagonal payoffs to capture  a positive benefit in direct A-B interactions. We find that this is  81  in fact no more general than the model with zero payoffs for A-B  interactions.  We then consider extensions to three technologies, identifying  situations in which two coexisting incumbent technologies may or  may not want to increases their mutual compatibility in the face of  a new, third technology.  Two technologies. A natural relaxation of the two-technology model  is to introduce (small) positive payoffs for A-B interaction; that is,  cross-technology communication yields some lesser value to both  agents. We can model this using a variable xAB representing the  payoff gathered by an agent with technology A when her   neighbor has technology B, and similarly, a variable xBA representing  the payoff gathered by an agent with B when her neighbor has A.  Here we consider the special case in which these off-diagonal   entries are symmetric, i.e., xAB = xBA = x. We also assume that  x < q ≤ 1 − q.  We first show that the game with off-diagonal entries is   equivalent to a game without these entries, under a simple re-scaling of  q and r. Note that if we re-scale all payoffs by either an additive  or a multiplicative constant, the behavior of the game is unaffected.  Given a game with off-diagonal entries parameterized by q, r and x,  consider subtracting x from all payoffs, and scaling up by a factor  of 1/(1 − 2x). As can be seen by examining Table 1, the resulting  payoffs are exactly those of a game without off-diagonal entries,  parameterized by q = (q − x)/(1 − 2x) and r = r/(1 − 2x).  Thus the addition of symmetric off-diagonal entries does not   expand the class of games being considered.  Table 1 represents the payoffs in the coordination game in terms  of these parameters.  Nevertheless, we can still ask how the addition of an off-diagonal  entry might affect the outcome of any particular game. As the   following example shows, increasing compatibility between two   technologies can allow one technology that was not initially epidemic  to become so.  EXAMPLE 6.1. Consider the contagion game played on a thick  line graph (see Section 3) with r = 5/32 and q = 3/8. In this  case, A is not epidemic, as can be seen by examining Figure 1,  since 2r < q and q + r > 1/2. However, if we insert symmetric  off-diagonal payoffs x = 1/4, we have a new game, equivalent to a  game parameterized by r = 5/16 and q = 1/4. Since q < 1/2  and q < 2r , A is epidemic in this game, and thus also in the game  with limited compatibility.  We now show that generally, if A is the superior technology (i.e.,  q < 1/2), adding a compatibility term x can only help A spread.  THEOREM 6.2. Let G be a game without compatibility,   parameterized by r and q on a particular network. Let G be that same  game, but with an added symmetric compatibility term x. If A is  epidemic for G, then A is epidemic for G .  PROOF. We will show that any blocking structure in G is also  a blocking structure in G. By our characterization theorem,   Theorem 4.6, this implies the desired result. We have that G is   equivalent to a game without compatibility parameterized by q = (q −  x)/(1 − 2x) and r = r/(1 − 2x). Consider a blocking structure  (SB, SAB) for G . We know that for any v ∈ SAB, q dSB (v) >  r Δ. Thus  qdSB (v) > (q − x)dSB (v)  = q (1 − 2x)dSB (v)  > r (1 − 2x)Δ  = rΔ,  as required for a blocking structure in G. Similarly, the two   blocking structure constraints for v ∈ SB are only strengthened when  we move from G to G.  More than two technologies. Given the complex structure   inherent in contagion games with two technologies, the understanding of  contagion games with three or more technologies is largely open.  Here we indicate some of the technical issues that come up with  multiple technologies, through a series of initial results. The   basic set-up we study is one in which two incumbent technologies B  and C are initially coexisting, and a third technology A, superior  to both, is introduced initially at a finite set of nodes.  We first present a theorem stating that for any even Δ, there is  a contagion game on a Δ−regular graph in which the two   incumbent technologies B and C may find it beneficial to increase their  compatibility so as to prevent getting wiped out by the new   superior technology A. In particular, we consider a situation in which  initially, two technologies B and C with zero compatibility are at  a stable state. By a stable state, we mean that no finite   perturbation of the current states can lead to an epidemic for either B or  C. We also have a technology A that is superior to both B and C,  and can become epidemic by forcing a single node to choose A.  However, by increasing their compatibility, B and C can maintain  their stability and resist an epidemic from A.  Let qA denote the payoffs to two adjacent nodes that both choose  technology A, and define qB and qC analogously. We will assume  qA > qB > qC . We also assume that r, the cost of selecting  additional technologies, is sufficiently large so as to ensure that  nodes never adopt more than one technology. Finally, we   consider a compatibility parameter qBC that represents the payoffs  to two adjacent nodes when one selects B and the other selects  C. Thus our contagion game is now described by five parameters  (G, qA, qB, qC , qBC ).  THEOREM 6.3. For any even Δ ≥ 12, there is a Δ-regular  graph G, an initial state s, and values qA, qB, qC , and qBC , such  that  • s is an equilibrium in both (G, qA, qB, qC , 0) and  (G, qA, qB, qC , qBC ),  • neither B nor C can become epidemic in either  (G, qA, qB, qC , 0) or (G, qA, qB, qC , qBC ) starting from state  s,  • A can become epidemic (G, qA, qB, qC , 0) starting from state  s, and  • A can not become epidemic in (G, qA, qB, qC , qBC )  starting from state s.  PROOF. (Sketch.) Given Δ, define G by starting with an infinite  grid and connecting each node to its nearest Δ − 2 neighbors that  are in the same row. The initial state s assigns strategy B to even  rows and strategy C to odd rows. Let qA = 4k2  + 4k + 1/2,  qB = 2k + 2, qC = 2k + 1, and qBC = 2k + 3/4. The first, third,  and fourth claims in the theorem can be verified by checking the  corresponding inequalities. The second claim follows from the first  and the observation that the alternating rows contain any plausible  epidemic from growing vertically.  The above theorem shows that two technologies may both be  able to survive the introduction of a new technology by increasing  their level of compatibility with each other. As one might expect,  82  A B AB  A (1 − q; 1 − q) (x; x) (1 − q; 1 − q − r)  B (x; x) (q; q) (q; q − r)  AB (1 − q − r; 1 − q) (q − r; q) (max(q, 1 − q) − r; max(q, 1 − q) − r)  Table 1: The payoffs in the coordination game. Entry (x, y) in row i, column j indicates that the row player gets a payoff of x and  the column player gets a payoff of y when the row player plays strategy i and the column player plays strategy j.  there are cases when increased compatibility between two   technologies helps one technology at the expense of the other.   Surprisingly, however, there are also instances in which compatibility  is in fact harmful to both parties; the next example considers a fixed  initial configuration with technologies A, B and C that is at   equilibrium when qBC = 0. However, if this compatibility term is   increased sufficiently, equilibrium is lost, and A becomes epidemic.  EXAMPLE 6.4. Consider the union of an infinite two-dimensional  grid graph with nodes u(x, y) and an infinite line graph with nodes  v(y). Add an edge between u(1, y) and v(y) for all y. For this   network, we consider the initial configuration in which all v(y) nodes  select A, and node u(x, y) selects B if x < 0 and selects C   otherwise.  We now define the parameters of this game as follows. Let qA =  3.95, qB = 1.25, qC = 1, and qBC = 0. It is easily verified that  for these values, the initial configuration given above is an   equilibrium. However, now suppose we increase the coordination term,  setting qBC = 0.9. This is not an equilibrium, since each node of  the form u(0, y) now has an incentive to switch from C (generating  a payoff of 3.9) to B (thereby generating a payoff of 3.95).   However, once these nodes have adopted B, the best-response for each  node of the form u(1, y) is A (A generates a payoff of 4 where as  B only generates a payoff of 3.95). From here, it is not hard to  show that A spreads directly throughout the entire network.  7. REFERENCES  [1] L. Blume. The statistical mechanics of strategic interaction.  Games and Economic Behavior, 5:387-424, 1993.  [2] R. L. Cooper (editor). Language spread: Studies in diffusion  and social change. Indiana U. Press, 1982.  [3] N. Economides. Desirability of Compatibility in the Absence  of Network Externalities. American Economic Review,  79(1989), pp. 1165-1181.  [4] N. Economides. Raising Rivals" Costs in Complementary  Goods Markets: LECs Entering into Long Distance and  Microsoft Bundling Internet Explorer. NYU Center for Law  and Business Working Paper 98-004, 1998.  [5] G. Ellison. Learning, local interaction, and coordination.  Econometrica, 61:1047-1071, 1993.  [6] G. Faulhaber. Network Effects and Merger Analysis: Instant  Messaging and the AOL-Time Warner Case.  Telecommunications Policy, Jun/Jul 2002, 26, 311-333  [7] M. Jackson and L. Yariv. Diffusion on social networks.  EconomiePublique, 16:69-82, 2005.  [8] M. Katz and C. Shapiro. Network Externalities, Competition  and Compatibility. American Economic Review. 75(1985),  424-40.  [9] M. Kearns, L. Ortiz. Algorithms for Interdependent Security  Games. NIPS 2003.  [10] C. R. Knittel and V. Stango. Strategic Incompatibility in  ATM Markets. NBER Working Paper No. 12604, October  2006.  [11] J. Mackie-Mason and J. Metzler. Links Between Markets and  Aftermarkets: Kodak (1997). In Kwoka and White eds., The  Antitrust Revolution, Oxford, 2004.  [12] C. Matutes and P. Regibeau. Mix and Match: Product  Compatibility without Network Externalities. RAND Journal  of Economics, 19(1988), pp. 221-234.  [13] S. Morris. Contagion. Review of Economic Studies,  67:57-78, 2000.  [14] E. Rogers. Diffusion of innovations. Free Press, fourth  edition, 1995.  [15] T. Schelling. Micromotives and Macrobehavior. Norton,  1978.  [16] D. Strang and S. Soule. Diffusion in organizations and social  movements: From hybrid corn to poison pills. Annual  Review of Sociology, 24:265-290, 1998.  [17] T. Valente. Network Models of the Diffusion of Innovations.  Hampton Press, 1995.  [18] M. Whinston. Tying, Foreclosure, and Exclusion. American  Economic Review 80(1990), 837-59.  [19] H. Peyton Young. Individual Strategy and Social Structure:  An Evolutionary Theory of Institutions. Princeton University  Press, 1998.  83