Ecn.ulaval.ca

Network Games under Strategic Complementarities Mohamed Belhaj, Yann Bramoullé and Frédéric Deroïan* Abstract : We study network games with linear best-replies and strategic complementarities. Weassume that actions are continuous but bounded from above. We show that there is always aunique equilibrium. We …nd that two key features of these games under small network e¤ectsmay not hold when network e¤ects are large. Action may not be aligned with network centralityand the interdependence between agents’actions may be broken.
*Belhaj: École Centrale Marseille (Aix-Marseille School of Economics); CNRS & EHESS; Bramoullé:Department of Economics, Université Laval and Aix-Marseille University (Aix-Marseille School of Eco-nomics); CNRS & EHESS; Deroïan: Aix-Marseille University (Aix-Marseille School of Economics); CNRS& EHESS. We thank Federico Echenique, Matthew Jackson, and participants of the 2012 Coalition TheoryNetwork for helpful comments and discussions.
In this paper, we study network games with strategic complementarities. Agents are embedded in a …xed network and interact with their network neighbors. They play a game characterized by positive interactions and linear best-replies, so an agent’s action is increasing in her neighbors’ actions. We assume that actions are continuous but bounded from above, which means that the game is supermodular. Our main result, Theorem 1, establishes that this game always possesses a unique equilibrium. We then build on this result to further characterize the equilibrium. Overall, we …nd that the presence of an upper bound on actions strongly a¤ects the outcomes of the game.
Our paper contributes to the analysis of games played on …xed networks. Ballester, Calvó- Armengol & Zenou (2006) study network games under linear best-replies and small network e¤ects. They …nd that the equilibrium is necessarily unique and that action is related to network centrality. However, no equilibrium exists under strategic complements when network e¤ects are large. Agents’ actions feed back into each other in an explosive way and essentially diverge to in…nity. This divergence seems irrealistic in many contexts where actions possess natural limits.
Indeed, in their empirical implementation of that model, Calvó-Armengol, Patacchini & Zenou (2009) discuss the possibility of introducing such bounds. They state: “Let us bound the strategy space in such a game rather naturally by simply acknowl- edging the fact that students have a time constraint and allocate their time between leisure and school work. In that case, multiple equilibria will certainly emerge, which is a plausible outcome in the school setting.”, Calvó-Armengol, Patacchini & Zenou We show that this conjecture does not hold under positive interactions, which is the usual empirical case. We extend Ballester, Calvó-Armengol & Zenou (2006)’s analysis to situations with large positive network e¤ects and bounded actions. We …nd that uniqueness is guaranteed and we study how the equilibrium depends on the network structure. We develop our analysis in three steps. First, we apply results of monotone comparative statics for supermodular games to our setup. Second, we study how network position is related to action. We show that more central agents may end up playing a lower action. This con…rms Bramoullé, Kranton & D’amours (2011)’s …nding that the tight link between action and centrality only holds for small network e¤ects. We show that this link is preserved for interesting families of networks, including nested split graphs, the line and related hierarchical graphs, and regular graphs. And third, we study the extent of interdependence in the game. We …nd that the interdependence between agents’ actions may be broken under large network e¤ects, especially in situations where bridging agents At …rst glance, uniqueness in this context may indeed seem surprising. On one hand, super- modular games typically admit multiple equilibria. On the other hand, equilibrium multiplicity may be quite drastic in network games with linear best replies, under strategic substitutes (see Bramoullé & Kranton (2007) and Bramoullé, Kranton & D’amours (2011)).1 Our proof makes clear that uniqueness relies on the combination of linearity and strategic complementarities. In- troducing enough non-linearity in the best-replies, or enough substituabilities in the interactions, would lead to multiple equilibria. In a way, linearity and strategic complementarities discipline Our study provides one of the …rst crossover between the theories of supermodular games and of network games. Galeotti, Goyal, Jackson, Vega-Redondo & Yariv (2008) analyze network games under strategic complementarities when agents have incomplete information on the network. We analyze a game of complete information here.2 Belhaj & Deroïan (2009) analyze communication e¤orts under strategic complements and indirect network interactions. They look at the line and related networks. In contrast, we study direct network interactions and obtain results valid for arbitrary networks. Finally, the proof of our main result relies on a principle of partial contraction that, to our knowledge, had not yet been identi…ed in the literature on supermodular games. This principle could potentially be useful in other setups.
The rest of the paper is organized as follows. We present the model in section 2. We prove uniqueness and derive some general properties of the equilibrium in Section 3. We study the relation between network position and action and the extent of interdependence in Section 4 and 1 At the extreme under perfect substitutes, the number of equilibria may increase exponentially with the number of nodes in the network, see Bramoullé & Kranton (2007).
2 However, we note that an agent only needs to know his neighbors’actions to be able to play a best-reply.
Consider n agents embedded in a …xed network, represented by a n entry gij is a non-negative real number representing the link between i and j. We consider an arbitrary weighted network with no self-loop. Formally, gij 2 [0; 1[ and gii = 0. Agent i is directly a¤ected by agent j if gij > 0 and gij then measures the strength of their relation. We do not impose symmetry so gij could di¤er from gji. In many of our examples, we will look at binary networks where gij 2 f0; 1g and links do not di¤er in strength.
Agents choose an action xi 2 [0; L] and play a game with best-response where ai denotes the optimal action of agent i absent social interactions with 0 < ai < L and > 0 denotes a global interaction parameter. A Nash equilibrium of the game is a pro…le of actions x such that 8i; xi = fi(x i).
We take best-replies as primitives, as in Bramoullé, Kranton & D’amours (2011). So our results apply to any game characterized by these best-replies. In particular, the game ij xixj belongs to this class. More generally, consider any functions fi de…ned over R, increasing over ] any real-valued function vi de…ned over [0; L]n 1. Then the game with payo¤s ij xj ) + vi(x i) yields best-replies (1).
In the absence of an upper bound (L = 1), these games have been analyzed in Ballester, Calvó-Armengol & Zenou (2006) and Ballester & Calvó-Armengol (2010). To see what happens, observe that if x is an equilibrium we have x = a+ Gx and hence, through repeated substitutions, x = a + Ga + 2G2a + ::: + tGta + t+1Gt+1x for any t 2 N. Denote by max(G) the largest eigenvalue of matrix G. There are two cases. If max(G) < 1, then there is a unique equilibrium given by x = (I (8i; ai = 1), actions are related to Bonacich centralities in the network.3 In contrast if 3 The pro…le of Bonacich centralities is de…ned as c = (I G)G1 (see Bonacich (1987)), which yields x = 1+ c.
1, there is no equilibrium since the previous series diverges to in…nity.
Our main new assumption is that actions are bounded from above: 8i; xi assumption, the strategy space [0; L] is now a complete lattice and since @2ui=@xi@xj = gij is now a supermodular game (see e.g. De…nitions and Theorem 4 in Milgrom & Roberts (1990)). Therefore we can apply classical results from the theory of supermodular games. In particular, a smallest and a largest Nash equilibrium always exist (see e.g. Theorem 5 in Milgrom & Roberts (1990)). Note that equilibrium conditions only depend on best-reply functions, so this property holds for any game in our class and not only Theorem 1. Let a 2 Rn and G 2 Rn2 such that ai > 0 and gij i 2 [0; L], and best-replies fi(x i) = min(ai + Proof: Denote by x and x the smallest and largest Nash equilibrium such that for any equilib- xi. Denote by I the set of agents who play an interior action in the is empty, the equilibrium is unique. Next, assume that I 6= ?. Given some arbitrary pro…le of actions for agents in I, y 2 [0; L]I, de…ne ^ ' the restriction of the best-reply function f to [0; L]I : '(y) = f (^ in N nI at the upper bound, ' describes the best-reply among agents in I.
Observe, …rst, that a pro…le x is an equilibrium i¤ x = ^ in N nI play the upper bound L in all equilibria. And the equilibrium conditions for agents in I correspond to the …xed point equations of '. Next, we show the following Lemma.
Lemma 1. Consider a system of linear equations of the form yi = bi + 0. If this system admits a non-negative solution y 6= 0, then max(H) < 1.
Proof of Lemma 1: Consider a non-negative solution y 6= 0. For any t, we have y = 1, the sequence on the right increases without bounds which is a contra- Finally, we use Lemma 1 to show that the restricted best-reply ' is contracting on [0; L]I . To see why, observe that yI is a positive solution of the following system of equations: 8i 2 I; yi = j2I ij yj . Apply Lemma 1 to bi = ai + L( y) = min( i(y); L). A linear function is contracting i¤ the largest eigenvalue of its associated matrix is lower than 1, and hence is contracting. Then, 8i; j'i(y) and hence ' is contracting as well. Thus, ' has a unique …xed point, and hence the equilibrium Our proof relies on a principle of partial contraction that could, potentially, have bite in many other contexts. Note that here when network e¤ects are large, the best-reply function is not contracting. Small di¤erences in actions may be strongly ampli…ed after a few rounds of best-replies. However, we show that the best-reply function is contracting on a critical subset of the original strategy space; namely, the set of actions lying between the smallest and largest equilibrium. Since any equilibrium belongs to that set, this property of partial contraction is su¢ cient to guarantee uniqueness. More generally, any supermodular game with such a partially contracting best-reply has a unique equilibrium.
Therefore, uniqueness prevails even in the presence of large positive network e¤ects. The structure imposed by linearity somehow disciplines the natural tendency of strategic comple- mentarities to generate multiple equilibria. Or, viewed from a complementary perspective, the structure imposed by the strategic complementarities somehow disciplines the tendency of linear network games to yield multiple equilibria. In short, we could say that linearity and complemen- Theorem 1 allows us to apply and adapt standard results and techniques from the theory of supermodular games. We begin with comparative statics.
Corollary 1. (Monotone Comparative Statics) For any agent, action in the unique equilibrium is weakly increasing in a, , G and L.
Proof: Note that in the game with quadratic utilities 4 Uniqueness also hinges on the assumption that idiosyncratic actions ai are all strictly positive. Uniqueness holds if some, but not all, ai are equal to zero as long as the network is connected. In contrast, in the degeneratecase where 8i; ai = 0, multiple equilibria may emerge.
derivatives are greater than or equal to zero: @2ui=@xi@ai = 1; @2ui=@xi@aj = 0 if j 6= i; xj; @2ui=@xi@gkl = 0 if kl 6= ij. By Theorem 6 in Milgrom & Roberts (1990), each individual action xi in the unique equilibrium is then weakly increasing in all these parameters. Next, let x (L) be the equilibrium at L and consider a change in upper bound to L0 > L. A …rst round of simultanous best-replies from x (L) necessarily leads x (L). Then, a process of repeated best-replies converges monotonically to the In this context of complementarities, direct and indirect network e¤ects are fully aligned.
Consider, for instance, the impact of connecting two agents. The direct e¤ect of the new link is to induce both agents to increase their actions if they can. As a consequence, their neighbors may also increase their actions and hence their neighbors’ neighbors may increase theirs. The impact of the new link propagates in the network and all the indirect e¤ects are greater than or equal to zero. So the action of every other agent increases weakly following the addition of a new link.5 This stands in sharp contrast to the case of strategic substitutes, where direct and indirect network e¤ects are generally not aligned and comparative statics are more complicated, see Bramoullé, Kranton & D’amours (2011).
We are especially interested in the e¤ect of an increase in , which allows to vary the strength of interactions holding the network structure …xed. Our comparative statics result shows that once an agent reaches the upper bound, he necessarily stays there. This leads to a separation of the parameter space in three regions. Introduce 1 = inff : 9i : [(I ij L). Under homogeneity (8i; ai = 1), observe that where kmin is the lowest degree of the network.
Corollary 2. If G has no isolated agent, the unique equilibrium x is such that 8i; x < L is low, the unique equilibrium is given by x = (I increases, a non-isolated agent necessarily reaches his upper bound Next, the pro…le where all agents play L is an equilibrium i¤ 5 The increase is strict in a connected network under small network e¤ects. The increase may not be strict here, due to the presence of an upper bound, see our discussion of broken interdependence below.
Thus, we see three domains emerging as a function of . When interior and action is proportional to Bonacich centrality in the network. When 1 agents have reached the upper bound but others have not. When the upper bound and action does not depend on the network position. These two thresholds depend on the upper bound L and on the structure of the network. We emphasize that 2 is often larger than 1= max(G), the critical value above which actions diverge in the absence of bound.
When some agents reach the upper bound, this dampens the explosive feedbacks and further postpones the levels for which the remaining agents will also reach it. In addition, the order in which agents reach the upper bound de…nes a network-speci…c ranking. We study below how this ranking depends on the network structure.
Finally, we note that we can import standard algorithms to our setup. In particular, we know that in supermodular games, repeated myopic best-replies converge rapidly and monotonically towards the smallest equilibrium when starting from the lowest pro…le (8i; xi = 0) and towards the largest equilibrium when starting from the highest pro…le (8i; xi = L), see e.g. Vives (1990).6 Therefore, both processes will converge towards the unique equilibrium here. We make use of these algorithms in our examples below.
IV. Structural properties of the equilibrium In this section, we study how the position of an agent in the network a¤ects his action in equilib- rium. To better identify the e¤ect of the structure, we assume throughout that agents’actions in isolation are homogenous (8i; ai = 1) and that links are binary (8i; j; gij 2 f0; 1g). So individuals only di¤er in their network characteristics. Recall that when network e¤ects are small, action is aligned with Bonacich centrality. We wish to understand how this is modi…ed under large We …rst provide an example where a more central agent ends up playing a lower action.
This shows that action and centrality are generally not aligned under large network e¤ects. In a second stage, we identify a number of cases where the alignement between action and centrality 6 In addition, a “round-robin” implementation, when agents take turn in best-replying, converges faster than a simultaneous implementation, when all agents best-reply at the same time.
Figure 1: An example where action and centrality are not aligned.
Consider the graph depicted in Figure 1. It has eight nodes and two cliques: One composed of agents 1 to 4 and the triangle 6-7-8. In addition, agent 5 in the middle is connected to agents 4 and = 0:3 and actions are not bounded, the equilibrium is such that x5 Even though agent 6 has one more neighbor than agent 5, his neighbors are not very central. In contrast, agent 5 is connected to agent 4 who is the most central agent in the graph. When is not too low, the e¤ect of indirect paths dominate and agent 5 is more central than agent 6 and play a higher action. Suppose next that actions are bounded from above by L = 5. The 4:0.8 Agents 1-4 reach the upper bound and this reduces the action premium that agent 5 gets from his link with agent 4. Agent 6, who is less We next identify interesting cases where the alignement between action and centrality is preserved. We …rst look at nested neighborhoods. The following result shows that agents who have less neighbors in the sense of set inclusion always play a weakly lower action.
Proposition 1. Consider two agents i and j. If every neighbor k 6= j of agent i is also a neighbor Proof. Suppose …rst that gij = 0. Then Ni fjg [ Nj. We can assume that x < L (otherwise x (15:46; 15:46; 15:46; 17:28; 7:89; 5:69; 3:87; 3:87).
(5; 5; 5; 5; 3:70; 3:99; 3:14; 3:14).
This property of Bonacich centrality therefore extends to large network e¤ects. Thus, an agent with additional neighbors will reach the upper bound …rst as further characterize the equilibrium for graphs where agents are ordered in a way consistent with nested neighborhoods. This is, in particular, the case for nested split graphs. In these graphs, agents can be ordered so that gkl = 1 ) gij = 1 whenever i instance, as outcomes of network formation processes based on centrality, see König, Tessone & Zenou (2011). On nested split graphs, ki < kj ) Nin fjg aligned. A direct implication of Proposition 1 is that on nested split graphs, agents reach the upper bound precisely in the order of their degrees. A more central agent thus never plays a Nested neighborhoods are not necessary, however, to preserve the alignement between action and centrality. In particular, we can apply the analysis of Belhaj & Deroïan (2010) to our setup.
They study supermodular games played on the line and on related hierarchical graphs. These graphs are de…ned by the following three features. (1) They are structured around a geometric center and increasingly peripheral layers. (2) Degrees decrease weakly as nodes get further away from the center. (3) All agents in a given geometric layer have symmetric positions. (See Belhaj & Deroïan (2010) for a formal de…nition). Their main result then states that more central agents cannot play a lower action in the lowest and in the highest equilibrium in these graphs. In our context, the equilibrium is unique and this yields: Corollary 3. (Belhaj & Deroïan (2010)) On the line and on related hierarchical graphs, an agent who is more central plays a weakly higher action in equilibrium.
Finally, the alignement between action and centrality can also be preserved in circumstances where some agents play the same action. A …rst observation, here, is that two individuals who have symmetric positions in the network must play the same action.9 Next, consider regular networks. A network is regular of degree k if every agent has k links: 8i; networks, agents have the same degree but may have structurally di¤erent positions. Introduce 1 ). We can easily check that in a regular graph of degree k, the unique equilibrium 9 Otherwise, we could build another equilibrium by simply permutating the actions of the players.
In regular graphs all agents play the same action even under large network e¤ects. All agents reach their upper bound for the same level of network e¤ects and this threshold level does not depend on the speci…c structure of the graph. This stands in sharp contrast to what happens under strategic substitutes, where agents play the same action in a stable equilibrium only for small network e¤ects and where the structure of the regular graph strongly a¤ects the level of interactions above which asymmetric actions emerge, see Bramoullé, Kranton & D’amours (2011).
In this section, we look at the pattern and extent of interdependencies. An important lesson of the previous literature is that interdependence is very high under small network e¤ects. Even though agents interact directly with their network neighbors only, the interplay of strategic interactions implies that every agent is eventually a¤ected by every other agent in the population when the network is connected. In contrast, we show here that this interdependence may be broken under large network e¤ects. The reason is that when an agent reaches his upper bound, he stops being a transmitter of in‡uences in the network.
Figure 3: Two communities connected by a bridge.
To illustrate this e¤ect consider the following stylized bridge example, depicted in Figure 3. Society is composed of two communities of equal size. In each community, every agent is connected to every other agent. In addition, one agent in the …rst community is connected to one agent in the second. So there is a unique link bridging the two communities. Then, if idiosyncratic actions ai are not too di¤erent, we can show that there exists two threshold level 1 and 2 such j > 0 for any two agents i and j in the population. In particular, agents in one community are a¤ected by shocks on agents in the other community. Every agent is a¤ected by every other agent. If 1 j > 0 for any two non-bridge agents in the same community while @xi i lies a one community and j in the other. Finally, if 2, every agent plays the upper bound.
Under small network e¤ects, the bridging link plays a crucial role: It transmits shocks from one community to the other. When network e¤ects increase, bridge agents tend to reach the maximal action …rst, because of their more central position. They then become unresponsive to shocks and this turns o¤ the transmission channel.
g the set of agents j who indirectly a¤ect i in the sense that a positive shock on j’s action leads to an increase in i’s action.10 Note that Pi = N nfig if the graph is connected and < 1 and that Pi = ? if x = L. We obtain the increases, the set of agents who indirectly a¤ect i, Pi( ), shrinks monoton- Proof: Suppose that x < L and denote by I the set of agents playing an interior action. Denote I ij if j 2 I . Therefore, an agent j belongs to Pi i¤ there is a positive integer t such This means that there exists a path from i to j in which all agents play an increases, more agents reach the upper bound and this set shrinks. When is large enough, everyone plays L and actions are insensitive to marginal changes in aj. QED.
Therefore, the extent of interdependencies is always smaller under higher network e¤ects.
Clearly, the way interdependence is broken depends on the shape of the network and on the number and the locations of the bridges. This, in turn, depends on the prominence of bridging agents within their communities. If bridging agents are equally central, or more, within their own community, as in the example above, we can expect interdependence to be reduced quite quickly because bridging agents will reach the upper bound …rst. But there are contexts where agents who are better connected externally are also less connected internally. In these situations, interdependence may be more robust as bridging agents within communities may reach the upper 1 0 Note that the left- and right- derivatives of individual action xi with respect to aj may di¤er and ( @xi )+ represents the right-derivative here. The analysis carries over to the set of agents j such that a negative shock onj’s action leads to a decrease in i’s action.
In this paper, we analyze linear network games under strategic complementarities and with an upper bound on actions. We show that there is always a unique equilibrium. We apply standard results from the literature on supermodular games and characterize structural features of the equilibrium. In particular, we show that action may not be aligned with Bonacich centrality and that large network e¤ects tend to break the interdependence.
Our results could be useful for empirical studies of peer e¤ects in networks, see Calvó- Armengol, Patacchini & Zenou (2009) and Bramoullé, Djebbari & Fortin (2009). A typical econometric model aimed at studying whether some variable of interest x is subject to peer is the main parameter of interest to be estimated and "i is an error term.11 Most choices and socio-economic outcomes are naturally bounded from above but existing empirical studies have neglected these bounds. This likely generates biases in existing estimates. While equilibrium multiplicity complicates the econometric analysis of games (see e.g. Tamer (2003)), Theorem 1 shows that this is not an issue here. Since the equilibrium x is a function of a; ; G and " we can, in principle and given some assumption on the error terms, compute the likelihood L(x ja; ; G) through maximum likelihood in a straightforward manner. Thus our analysis provides a stepping stone for an empirical study of peer e¤ects in networks with continuous but 1 1 There are various possible empirical speci…cations for the a’s (including individual covariates and, possibly, contextual peer e¤ects), the g’s (linear-in-sum or linear-in-means), and the error terms ".
Ballester, Coralio, Calvó-Armengol, Antoni, and Yves Zenou. 2006. “Who’s who in networks.
Wanted: the key player,” Econometrica, 74(5), pp. 1403-1417.
Ballester, Coralio and Antoni Calvó-Armengol. 2010 “Interactions with hidden complementari-ties,” Regional Science and Urban Economics, 40(6), pp. 397-406.
Belhaj, Mohamed and Frédéric Deroïan. 2010. “Endogenous e¤ort in communication networksunder strategic complementarity,” International Journal of Game Theory, 39, pp. 391-408.
Bonacich, P. 1987. “Power and Centrality: A Family of Measures,”American Journal of Sociology,92(5), pp. 1170-1182.
Bramoullé, Yann, Kranton, Rachel and Martin D’amours. 2011. “Strategic Interaction andNetworks,” mimeo Duke University.
Bramoullé, Yann, Djebbari, Habiba and Bernard Fortin. 2009. “Identi…cation of Peer E¤ectsthrough Social Networks,” Journal of Econometrics, 150, pp. 41-55.
Bramoullé, Yann, and Rachel Kranton. 2007. “Public Goods in Networks,”Journal of EconomicTheory, 135(1), pp. 478-494.
Calvó-Armengol, Antoni, Patacchini, Eleanora and Yves Zenou. 2009. “Peer E¤ects and SocialNetworks in Education,” Review of Economic Studies, 76(4), pp. 1239-1267, König, Michael, Tessone, Claudio, and Yves Zenou. 2011. “Nestedness in Networks: A TheoreticalModel and Some Applications,” mimeo Stockholm University.
Milgrom, Paul and John Roberts. 1990. “Rationalizability, Learning and Equilibrium in Gameswith Strategic Complementarities,” Econometrica, 58(6), pp. 1255-1277, Tamer, E. T. 2003. “Incomplete Bivariate Discrete Response Model with Multiple Equilibria,”Review of Economic Studies, 70, pp. 147-167.
Vives, Xavier. 1990 “Nash Equilibrium with Strategic Complementarities,” Journal of Mathe-matical Economics 19, pp. 305-321.

Source: https://www.ecn.ulaval.ca/sites/ecn.ulaval.ca/files/professeurs/YannBramoulle/networkcomplementsoctober2012.pdf