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 @[email protected]
@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: @[email protected]
@ai = 1; @[email protected]
@aj = 0 if j 6= i;
xj; @[email protected]
@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.
International Swaps and Derivatives Association, Inc. Disclosure Annex for Interest Rate Transactions This Annex supplements and should be read in conjunction with the General Disclosure Statement. NOTHING IN THIS ANNEX AMENDS OR SUPERSEDES THE EXPRESS TERMS OF ANY TRANSACTION BETWEEN YOU AND US OR ANY RELATED GOVERNING DOCUMENTATION. Accordingly, descriptions in this Annex of the operation o
GMR Varalakshmi Foundation Girijana Institute of Rural Entrepreneurship Development (GIRED) Girijana Institute of Rural Entrepreneurship Development (GIRED) is a unique initiative specifically targeting tribal youth. This Vocational Training centre was started in September 2010 by GMR Varalakshmi Foundation in partnership with Integrated Tribal Development Agency (ITDA) ‐Seethampeta (an