# Structural Interventions in Networks††thanks: For useful comments and
suggestions we thank Hanming Fang, Ben Golub, Sanjeev Goyal, Matthew Jackson,
Evan Sadler, Adam Szeidl, Yves Zenou, and participants at conferences and
workshops.

Yang Sun Department of Economics, Sichuan University, China. Email:
<EMAIL_ADDRESS>Wei Zhao Department of Economics and Decision
Sciences, HEC Paris, France. Email<EMAIL_ADDRESS>Junjie Zhou Department
of Economics, National University of Singapore, Singapore. Email:
<EMAIL_ADDRESS>
###### Abstract

Two types of interventions are commonly implemented in networks:
characteristic intervention which influences individuals’ intrinsic
incentives, and structural intervention which targets at the social links
among individuals. In this paper we provide a general framework to evaluate
the distinct equilibrium effects of both types of interventions. We identify a
hidden equivalence between a structural intervention and an _endogenously
determined_ characteristic intervention. Compared with existing approaches in
the literature, the perspective from such an equivalence provides several
advantages in the analysis of interventions targeting on network structure. We
present a wide range of applications of our theory, including identifying the
most wanted criminal(s) in delinquent networks and targeting the key connector
for isolated communities.

##  1 Introduction

Social ties shape economic agents’ decisions in a connected world, ranging
from which product to adopt for consumers, how much time to spend on study for
pupils, how much effort to exert for workers within a team, whether to conduct
crime for teenagers, etc.111Numerous studies have highlighted the influence of
networks in different contexts such as microfinance (Banerjee et al. (2013)),
firm performance (Cai and Szeidl (2018)), productivity at work (Mas and
Moretti (2009)), R&D (Goyal and Moraga-González (2001)), education (Sacerdote
(2001); Calvó-Armengol et al. (2009)), crime (Ballester et al. (2006)), public
goods provision (Bramoullé and Kranton (2007); Allouch (2017), brand choice
(David and Dina (2004)), and policy intervention Galeotti et al. (2020)). For
recent surveys, see, for instance, Bramoullé et al. (2016); Jackson et al.
(2017); Elliott et al. (2019). These social ties, structurally represented as
a network, govern individual incentives and therefore collectively determine
equilibrium outcomes and welfare in the society. Thus, structural intervention
on social ties provides an important policy instrument for the social planner.
A natural research question arises: how to best intervene the social structure
to maximize a certain performance objective subject to certain resource
constraints. This research problem is inherently difficult as it is well-known
that network operates in a complex way. Local changes of social links among a
few nodes can influence actions of a large set of nodes, including those who
are far away through ripple effects. Furthermore, the influence is not
homogeneous: nodes that are closer to (further away) the origin of shocks tend
to be more (less) responsive. These key features of shock propagation and
heterogeneous responses make the analysis of structural interventions both
intriguing and challenging.222Admittedly, these two features are also true for
other types of intervention, such as the characteristic intervention. As shown
in Section 2.2, the problem of characteristic intervention in a fixed network
is much simpler and has been extensively studied in the literature.

In this paper, we propose a general yet tractable framework to quantitatively
assess the consequences of an arbitrary structural intervention of social ties
on the equilibrium actions. Overcoming the challenges mentioned above, we
present a neat characterization result in Proposition 1 which evaluates the
change of equilibrium behavior in response to changes in the network
structure. Then we apply Proposition 1 to several economic settings, such as
key group removal in delinquent networks (in Section 3) and key connectors for
isolated communities (in Sections 4).

More specifically, our model of structural intervention builds up a seminal
paper by Ballester et al. (2006) (BCZ hereafter), who propose a simple yet
powerful model of interactions on a fixed network.333The model in BCZ has been
applied, empirically tested, and generalized extensively in the network
literature, see, for example, Calvó-Armengol et al. (2009); Chen et al.
(2018b); Galeotti et al. (2020). They identify the equivalence between
equilibrium actions in a network game and the Katz-Bonacich centralities in
sociology (Bonacich (1987)). The Katz-Bonacich centrality of a node on a
network simply counts the sum of geometrically discounted walks originated
from this node to all the other nodes in the network, weighted by the
characteristics of the ending nodes.444This Katz-Bonacich centrality (and its
variants and generalizations) plays important roles in shaping agents’
decisions in a wide range of network models, see, for instance, production
network (Acemoglu et al. (2012); Baqaee (2018); Liu (2019)), pricing of social
products (Candogan et al. (2012); Bloch and Quérou (2013); Chen et al.
(2018a)). Proposition 1 in our paper characterizes the impacts of structural
intervention on the equilibrium by utilizing another equivalence result: any
(local) intervention on the network structure is equivalent to a (local)
_endogenously determined_ interventions on characteristics. Specifically, we
find that the equilibrium induced by a structural intervention coincides with
that by an endogenously determined characteristic intervention without
changing the network structure. Moreover, the endogenously determined
characteristic intervention only changes the characteristics of the players
whose social ties are altered by the structural intervention. The analysis of
post-intervention equilibrium becomes much simpler after translating a
structural intervention to the characteristic intervention since the later
changes individual’s equilibrium behavior linearly and is well studied in the
literature, while the former is non-linear. Furthermore, in Corollary 1, we
provide a sufficient condition on a structural intervention to induce higher
aggregate equilibrium activity, and use it to check the effect of a link
reallocation, or a link swap on the aggregate action.

For applications, we first adopt the outcome equivalence result to study the
key group problem which aims to specify a group of players removing whom
reduces the aggregate equilibrium activity the most. Specifically, the removal
of a group of players is equivalent to a certain characteristic intervention
restricted to this group. Such a characteristic intervention is chosen to make
sure that, within the original network, the induced equilibrium efforts of
nodes in this group to zero. As a generalization of single node inter-
centrality given by BCZ, we provide a closed-form index of group inter-
centrality explicitly. Such index takes into account both the activities nodes
in this group and their influences on nodes outside of the group. The group
inter-centrality index reveals that the higher the connectedness between nodes
within a group, the lower the inter-centrality of the group. Therefore, the
greedy algorithm, which sequentially selects nodes with highest single node
inter-centrality, may fail to find the key group with highest inter-
centrality. We also show that group inter-centrality index is equivalent to
the aggregate sum of all walks which must pass the group. As a by product, we
characterize the aggregate sum of all walks starting from one group and ending
at the second group, which does _not_ pass the third group. This result
generalizes some of the findings about the targeting centrality proposed by
Bramoullé and Garance (2018) in the information diffusion setting.

Next, we introduce a bridge index to characterize the impact of building up a
bridge between separated networks (Proposition 4). We use the bridge index to
fully solve the key bridge problem. Furthermore, we show that the key bridge
player must locate at the Pareto frontier of Katz-Bonacich centrality and
self-loop in the network. In general, the selection of a bridge pair is an
interdependent decision across two networks as identity of key bridge player
in one network depends on who is selected as his partner in the second
network. These findings are summarized in Corollary 2 and illustrated in
Example 3. We also extend the analysis to consider the value of an existing
link (the key link problem) and the value of a potential link for an arbitrary
network in Section 4.2. As an illustration, we compare inter-group links and
intra-group links in Example 4.

Our paper builds up on the vast literature on network games (see Ballester et
al. (2006), Bramoullé and Kranton (2007) and Galeotti and Goyal (2010)). These
papers typically characterize the effects of network structure on equilibrium
behavior. Our paper instead focuses on how interventions of network structures
affect equilibrium outcomes and sheds light upon the policy design targeting
at network structure.

The literature on interventions in networks could be broadly divided into two
categories: characteristic intervention and network structure intervention. In
the first category, the characteristics of individuals can be changed by
subsidy or taxation on the choices. For instance, Demange (2017) and Galeotti
et al. (2020) study the optimal intervention on characteristics subject to a
fixed budget constraint and a quadratic adjustment cost, respectively.
Motivated by Ballester et al. (2006, 2010), our paper mainly focuses on the
second category: structural intervention. The identified equivalence between a
structural intervention and an endogenously determined characteristic
intervention in our paper provides an interesting link between these two
categories. Several papers on network formation study the most efficient
network by analyzing the impact of link shifting (e.g., Belhaj et al. (2016)
and Li (2020)). As a complementary result, we propose a sufficient condition
to guarantee that a structural intervention leads to higher aggregate action.

An important topic in social networks is to study the relative importance of a
node in a given network using some indices. Various centrality measures have
been proposed to serve the purpose. Bloch et al. (2020) take an axiomatic
approach to provide a unified perspective on several commonly used centrality
measures. Ballester et al. (2006) give a micro-foundation of Katz-Bonacich
centrality and propose another measure, i.e. inter-centrality, to characterize
the impact of a node removal. Analogous measures for a group of nodes, instead
of a single node, are not fully developed. One exception is Ballester et al.
(2010), who define the group intercentrality. One of our contribution is to
propose a specific form of group intercentrality by using the statistics in
the underlying network and show that the group intercentrality decreases with
connectedness between group members. Bramoullé and Garance (2018) study the
contribution of a pair of nodes (one sender and one receiver) in an
information transmission setting. Our analysis in Section 3.2 can be viewed as
an extension of their results by allowing for multiple senders and multiple
receivers.

This paper also speaks to the literature on the effect of bridge(s) between
isolated communities. Verdier and Zenou (2015, 2018) study the communication
between cultural leaders, who serve as a bridge connecting different race
groups. Cai and Szeidl (2018) demonstrate that business meetings facilitate
interfirm communications and create enormous economic values by increasing
firm performance. To the best of our knowledge, Golub and Lever (2010) is the
only network paper to theoretically study the impact of bridge. Golub and
Lever (2010) consider a social learning model and their main focus is on the
eigenvalue centrality. Our paper, instead, studies its impact of a bridge on
Katz-Bonacich centralities and proposes an explicit bridge index to
characterize the key pair of nodes connecting two separated networks. See
Golub and Lever (2010) for a comprehensive discussion of the related
literature.

##  2 Interventions in networks: theory

###  2.1 Setup

Baseline game played on a network Consider a network game played by a set of
players $N=\left\\{1,2,\ldots,n\right\\}$ embedded in a social network
$\mathbf{G}$, which is represented by a $n\times n$ adjacency matrix
$\mathbf{G}=\left(g_{ij}\right)_{n\times n}$. Each player $i$ chooses an
effort $a_{i}\in[0,\infty)$ simultaneously with payoff function given as
follows:555In Section 5, we discuss several extensions of the baseline model.

$u_{i}\left(a_{i},\mathbf{a}_{-i}\right)=\theta_{i}a_{i}-\frac{1}{2}a_{i}^{2}+\delta\underset{k=1}{\overset{n}{\sum}}g_{ik}a_{i}a_{k},~{}~{}~{}~{}i\in
N.$ (1)

This specification of payoff closely follows from Ballester et al. (2006),
where $\theta_{i}$ measures player $i$’s intrinsic marginal utility (hence
$i$’s characteristic), $\frac{1}{2}a_{i}^{2}$ denotes player $i$’s cost of
effort, and the last term
$\delta\underset{k=1}{\overset{n}{\sum}}g_{ik}a_{i}a_{k}$ captures the
interaction term representing the local network effects among players. The
scalar parameter $\delta$ controls the strength of network interaction. We
assume $\delta>0$ so the game exhibits strategic complementarity. We use
$\Gamma\left(\mathbf{G},\boldsymbol{\theta},\delta\right)$ to denote the
network game represented above, where
$\boldsymbol{\theta}=\left(\theta_{1},\ldots,\theta_{n}\right)^{\prime}$ is
the characteristics vector.

Throughout the paper, we impose the standard assumptions that (i) $\mathbf{G}$
is symmetric with $g_{ij}=g_{ji}\in\left\\{0,1\right\\}$, and (ii) that
$g_{ii}=0$ for all $i\in N$.666For ease of interpretation, we focus on
undirected zero-one network matrix $\mathbf{G}$. Our results can be easily
generalized to weighted directed networks. Let
$\lambda_{\max}\left(\mathbf{G}\right)$ denote the spectral radius of matrix
$\mathbf{G}$. By Perron-Frobenius Theorem,
$\lambda_{\max}\left(\mathbf{G}\right)$ also equals the largest eigenvalue of
$\mathbf{G}$. The following is a well-known measure of centralities in network
literature.

######  Definition 1.

Given a network $\mathbf{G}$, a scalar $\delta$, and a $n$-dimensional vector
$\boldsymbol{\theta}$, we define $\boldsymbol{\theta}$-weighted Katz-Bonacich
centralities as

$\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta},\delta\right)=(b_{1},b_{2},\cdots,b_{n})^{\prime}\equiv\left(\mathbf{I}-\delta\mathbf{G}\right)^{-1}\boldsymbol{\theta},$
(2)

provided that $\delta<\frac{1}{\lambda_{\max}\left(\mathbf{G}\right)}$. When
$\boldsymbol{\theta}=(1,1,\cdots,1)^{\prime}=\mathbf{1}$, we call
$\mathbf{b}\left(\mathbf{G},\delta\right)\equiv\mathbf{b}\left(\mathbf{G},\boldsymbol{1},\delta\right)$
the unweighted Katz-Bonacich centralities. Define the Leontief inverse matrix

$\mathbf{M}\left(\mathbf{G},\delta\right)=\left(m_{ij}\left(\mathbf{G}\right)\right)_{n\times
n}\equiv\left(\mathbf{I}-\delta\mathbf{G}\right)^{-1},$ (3)

so that
$b_{i}\left(\mathbf{G},\boldsymbol{\theta},\delta\right)=\underset{j=1}{\overset{n}{\sum}}m_{ij}\left(\mathbf{G}\right)\theta_{j}$.

Intuitively, $m_{ij}\left(\mathbf{G}\right)$ counts the total number of walks
from $i$ to $j$ in network $\mathbf{G}$ with path of length $k$ discounted by
$\delta^{k}$. So $i$’s Katz-Bonacich centrality
$b_{i}\left(\mathbf{G},\boldsymbol{\theta},\delta\right)$ is the sum of walks
starting from $i$ ending at any node $j$ with weights $\theta_{j}$.777It
follows from the following identity of the Leontief inverse matrix:
$\mathbf{M}\left(\mathbf{G},\delta\right)=\left(\mathbf{I}-\delta\mathbf{G}\right)^{-1}=\mathbf{I}+\delta\mathbf{G}+\delta^{2}\mathbf{G}^{2}+\cdots.$
This Neumann series converges when
$0\leq\delta<\frac{1}{\lambda_{\max}\left(\mathbf{G}\right)}$. Interestingly,
Ballester et al. (2006) show that, when
$\delta<\frac{1}{\lambda_{\max}\left(\mathbf{G}\right)}$, game
$\Gamma\left(\mathbf{G},\boldsymbol{\theta},\delta\right)$ has a unique Nash
equilibrium in which each player $i$’s equilibrium action $x_{i}^{\ast}$ is
exactly equal to $i$’s Katz-Bonacich centrality, i.e.,

$\mathbf{x}^{\ast}=\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta},\delta\right)\text{.}$
(4)

The more influential players, measured by the Katz-Bonacich centralities, are
more active in equilibrium. Such an elegant relationship between equilibrium
outcomes and Katz-Bonacich centralities is the starting point of our analysis.

Interventions on networks The network structure $\mathbf{G}$ and the
characteristics vector $\boldsymbol{\theta}$ jointly shape the equilibrium
actions of players and welfare in
$\Gamma\left(\mathbf{G},\boldsymbol{\theta},\delta\right)$. We introduce two
primary types of interventions to influence the equilibrium outcomes:
_characteristic intervention_ and _structural intervention_. In the former
case, $\boldsymbol{\theta}$ is modified to $\boldsymbol{\hat{\theta}}$ while
$\mathbf{G}$ is fixed, and in the latter case, $\mathbf{G}$ is changed to
$\mathbf{\hat{G}}$ while $\boldsymbol{\theta}$ is fixed. The economic
consequences of these two types of interventions are characterized in details
in next two subsections. The hybrid case involving both types of interventions
is discussed in Section 5.2. Importantly, changes in either $\mathbf{G}$ and
$\boldsymbol{\theta}$ in our paper occur due to exogenous and independent
reasons. Furthermore, we do not consider the possibility that changes in
characteristics may induce changes in the network structure, and vice versa.
The parameter $\delta$ is fixed throughout the paper, and often omitted in the
expressions when the context is clear.

Assumptions To ensure the uniqueness of Nash equilibrium before and after the
intervention, we impose the standard spectral condition:
$\delta<\frac{1}{\lambda_{\max}\left(\mathbf{G}\right)}$ and
$\delta<\frac{1}{\lambda_{\max}\left(\mathbf{\hat{G}}\right)}$. Our main focus
is on the effects of interventions on equilibrium actions. In applications we
analyze optimal intervention under certain resource constraint (such as
limiting the number of links or players that can be intervened). Beyond that,
we do not explicitly model the cost side of interventions.888With parametric
assumptions on the cost of interventions, certainly more can be said about the
optimal interventions for the social planer. Assuming a quadratic loss
function of the Euclidean distance between $\boldsymbol{\theta}$ and
$\boldsymbol{\hat{\theta}}$, Galeotti et al. (2020) explicitly solve the
optimal characteristic intervention, for both the case with $\delta>0$
(strategic complement) and that with $\delta<0$ (strategic substitute). They
relate the optimal interventions to the spectral properties of interaction
network and show that the optimal intervention takes a simple form when the
budget of the planner is sufficiently large.

Notation Before proceed, we introduce some notation that will be used in this
paper. In the network $\left(N,\mathbf{G}\right)$, for any subset $A\subseteq
N$, we let $|A|$ denote the cardinality of this set, and let
$A^{C}=N\backslash A$ denote the complement of $A$. Let $\mathbf{G}_{AA}$
denote the $|A|\times|A|$ adjacency matrix of the subnetwork formed by players
in $A$. Moreover, the adjacency matrix $\mathbf{G}$ can be written as a block
matrix
$\mathbf{G}=\begin{bmatrix}\mathbf{G}_{A^{C}A^{C}}&\mathbf{G}_{A^{C}A}\\\
\mathbf{G}_{AA^{C}}&\mathbf{G}_{AA}\end{bmatrix}.$ Similarly, we can rewrite a
column vector $\mathbf{x}$ of length $n$ as
$\begin{bmatrix}\mathbf{x}_{A^{C}}\\\ \mathbf{x}_{A}\end{bmatrix}$. We use $x$
to denote the sum of all elements in vector
$\mathbf{x=}\left(x_{i}\right)_{n\times 1}$, i.e.,
$x=\underset{i=1}{\overset{n}{\sum}}x_{i}$. The transpose of a matrix
$\mathbf{H}$ is denoted by $\mathbf{H}^{\prime}$. Consider two matrices
$\mathbf{Q=}\left(q_{ij}\right)_{n\times m}$ and
$\mathbf{P}=\left(p_{ij}\right)_{n\times m}$ of the same dimension, we write
$\mathbf{Q}\succeq(\preceq)\mathbf{P}$ if and only if
$q_{ij}\geq(\leq){p}_{ij}$ for any $i$, $j$.

###  2.2 Effects of a characteristic intervention

In this subsection, we consider the impact of characteristic intervention. In
reality, the characteristics of players can be increased by subsidy, or
decreased by taxation (See, for example, Galeotti et al. (2020) for further
illustrations of changing $\boldsymbol{\theta}$.) The characteristic
intervention changes the characteristic vector $\boldsymbol{\theta}$ to
$\boldsymbol{\hat{\theta}}$. The game after intervention
$\Gamma\left(\mathbf{G},\boldsymbol{\hat{\theta}}\right)$ reaches a new
equilibrium, denoted as $\mathbf{\hat{x}}^{\ast}$. Define
$\Delta\boldsymbol{\theta}:=\boldsymbol{\hat{\theta}}-\boldsymbol{\theta}$ as
the differences in players’ characteristics and
$\Delta\mathbf{x}^{\ast}=\mathbf{\hat{x}}^{\ast}-\mathbf{x}^{\ast}$ as the
changes in equilibrium actions. Since interventions can be targeted, not every
player is equally affected, thus $\Delta\theta_{i}$ may not have the same sign
or magnitude as $\Delta\theta_{j}$. Define $S=\left\\{i\in
N:\Delta\theta_{i}\neq 0\right\\}$ as the set of players involved in this
characteristic intervention and we rewrite $\Delta\boldsymbol{\theta}$ as
$\begin{bmatrix}\mathbf{0}\\\ \Delta\boldsymbol{\theta}_{S}\end{bmatrix}$
after suitable relabelling of players. That is, characteristics of players in
$S$ are changed by $\Delta\boldsymbol{\theta}_{S}$, while characteristics of
players in its complement $S^{C}$ are not affected. The following Lemma
summarizes the effects of a characteristic intervention.

######  Lemma 1.

After characteristic intervention
$\Delta\boldsymbol{\theta}=\begin{bmatrix}\mathbf{0}\\\
\Delta\boldsymbol{\theta}_{S}\end{bmatrix}$, the change in equilibrium is

$\Delta\mathbf{x}_{A}^{\ast}=\mathbf{M}_{AS}\left(\mathbf{G}\right)\Delta\boldsymbol{\theta}_{S}$
(5)

for any subset $A\subseteq N$. Moreover, the change in the aggregate action is

$\Delta x^{\ast}=\sum_{i\in N}\Delta
x_{i}^{*}=\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\Delta\boldsymbol{\theta}_{S}\text{.}$
(6)

This Lemma is straightforward according to equation (4) since the network
structure is fixed during the intervention, and the equilibrium action profile
$\mathbf{x}^{\ast}$ is linear in the characteristics vector
$\boldsymbol{\theta}$ with sensitivity matrix given by
$\mathbf{M}(\mathbf{G})$. In particular, consider a characteristic
intervention at a single node $S=\\{j\\}$ by $\Delta\theta_{j}$, then for
$A=\\{i\\}$, $\Delta
x_{i}^{\ast}=m_{ij}\left(\mathbf{G}\right)\Delta\theta_{j}$ by Lemma 1. The
marginal contribution of $j$’s characteristics on $i$’s equilibrium behavior
is exactly $m_{ij}(\mathbf{G})$: the total number of walks from $i$ to $j$
with length discount $\delta$ in the network. Summing over all $i$, the
marginal contribution of $j$’s characteristics on the aggregate effort is just
$\sum_{i\in N}m_{ij}(\mathbf{G})=\sum_{i\in
N}m_{ji}(\mathbf{G})=b_{j}\left(\mathbf{G}\right)$.999We exploit the symmetry
of matrix $\mathbf{M}$ here. In other words, we have

$\frac{\partial x^{\ast}}{\partial{\theta}_{j}}=\frac{\partial\\{\sum_{i\in
N}x_{i}^{\ast}\\}}{\partial{\theta}_{j}}=b_{j}(\mathbf{G}).$ (7)

When characteristics of multiple players are modified during the intervention
(so $S$ contains multiple players), by Lemma 1, we observe a form of
linearity: the change of player $i$’s equilibrium action is simply the sum,
over $j$ in $S$, of the effect caused by $j$, i.e., $\Delta
x_{i}^{\ast}=\sum_{j\in S}m_{ij}\left(\mathbf{G}\right)\Delta\theta_{j}$. In
other words,

$\frac{\partial\mathbf{x}_{A}^{\ast}}{\partial\boldsymbol{\theta}_{S}}=\mathbf{M}_{AS}\left(\mathbf{G}\right),\mbox{for
any subset $A\subseteq N$.}$ (8)

As we will see in next subsection, this desirable feature of linearity does
not hold for structural intervention, the effects of which are nonlinear and
hence more complex to analyze.

###  2.3 Effects of a structural intervention

In this subsection, we study the impact of structural intervention, i.e.,
changing $\mathbf{G}$ to $\mathbf{\hat{G}}$. The equilibrium action profile
changes from $\mathbf{x}^{*}$ in the original game
$\Gamma\left(\mathbf{G},\boldsymbol{\theta},\delta\right)$ to
$\mathbf{\hat{x}}^{*}$ in the new game
$\Gamma\left(\mathbf{\hat{G}},\boldsymbol{\theta},\delta\right)$. Define
$\mathbf{C}=\mathbf{\hat{G}}-\mathbf{G}$ as the change in the network
structure, and
$\Delta\mathbf{\hat{x}}^{*}=\mathbf{\hat{x}}^{\ast}-\mathbf{x}^{\ast}$ as the
change in equilibrium actions. Structural interventions may occur when new
links are formed and/or existing links or nodes are deleted. The matrix
$\mathbf{C}=\left(c_{ij}\right)_{n\times n}$ is symmetric with entries in
$\left\\{1,0,-1\right\\}$. In particular, $\mathbf{C}$ is not necessarily a
non-negative matrix. Let $S=\left\\{i\in N:c_{ij}\neq 0\text{ for some }j\in
N\right\\}$ denote the set of players involved in this intervention.
Rearranging the order of players if necessary, we can represent the
intervention matrix $\mathbf{C}$ by the following block matrix
$\begin{bmatrix}\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&\mathbf{C}_{SS}\end{bmatrix}.$

To state the next result regarding the effects of the structural intervention
$\mathbf{C}$, we define an $|S|$-dimensional vector
$\boldsymbol{\Delta\theta}_{S}^{\ast}$ as follows:

$\boldsymbol{\Delta\theta}_{S}^{\ast}\equiv\delta\mathbf{C}_{SS}\left(\mathbf{I}-\delta\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{C}_{SS}\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right).$
(9)

Note that this vector can be easily computed using centralities measures
before the intervention (such as $\mathbf{b}_{S}\left(\mathbf{G}\right)$ and
$\mathbf{M}_{SS}\left(\mathbf{G}\right)$), and the intervention matrix
$\mathbf{C}_{SS}$.

######  Lemma 2 (Equivalence between structural intervention and
characteristics intervention).

Start with $\Gamma\left(\mathbf{G},\boldsymbol{\theta},\delta\right)$, a
structural intervention $\mathbf{C}=\begin{bmatrix}\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&\mathbf{C}_{SS}\end{bmatrix}$ has the same effects on equilibrium
actions as a characteristics intervention
$\widetilde{\Delta\boldsymbol{\theta}}\equiv\begin{bmatrix}\mathbf{0}\\\
\boldsymbol{\Delta\theta}_{S}^{\ast}\end{bmatrix},$ where
$\boldsymbol{\Delta\theta}_{S}^{\ast}$ is given in equation (9).

The main idea behind Lemma 2 is very simple. An equilibrium is a fixed point
of the best-response mapping, which, in the framework of BCZ, is linearly
additively separable in actions $\mathbf{x}$ and characteristics
$\boldsymbol{\theta}$. That is, $\mathbf{x}^{\ast}$ is an equilibrium of game
$\Gamma\left(\mathbf{G},\boldsymbol{\theta},\delta\right)$ if and only if
$\mathbf{x}^{\ast}=\boldsymbol{\theta}+\delta\mathbf{G}\mathbf{x}^{\ast}$. We
could re-interpret the post-intervention equilibrium $\mathbf{\hat{x}}^{\ast}$
as a fixed point in the pre-intervention game after modifying the
characteristics vector of players in $S$ from $\boldsymbol{\theta}_{S}$ to
$\boldsymbol{\theta}_{S}+\boldsymbol{\Delta\theta}_{S}^{\ast}$ with
$\boldsymbol{\Delta\theta}_{S}^{\ast}=\delta\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{\ast}$.101010Formally,
the post-intervention equilibrium action profile $\mathbf{\hat{x}}$ solves
$\displaystyle\mathbf{\hat{x}}^{\ast}$ $\displaystyle=$
$\displaystyle\boldsymbol{\theta}+\delta\left(\mathbf{G}+\mathbf{C}\right)\mathbf{\hat{x}}^{\ast}=\left(\boldsymbol{\theta}+\delta\mathbf{C}\mathbf{\hat{x}}^{\ast}\right)+\delta\mathbf{G\hat{x}}^{\ast}=\left(\boldsymbol{\theta}+\begin{bmatrix}\mathbf{0}\\\
\delta\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{*}\end{bmatrix}\right)+\delta\mathbf{G\hat{x}}^{\ast}.$
Put differently, we have
$\mathbf{\hat{x}}^{\ast}=\mathbf{b}(\mathbf{G},\boldsymbol{\theta}+\widetilde{\Delta\boldsymbol{\theta}})$
with $\widetilde{\Delta\boldsymbol{\theta}}=\begin{bmatrix}\mathbf{0}\\\
\delta\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{*}\end{bmatrix}$. To determine
$\mathbf{\hat{x}}_{S}^{\ast}$, which is endogenous, we make use of the
following identity:

$\underbrace{\mathbf{\hat{x}}_{S}^{\ast}-\mathbf{b}_{S}}_{=\Delta\mathbf{x}_{S}^{\ast}}=\mathbf{M}_{SS}\underbrace{\left(\delta\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{\ast}\right)}_{=\boldsymbol{\Delta\theta}_{S}^{\ast}}.$

The above identity follows from equation (5): the term on the left-hand side
is just the change in the equilibrium profile of $S$ (recall $\mathbf{b}_{S}$
is just the pre-intervention effort profile of $S$), and the term on the
right-hand side follows from the above equivalent characteristical re-
interpretation of structural intervention.

Lemma 2 demonstrates a simple equivalence between a structural intervention
and an _endogenously determined_ characteristics intervention. Lemma 2,
combined with Lemma 1, greatly simplifies the analysis of effects of
structural interventions in networks. There are three key features worth
noting. The first is _locality_. The vector of the equivalent characteristics
intervention is non-zero only on $S$ (the set of nodes involved in the
intervention) and it only requires information of $\mathbf{M(G)}$ and
$\mathbf{b(G)}$ of nodes in $S$, i.e., the entries of
$\mathbf{M}_{SS}(\mathbf{G})$ and $\mathbf{b}_{S}(\mathbf{G})$. This feature
is appealing, as in many applications $|S|$ is relatively small, compared with
the network size $|N|$ (see our applications in subsequent Sections). Locality
makes the expression of the effects of structural interventions much more
succinct, hence easier to interpret.

The second is _convenience_. On top of the intervention $\mathbf{C}$, the
determination of the equivalent characteristics intervention uses the Leontief
inverse matrix $\mathbf{M}(\mathbf{G})$ and Katz-Bonacich centralities
$\mathbf{b}(\mathbf{G},\boldsymbol{\theta})$ evaluated _before_ the
intervention, rather than indices of post-intervention network
$\hat{\mathbf{G}}$. Since these information about pre-intervention
centralities is usually available, the amount of additional information to
evaluate structural intervention is minimal. The second feature also makes the
comparative analysis across different structural interventions manageable. To
compare the effects of two structural interventions, say $\mathbf{C^{\prime}}$
and $\mathbf{C^{\prime\prime}}$, we keep track of the differences in the
vectors of characteristics interventions by mainly focusing on the differences
between $\mathbf{C^{\prime}}$ and $\mathbf{C^{\prime\prime}}$, as information
about centralities comes from a common source: the pre-intervention
equilibrium.

Thirdly, characteristic intervention affects players’ equilibrium efforts
linearly with sensitivity matrix $\mathbf{M}\left(\mathbf{G}\right)$ (see
Lemma 1). In contrast, the impact of structural intervention is much more
involved. Using the Newmann series definition (or the walk counting
explanations) of centrality measures, we obtain the following decomposition of
the changes in actions:

$\displaystyle\Delta\mathbf{x}^{\ast}$ $\displaystyle=$
$\displaystyle\left(\mathbf{I}-\delta\left(\mathbf{G+C}\right)\right)^{-1}\boldsymbol{\theta}-\left(\mathbf{I}-\delta\mathbf{G}\right)^{-1}\boldsymbol{\theta}$
$\displaystyle=$
$\displaystyle\left\\{\delta\mathbf{C}+\delta^{2}\left(\left(\mathbf{G+C}\right)^{2}-\mathbf{G}^{2}\right)+\delta^{3}\left(\left(\mathbf{G+C}\right)^{3}-\mathbf{G}^{3}\right)+\cdots\right\\}\boldsymbol{\theta}\text{.}$

For each $k=1,2,\cdots$, the term
$\left(\mathbf{G+C}\right)^{k}-\mathbf{G}^{k}$ keeps track of changes in the
number of walks with length $k$ due to this intervention $\mathbf{C}$.
Evaluating this term directly is increasingly complicated as $k$ gets larger.
By transforming the structural intervention to an _endogenously determined_
characteristic intervention, Proposition 1 bypasses most of the challenging
issues associated with the evaluation of structural interventions.

The following Proposition immediately follows from Lemmas 1 and 2.

######  Proposition 1 (Effects of structural interventions).

After structural intervention
$\mathbf{C}=\begin{bmatrix}\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&\mathbf{C}_{SS}\end{bmatrix}$,

  1. (i)

the change in equilibrium is

$\Delta\mathbf{x}_{A}^{\ast}=\mathbf{M}_{AS}\left(\mathbf{G}\right)\Delta\boldsymbol{\theta}_{S}^{\ast},$
(10)

for any subset $A\subseteq N$; and

  2. (ii)

the change in the aggregate action is

$\Delta
x^{\ast}=\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\Delta\boldsymbol{\theta}_{S}^{\ast},$
(11)

where $\boldsymbol{\Delta\theta}_{S}^{\ast}$ is given in equation (9).

Proposition 1 is applicable to an arbitrary structural intervention. In what
follows, we present several examples of structural interventions, which are
commonly used in the network literature, though under different contexts.

######  Example 1 (Different types of structural interventions).

  1. (i)

Creating a new link between $i$ and $j$:
$\mathbf{C}=\mathbf{E}_{ij}$.121212For instance, Golub and Lever (2010)
evaluate the impact of adding a link (a weak tie) between two disconnected
networks on the eigenvalue centralities.Here $\mathbf{E}_{ij}$ denotes the
matrix with $1$ on $\left(i,j\right)$ and $\left(j,i\right)$ entries, $0$ on
all the other entries.

  2. (ii)

Removing an existing link between $i$ and $j$:
$\mathbf{C}=-\mathbf{E}_{ij}$.131313For instance,Ballester et al. (2010)
investigate the impact of removing a link in a delinquent network.

  3. (iii)

Removing all the links associated with a given player $i$:
$\mathbf{C}=-\sum_{j:g_{ij}=1}\mathbf{E}_{ij}$.141414Ballester et al. (2006)
study the impact of removing a single node from the criminal network. Also see
Bramoullé et al. (2016) for a recent survey of key player.

  4. (iv)

Creating new links while removing existing links simultaneously.151515For
instance, Cai and Szeidl (2018) show that business meetings, which help firms
build up social connections, have positive impacts on firm performances. König
et al. (2014) study a model of network formation with new links added and
existing links removed dynamically. To study the efficient network design with
fixed number of total links, Belhaj et al. (2016) analyze the effects of a
_link swap_ , an operation which cuts an existing link between $i$ and $j$,
while adds a new link between $k$ and $l$ (in our language,
$\mathbf{C}=-\mathbf{E}_{ij}+\mathbf{E}_{kl}$ for a swap).

Proposition 1 (i) provides the effect of interventions for each player. In
many applications, the designer may care about the aggregate action, or even
its sign. Obviously, if links are created, i.e.,
$\mathbf{C}\succeq\mathbf{0}$, the aggregate action unambiguously increases.
Likewise, when links are removed, i.e., $\mathbf{C}\preceq\mathbf{0}$, the
aggregate action decreases. Suppose that new links are formed and meanwhile
existing links are removed in the intervention $\mathbf{C}$, some players
become more active, while others are less active with the net effect on
aggregate action less clear-cut to check. Proposition 1 (ii) provides a
necessary and sufficient condition. In the next Corollary, we present a
sufficient condition to guarantee that a structural intervention leads to
higher aggregate action. Such a condition is much simpler to check than that
in Proposition 1 (ii).161616To use Proposition 1 (ii), we need to check the
sign of
$\mathbf{b}_{S}^{\prime}\delta\mathbf{C}_{SS}\left(\mathbf{I}-\delta\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{C}_{SS}\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)$.

######  Corollary 1.

Assume $\boldsymbol{\theta}=\mathbf{1}$. In network
$\left(N,\mathbf{G}\right)$, a structural intervention $\mathbf{C}$ satisfying

$\mathbf{b}^{\prime}\mathbf{C}\mathbf{b}=\mathbf{b}_{S}^{\prime}\mathbf{C}_{SS}\mathbf{b}_{S}\geq(>)0$
(12)

always increases (strictly increases) aggregate equilibrium action, where
$\mathbf{b}=\mathbf{b}\left(\mathbf{G},\mathbf{1},\delta\right)$.

Corollary 1 is a direct consequence of the following inequality:

$\underbrace{b(\mathbf{G}+\mathbf{C})-b(\mathbf{G})}_{:=\Delta
x^{*}}\geq\delta\mathbf{b}^{\prime}\left(\mathbf{G}\right)\mathbf{C}\mathbf{b}(\mathbf{G}),$
(13)

which, under the condition $\boldsymbol{\theta}=\mathbf{1}$, provides a lower
bound on the change of aggregate action for any intervention $\mathbf{C}$ in
$\Gamma(\mathbf{G},\mathbf{1})$. The above inequality employs a convexity
property of the equilibrium aggregation effort $b(\mathbf{G})$ as a function
of the network topology $\mathbf{G}$, as the term on the right-hand side can
be viewed as the linear approximation (hence an under-estimation due to
convexity) of the change of aggregate action. The condition stated in
Corollary 1 is sufficient, but in general not necessary. An intervention which
does not satisfy the condition in Corollary 1 could still improve aggregate
action. Since $c_{ij}\in\\{0,\pm 1\\}$, we can reformulate the expression in
Corollary 1 as follows

$\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\mathbf{C}_{SS}\mathbf{b}_{S}\left(\mathbf{G}\right)=\sum_{i,j\in
S}c_{ij}b_{i}b_{j}=\left(\sum_{(i,j):c_{ij}=1}b_{i}b_{j}\right)-\left(\sum_{(i,j):c_{ij}=-1}b_{i}b_{j}\right).$
(14)

If we define the product Katz-Bonacich centralities of two nodes associated
with a link the _l-value_ of that link, then Corollary 1 states that if sum of
_l-values_ over new links in an intervention $\mathbf{C}$ exceeds the sum of
_l-values_ over removed links in $\mathbf{C}$, the aggregate action must
increase after this intervention. To see some immediate implication of this
Corollary, we present two simple examples.

  1. 1.

First, we consider a link reallocation in the form of
$\mathbf{C}=-\mathbf{E}_{ij}+\mathbf{E}_{kl}$, i.e., removing the link between
$i$ and $j$, while adding a new link between $k$ and $l$.171717To make such an
intervention $\mathbf{C}$ legitimate for network $\mathbf{G}$, we assume
$g_{ij}=1$ and $g_{kl}=0$. Moreover, we assume at least three elements of
$\\{i,j,k,l\\}$ must be distinct. Then, Corollary 1 implies that such a
reallocation of link increases aggregate action if $b_{i}b_{j}<b_{k}b_{l}$. In
particular it holds when $b_{i}<b_{k}$ and $b_{j}\leq b_{l}$. Whenever the new
formed link contains nodes with higher Katz-Bonacich centralities than the
removed link, this type of link reallocation increases aggregate action.

  2. 2.

Second, we consider a link swap
$\mathbf{\tilde{C}}=-\mathbf{E}_{ij}+\mathbf{E}_{il}$ (a specific reallocation
with $i=k$), i.e., removing the link between $i$ and $j$, while adding a new
link between $i$ and $l$. Such a swap, by Corollary 1, increases aggregation
action whenever $b_{j}<b_{l}$. Cutting an old link with a neighbouring node
$j$ of node $i$ with lower Katz-Bonacich centrality, while creating a new link
from $i$ to another unconnected node $l$ with higher Katz-Bonacich centrality
makes the whole group overall more active.

In both examples, we identify simple ways to reallocate or swap links of
existing network to improve aggregate action. This argument is complementary
to the critical Lemma (Lemma 1) in Belhaj et al. (2016) which states that
certain type of link swap or reallocation leads to higher aggregate
welfare.181818The planer’s objective in Belhaj et al. (2016) is aggregate
welfare, not aggregate effort as in Corollary 1. But the underlying driving
forces behind Lemma 1 in their paper are similar to ours. See our companion
paper Sun et al. (2021) for related discussions and further implications of
this Corollary on efficient network design.

Another potential application of Corollary 1 is to provide local optimality
conditions for constrained network optimization problem. Take a set of
networks $\mathcal{G}$, if $\mathbf{G}^{\ast}\in\mathcal{G}$ solves the
problem: $\max{x}^{\ast}(\mathbf{G^{\prime}})$ subject to
$\mathbf{G}^{\prime}\in\mathcal{G}$. Then the optimality of
$\mathbf{G}^{\ast}$ immediately imply that
$\mathbf{b}^{\prime}\mathbf{C}\mathbf{b}\leq 0$ for any
$\mathbf{C}=\mathbf{G^{\prime}}-\mathbf{G}^{\ast}$ with
$\mathbf{G}^{\prime}\in\mathcal{G}$, where
$\mathbf{b}=\mathbf{b}\left(\mathbf{G}^{\ast}\right)$.191919Since the network
structure we consider in this paper is discrete (the bilateral link is either
zero or one), not continuous, the standard KKT conditions for optimality do
not directly apply. Focusing on the class of weighted and directed networks,
Li (2020) employ KKT conditions to show that optimal networks in his setting
are generalized nested split graphs. For certain specification of
$\mathcal{G}$, the combinations of these local necessary conditions are rich
enough to infer useful structural properties of the resulting optimal
network.202020In a companion paper Sun et al. (2021) on designing efficient
networks sequentially, we show that the optimal network $\mathbf{G}^{t}$ in
each step $t$ must be contained in an important class of networks called
quasi-complete graphs.

We mainly focus on the network model in Ballester et al. (2006). As shown by
Bramoullé et al. (2014), our results regarding the effects of interventions on
networks carry over to a more general class of utility functions that induce
linear best responses.

Two main forms of interventions are studied in this Section. Lemma 1 focuses
on general characteristic intervention. Proposition 1 and Corollary 1 provide
a unified approach to analyze the impacts of structural intervention on the
equilibrium behavior at the individual and aggregate level. The gist of Lemma
2 is to offer a new perspective of identifying a structural intervention and
an _endogenously determined_ characteristic intervention. Restricting to more
specific types of structural interventions in subsequent applications, we
illustrate several advantages of our theory of interventions in networks,
compared with existing approaches in the literature.

##  3 The most wanted criminal(s) in delinquent networks

###  3.1 The key group problem and the intercentrality index

Consider the following optimization problem:

$\underset{S\subseteq N,|S|\leq
k}{\min}b\left(\mathbf{G}_{S^{C}S^{C}},\boldsymbol{\theta}_{S^{C}}\right),$
(15)

which is motivated by the application of criminal network (see Ballester et
al. (2006, 2010) for detailed discussion): the government, facing a group of
criminals in a network $\mathbf{G}$, wants to identify a subset of criminals
$S$ of $N$ (as known as _the most wanted_) so that the total action (criminal
effort in this context) in the remaining network is minimized after removing
$S$ from the original network $\mathbf{G}$.212121It is well established that
criminality is a social action with strong peer influences (see, for example,
Jerzy (2001); Mark (2002); Patacchini and Zenou (2012)). Note that, before the
intervention, the criminals play a game
$\Gamma\left(\mathbf{G},\boldsymbol{\theta}\right)$ with total criminal
activities $b\left(\mathbf{G},\boldsymbol{\theta}\right)$; after the removal
of $S$ from $\mathbf{G}$, the remaining criminals $S^{C}$ play the game
$\Gamma(\left(\mathbf{G}_{S^{C}S^{C}},\boldsymbol{\theta}_{S^{C}}\right)$,
which leads to the objective stated in program (15). To accommodate the
constrain from the government side (for instance, limited police resource),
the size of $S$ is bounded above by a positive integer $k$.

Problem (15) is called the key player problem for $k=1$, and the key group
problem in general for $k\geq 2$. Ballester et al. (2010) introduce the
following definition.

######  Definition 2.

The intercentrality index of group $S$ in network $\left(N,\mathbf{G}\right)$
is defined as

$d_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)\equiv
b\left(\mathbf{G},\boldsymbol{\theta}\right)-b\left(\mathbf{G}_{S^{C}S^{C}},\boldsymbol{\theta}_{S^{C}}\right)\text{.}$

The intercentrality of group $S$,
$d_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)$, is the precisely reduction
of aggregate activity by removing group $S$ and it can be decomposed into two
parts: a direct effect by the removed players in $S$, $\sum_{l\in
S}b_{l}\left(\mathbf{G},\boldsymbol{\theta}\right)$, and an indirect effect
due to the decreasing of equilibrium actions of the remaining players $j\in
S^{C}$, $\sum_{j\in
S^{C}}\left\\{b_{j}\left(\mathbf{G},\boldsymbol{\theta}\right)-b_{j}\left(\mathbf{G}_{S^{C}S^{C}},\boldsymbol{\theta}_{S^{C}}\right)\right\\}$.
The next Lemma gives a simple expression for $d_{S}$.

######  Lemma 3.

For any $S\subseteq N$, we have

$d_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)=\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right).$
(16)

Figure 1: Key player problem from the angle of view from characteristic
intervention

For illustration, we consider Figure 1. Imagine a thought experiment in which
we change $\theta_{4}$ by
$\Delta\theta_{4}^{\ast}=-\frac{b_{4}\left(\mathbf{G},\boldsymbol{\theta}\right)}{m_{44}\left(\mathbf{G}\right)}$
while keeping other $\theta_{i},i\neq 4$ the same. By Lemma 1, after this
characteristic intervention $\Delta\theta_{4}^{\ast}$, each $i$’s equilibrium
action is changed by $m_{i4}(\mathbf{G})\Delta\theta_{4}^{\ast}$, and the
aggregate action is changed by
$b_{4}(\mathbf{G})\Delta\theta_{4}^{\ast}=-b_{4}(\mathbf{G},\mathbf{1})\frac{b_{4}\left(\mathbf{G},\boldsymbol{\theta}\right)}{m_{44}\left(\mathbf{G}\right)}$.
This critical value $\Delta\theta_{4}^{\ast}$ is picked so that player $4$
would be exactly choosing zero in equilibrium after this characteristic
intervention:
$b_{4}\left(\mathbf{G},\boldsymbol{\theta}\right)+m_{44}(\mathbf{G})\Delta\theta_{4}^{\ast}=0$.
Given that player 4 is inactive in equilibrium, the other three players
effectively play a network game with node $4$ removed. In other words, such a
change of $\theta_{4}$ by $\Delta\theta_{4}^{\ast}$ exactly replicates the
impacts of removing $4$ from the network in terms of equilibrium choice. As a
result, the total impact of removing $4$ on the aggregate equilibrium activity
is given by
$d_{4}(\mathbf{G},\boldsymbol{\theta})=b_{4}(\mathbf{G},\mathbf{1})\frac{b_{4}\left(\mathbf{G},\boldsymbol{\theta}\right)}{m_{44}\left(\mathbf{G}\right)}$.

The idea presented in Figure 1 for a single node removal can be easily
extended to the setting with multiple nodes removed simultaneously. The key
observation is that the removal of group $S$ from the network has the same
effects as changing the characteristics of players in $S$ by

$\Delta\boldsymbol{\theta}_{S}=-\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)\text{.}$

According to equation (6), this characteristic intervention leads to the
reduction of aggregate action by
$-\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\Delta\boldsymbol{\theta}_{S}=d_{S}(\mathbf{G},\boldsymbol{\theta})$
in equation (16). Therefore, Lemma 3 follows immediately after showing the
equivalence between a structural intervention (removal of a set of nodes) to a
characteristic intervention (decreasing $\boldsymbol{\theta}_{S}$ by
$\Delta\boldsymbol{\theta}_{S}$). Consequently, the key group program (15) can
be reformulated as

$\underset{S\subseteq N,|S|\leq
k}{\max}d_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)=\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right).$
(17)

When $k=1$, taking $S=\left\\{i\right\\}$, we obtain
$d_{i}(\mathbf{G},\boldsymbol{\theta})=\frac{b_{i}\left(\mathbf{G}\right)b_{i}\left(\mathbf{G},\boldsymbol{\theta}\right)}{m_{ii}\left(\mathbf{G}\right)}$
by equation (16), which coincides with key player index in Ballester et al.
(2006). To the best of our knowledge, there is no analogous simple expression
for the key group index (or the intercentrality index) with $k\geq 2$, except
for the definition. As a non-trivial generalization of the key player index,
Lemma 3 uses self-loops and centralities of the removed players to construct
the key group index. Thus, we can conveniently identify the key group from the
information in the matrix $\mathbf{M}\left(\mathbf{G}\right)$ without re-
computing the new equilibrium after the removal of nodes. Furthermore, the
analytically simplicity of the expression in Lemma 3 enables us to make
inference regarding the key group.

######  Proposition 2.

Assume $\boldsymbol{\theta}=\mathbf{1}$. Consider two subsets, $S$ and
$S^{\prime}$,

  1. (i)

if $S\subseteq(\subset)S^{\prime}$, then
$d_{S}\left(\mathbf{G},\boldsymbol{1}\right)\leq(<)d_{S^{\prime}}\left(\mathbf{G},\boldsymbol{1}\right)$;

  2. (ii)

if $\left|S\right|=\left|S^{\prime}\right|$,
$\mathbf{b}_{S}\left(\mathbf{G}\right)\preceq\mathbf{b}_{S^{\prime}}\left(\mathbf{G}\right)$,
and
$\mathbf{M}_{SS}\left(\mathbf{G}\right)\succeq\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)$,
then $d_{S}\left(\mathbf{G},\boldsymbol{1}\right)\leq
d_{S^{\prime}}\left(\mathbf{G},\boldsymbol{1}\right)$.

Proposition 2 (i) is rather intuitive: removing a larger group induces a more
significant impact. In particular, to search for the optimal $S^{\ast}$ in
equation (15), it is without loss of any generality to consider $S$ with
$|S|=k$. Proposition 2 (ii) shows that, when comparing groups with the same
size, group $S^{\prime}$ with greater Katz-Bonacich centralities,
$\mathbf{b}_{S^{\prime}}$, and fewer number of walks within any pair of nodes
in $S^{\prime}$ (measured by
$\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)$) has a larger
intercentrality. These monotonicity results are useful in reducing the
possible choices of candidates for the key group problem, as shown in Example
2 below.222222Ballester et al. (2010), in their Example 2 on the key group
problem with $k=2$, illustrate similar observations as our Proposition 2 (ii).

######  Example 2.

Consider a regular network depicted in Figure 2. We consider two cases: $k=1$
(the key player problem) and $k=2$ (the key group problem). Assume
$\boldsymbol{\theta=1}$ and $\delta=0.2$, then all nodes have the same
unweighted Katz-Bonacich centralities:
$b_{i}(\mathbf{G},\mathbf{1})=b_{j}(\mathbf{G},\mathbf{1})$ for any
$i,j$.232323This network is regular with degree $d=3$, so
$\mathbf{G}^{k}\mathbf{1}=3^{k}\mathbf{1},\forall k,$ and
$b_{i}(\mathbf{G},\mathbf{1})=\frac{1}{1-d\delta}=2.5,\forall i$. This same
network is also analyzed in Calvó-Armengol and Jackson (2004) and Zhou and
Chen (2015) under different contexts.

Figure 2: A regular network with degree three

  1. (i)

Assume $k=1$ so that we can only remove one node ($|S|=1$). For $S=\\{i\\}$,
$d_{i}=\frac{b_{i}^{2}}{m_{ii}}$ by Lemma 3. Since $b_{i}$ is the same for all
$i$, so $d_{l}>d_{j}\Longleftrightarrow m_{ll}<m_{jj}$, consistent with
Proposition 2 (ii). Table 1 summarizes $m_{ii},d_{i}$ for each equivalent type
of player.242424For the key player problem ($k=1$), there are only three
equivalent types due to symmetry of the network. For instance, players 1 and 6
are equivalent. Similarly, $2,5,7,10$ are mutually equivalent. The key player
index is negatively related to self-loops. Therefore, player 1 (equivalently
player 6) is the key player.

Table 1: The key player $S$ | $m_{SS}\left(\mathbf{G}\right)$ | $d_{S}\left(\mathbf{G},\boldsymbol{1}\right)$
---|---|---
{1} | 1.1688 | 5.3474*
{2} | 1.1981 | 5.2166
{3} | 1.2162 | 5.1390
Table 2: The key group $S$ | $d_{S}\left(\mathbf{G},\boldsymbol{1}\right)$ | $S$ | $d_{S}\left(\mathbf{G},\boldsymbol{1}\right)$
---|---|---|---
{1,2} | 8.4725 |  {2,3} | 8.0331
{1,3} | 9.3419 |  {2,5} | 8.9529
{1,6} | 8.7506 |  {2,7} | 10.2938*
{1,7} | 10.0150 |  {2,8} | 10.2863
{1,8} | 10.2081 |  {3,4} | 7.8174
|  |  {3,8} | 10.2431
  2. (ii)

Assume $k=2$, i.e, we can remove two nodes ($|S|=2$). Table 2 shows
intercentralities of all equivalent types of groups with size $k=2$.252525For
this key group problem with $k=2$, there are exactly $11$ types up to
equivalence as shown in Table 2. Note that node $2$ is equivalent to $7$ for
the key player problem ($m_{22}=m_{77}$ and $b_{2}=b_{7}$), but $\\{1,2\\}$
and $\\{1,7\\}$ are not equivalent for the key group problem as $m_{12}\neq
m_{17}$. By Proposition 2 (ii), for $S=\\{i,j\\}$, $d_{S}$ is proportional to
$\mathbf{1}^{\prime}\left(\mathbf{M}_{SS}\right)^{-1}\mathbf{1=}\frac{m_{ii}+m_{jj}-2m_{ij}}{m_{ii}m_{jj}-m_{ij}^{2}}$
(note that $b_{i}=b_{j}$ for any $i,j$), and decreases in $m_{ii},m_{ij}$ and
$m_{jj}$. Observe that $d_{\\{2,7\\}}$ is higher than $d_{\\{2,5\\}}$. Both
sets $\\{2,7\\}$ and $\\{2,5\\}$ share the same player 2, furthermore
$m_{77}=m_{55}=1.1981$, but $m_{27}=0.0162<m_{25}=0.1981$, implying
$d_{\\{2,7\\}}>d_{\\{2,5\\}}$.262626By the same token, we can show
$d_{\\{1,2\\}}<d_{\\{1,7\\}}$, $d_{\\{1,3\\}}<d_{\\{1,8\\}}$,
$d_{\\{2,3\\}}<d_{\\{2,8\\}}$. In fact, as demonstrated by Table 2, group
$S^{\ast}=\left\\{2,7\right\\}$ is the key group.

For the key player problem with $k=1$, comparing the selfloop $m_{ii}$ is
suffice to determine who is the most wanted player in the network in Figure 2.
The group version of intercentrality requires more detailed information beyond
selfloops. In particular, the number of walks between the players in $S$,
$m_{ij}$, also matters, as shown from the comparison between $\\{2,7\\}$ and
$\\{2,5\\}$. Nevertheless, the monotonicity result in Proposition 2 (ii)
enables us to rule out many dominated groups for consideration.

Another interesting point is the comparison between
$S^{\ast}=\left\\{2,7\right\\}$ and $\hat{S}=\\{1,6\\}$. Both player 1 and 6
are key players with $k=1$ (see Table 1), but $\hat{S}=\\{1,6\\}$, the
combination of two key players, does not form the key group with $k=2$ as
$d_{\\{1,6\\}}<d_{\\{2,7\\}}$.272727Note that Proposition 2 (ii) is not
applicable here as the matrix $\mathbf{M}_{\hat{S}\hat{S}}$ does not dominate
$\mathbf{M}_{S^{*}S^{*}}$ entry by entry ($m_{22}=m_{77}>m_{11}=m_{66}$, but
$m_{27}<m_{16}$). Simply collecting all the key players together does not
solve the key group problem. In fact, in this example, the key group with
$k=2$ does not include any key player with $k=1$. These observations point to
the computational complexity of the key group problem, which is NP-hard (see
Proposition 5 in Ballester et al. (2010) and the detailed discussion therein).

###  3.2 A view from walk counting

Given the close relationship between equilibrium action in the game and Katz-
Bonacich centralities in the network, we offer an explanation of the
intercentrality index from the view of walk counting.

In network $\left(N,\mathbf{G}\right)$, $m_{ij}\left(\mathbf{G}\right)$
summerizes the total number of walks from $i$ to $j$ (with length discount
$\delta$). In particular, for a non-empty set $S\subset N$,
$m_{ij}\left(\mathbf{G}\right)$ counts the walks passing one or more nodes in
$S$, as well as the other walks never hitting any nodes in $S$. The former
types of walks with length discount exactly measure the importance of group
$S$ in the key group problem since those walks do not contribute to the
centrality in remaining network $\mathbf{G}_{S^{C}S^{C}}$. To distinguish
these two types of walks and facilitate the walk counting, we introduce the
following notation.

######  Definition 3.

Fixing a non-empty proper subset $S$ of $N$ in network
$\left(N,\mathbf{G}\right)$, for any $i$, $j\in N$, we define
$w_{ij}\left(\mathbf{G},S\right)$ as total number of walks with length
discount from $i$ to $j$ that do not pass any node in $S$ with the possible
exception for the starting node $i$ and the ending node $j$. Let
$\mathbf{W}\left(\mathbf{G},S\right)=\left(w_{ij}\left(\mathbf{G},S\right)\right)_{n\times
n}$.

Different from $m_{ij}\left(\mathbf{G}\right)$,
$w_{ij}\left(\mathbf{G},S\right)$ precludes the walks from $i$ to $j$ that
cross group $S$. In particular,
$w_{ij}\left(\mathbf{G},\emptyset\right)=m_{ij}\left(\mathbf{G}\right)$. If
$i$, $j\in S^{C}$, then $w_{ij}\left(\mathbf{G},S\right)$ counts the total
number of walks from $i$ to $j$ that never passing group $S$; If $i\in S^{C}$
and $j\in S$, then $w_{ij}\left(\mathbf{G},S\right)$ counts the total number
of walks from $i$ to $j$ that never passing group $S$ before stopping at node
$j\in S$; If $i$, $j\in S$, then $w_{ij}\left(\mathbf{G},S\right)$ denotes the
total number of walks from $i$ to $j$ that never pass group $S$ except the
starting and ending nodes $i$, $j$.

Since network $\mathbf{G}$ is undirected, matrix
$\mathbf{W}\left(\mathbf{G},S\right)$ is necessarily symmetric: any walk from
$i$ to $j$ that bypasses group $S$ is also a walk from $j$ to $i$ that does
not cross $S$, and vice versa. After suitable relabelling of nodes,
$\mathbf{W}\left(\mathbf{G},S\right)$ can be represented as the following
block matrix:

$\mathbf{W}\left(\mathbf{G},S\right)=\left[\begin{array}[]{cc}\mathbf{W}_{S^{C}S^{C}}\left(\mathbf{G},S\right)&\mathbf{W}_{SS^{C}}\left(\mathbf{G},S\right)\\\
\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)&\mathbf{W}_{SS}\left(\mathbf{G},S\right)\end{array}\right].$

The matrix $\mathbf{M}\left(\mathbf{G}\right)$ can be partitioned in the same
way. We establish the following result.

######  Proposition 3.

For any $S\subseteq N$, the following identities hold:

$\displaystyle\mathbf{W}_{S^{C}S^{C}}\left(\mathbf{G},S\right)$
$\displaystyle=$
$\displaystyle\mathbf{M}_{S^{C}S^{C}}\left(\mathbf{G}\right)-\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)$
(18) $\displaystyle\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)$
$\displaystyle=$
$\displaystyle\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}$
(19) $\displaystyle\mathbf{W}_{SS}\left(\mathbf{G},S\right)$ $\displaystyle=$
$\displaystyle
2\mathbf{I}-\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}$ (20)

In particular, for any $A,B\subseteq N$ and $A\cap B=\emptyset$, then

$\displaystyle\mathbf{W}_{AB}\left(\mathbf{G},A\cup B\right)$
$\displaystyle=\left(\mathbf{M}_{AA}\left(\mathbf{G}\right)\right)^{-1}\mathbf{M}_{AB}\left(\mathbf{G}\right)\left(\mathbf{W}_{BB}\left(\mathbf{G},A\right)\right)^{-1}$
(21)
$\displaystyle=\left(\mathbf{W}_{AA}\left(\mathbf{G},B\right)\right)^{-1}\mathbf{M}_{AB}\left(\mathbf{G}\right)\left(\mathbf{M}_{BB}\left(\mathbf{G}\right)\right)^{-1}$

Proposition 3 characterizes the impacts of removing group $S$ on the total
number of walks between each pair of nodes.292929We provide a view from walk
counting for the identities in Proposition 3 in Appendix B. There are three
points worth noting.

  1. 1.

Equation (18) uses centrality measures in the original network to quantify all
the walk changes in the remaining network when a set of nodes is removed.
Specifically,
$\mathbf{M}_{S^{C}S^{C}}\left(\mathbf{G}\right)-\mathbf{W}_{S^{C}S^{C}}\left(\mathbf{G},S\right)=\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)$
summarizes the reduction of total number of walks between each pair of nodes
in $S^{C}$. When $S=\left\\{i\right\\}$, for any pair $\left(j,k\right)\in
S^{C}$, equation (18) yields to

${m_{jk}}({\mathbf{G}})-{w_{jk}}({\mathbf{G}},\\{i\\})=\frac{{{m_{ji}}\left({\mathbf{G}}\right){m_{ik}}\left({\mathbf{G}}\right)}}{{{m_{ii}}\left({\mathbf{G}}\right)}}\text{.}$

This equation is equivalent to Lemma 1 in Ballester et al. (2006), which
characterizes the change of walks in the network after removing a single node
$i$ and leads to the intercentrality index. Equation (18) extends Ballester et
al. (2006)’s Lemma 1 into the case of removing multiple nodes.

  2. 2.

Equation (19) indicates that the intercentrality measure $d_{S}$ in equation
(16) is precisely the discounted number of walks that pass through group $S$.
To fix idea, we set $\mathbf{\theta=1}$. The intercentrality of group $S$ can
be decomposed according to whether the starting node of such a walk is in $S$
(type I walks) or not (type II walks):

$d_{S}\left(\mathbf{G,1}\right)={{\underbrace{b_{S}\left(\mathbf{G}\right)}_{\text{Term
I}}+\underbrace{\mathbf{1}^{\prime}\mathbf{W}_{S^{C}S}(\mathbf{G},S)\mathbf{b}_{S}\left(\mathbf{G}\right)}_{\text{Term
II}}}\text{.}}$

Term I is precisely the sum of walks with the starting node in $S$, i.e, type
I walks $b_{S}(\mathbf{G})=\sum_{i\in S}{b_{i}(\mathbf{G})}$. Term II exactly
captures the walks that starts with a node in $S^{C}$ and passes group $S$ at
least once, i.e., type II walks. Each walk of type II can be decomposed as the
concatenations of two walks: Consider an arbitrary walk starting from node
$i\in S^{C}$ and ending at $j$ (which may or may not in $S$), which passes the
group $S$ at least once. Let $l\in S$ be the first node that the walk meets
group $S$. Then, this walk can be _uniquely_ decomposed as the concatenations
of a walk from $i$ to $l$ and the other walk from $l$ to $j$. The former
category of walks never cross group $S$ before ending, and therefore, is
summerized by $w_{il}\left(\mathbf{G},S\right)$. The total number of the
latter category of walks, with length discount, is counted by
$m_{lj}\left(\mathbf{G}\right)$. Consequently, the number of type II walks
from $i$ to $j$ is given by $\sum_{l\in
S}w_{il}\left(\mathbf{G},S\right)m_{lj}\left(\mathbf{G}\right)$. Summing over
indices $i\in S^{C}$ and $j\in N$, we obtain term II $\sum_{i\in
S^{C}}\sum_{j\in N}\sum_{l\in
S}w_{il}(\mathbf{G},S)m_{lj}(\mathbf{G})=\mathbf{1}^{\prime}\mathbf{W}_{S^{C}S}(\mathbf{G},S)\mathbf{b}_{S}\left(\mathbf{G}\right)$.
As a whole, the intercentrality of group $S$,
$d_{S}\left(\mathbf{G,1}\right)$, is the discounted number of walks in network
$\left(N,\mathbf{G}\right)$ that pass group $S$ at least once.

  3. 3.

Equation (20) captures the aggregate walks from $i$ to $j$ without passing any
of them during the path. In particular, let $S=\left\\{i,j\right\\}$, then we
have

${w_{ij}}({\mathbf{G}},\\{i,j\\})=\frac{{{m_{ij}}({\mathbf{G}})}}{{{m_{ii}}({\mathbf{G}}){m_{jj}}({\mathbf{G}})-{{\left({{m_{ij}}({\mathbf{G}})}\right)}^{2}}}}\text{.}$

Equation (3) is consistent with Proposition 2 in Bramoullé and Garance (2018)
on targeting centralities, which characterizes the expected number of times
$i$’s request reaches $j$ if both nodes $i$ and $j$ are excluded from favor
re-transmission.323232The economic issue explored in Bramoullé and Garance
(2018) and the notation they use are slightly different from ours. Here we
have adapted their results using our notation. In fact, Proposition 3
generalizes Bramoullé and Garance (2018)’s targeting centrality in two
dimensions. Specifically, equation (20) captures the expected times that $i$’s
request reaches $j$ when a group of individuals, rather than only $i$ and $j$
in Bramoullé and Garance (2018), are excluded from re-transmission. Meanwhile,
equation (18) and (19) capture the cases that either request originator $i$ or
receiver $j$ or both are allowed to retransmit the request when a group of
individuals cannot. Finally, it is worth noting that, equation (21)
demonstrates a symmetric decomposition of the walks between two disjoint set
of nodes in the network. This symmetric property is a group generalization of
Bramoullé and Garance (2018)’s observation (cf. footnote 7 in Bramoullé and
Garance (2018)).333333Bramoullé and Garance (2018) state that (in our
notation):  “for any $i$, $j$,
$m_{ii}\left(\mathbf{G}\right)w_{jj}\left(\mathbf{G},\left\\{i\right\\}\right)=$
$m_{jj}\left(\mathbf{G}\right)w_{ii}\left(\mathbf{G},\left\\{j\right\\}\right)$.
To our knowledge, this provides a noval result in matrix analysis.” The
symmetric property is consistent with (21) after canceling out the common term
$m_{ij}\left(\mathbf{G}\right)$ on both sides.

##  4 The key bridge connecting isolated networks

###  4.1 The bridge index and the key bridge

Consider two isolated networks, $\left(N_{1},\mathbf{N}^{1}\right)$ and
$\left(N_{2},\mathbf{N}^{2}\right)$, where $N_{i}$ denotes the set of players
and $\mathbf{N}^{i}$ denotes the corresponding adjacency matrix for
$i\in\left\\{1,2\right\\}$. Define $N=N^{1}\cup N^{2}$ and the adjacency
matrix $\mathbf{G}=\begin{bmatrix}\mathbf{N}^{1}&\mathbf{0}\\\
\mathbf{0}&\mathbf{N}^{2}\end{bmatrix}$. Note that
$m_{ij}(\mathbf{G})=m_{ji}(\mathbf{G})=0$ for $i\in N_{1},j\in N_{2}$. To
simplify the notation, we set $\theta_{k}=1$ for any $k\in N$ throughout this
section. The planner’s problem is to maximize aggregate equilibrium effort by
adding a new link between some nodes $i\in N_{1}$ and $j\in N_{2}$.
Mathematically, the planner solves

$\max_{(i,j)\in N_{1}\times N_{2}}b\left(\mathbf{G+E}_{ij}\right)\text{.}$
(24)

The pair of nodes $(i^{\ast},j^{\ast})$ that solves the above problem is
called the key bridge pair. We call node $i^{\ast}$ (node $j^{\ast}$) as the
key bridge player in network $\mathbf{N}^{1}(\mathbf{N}^{2})$.

The key bridge problem naturally arise in many economic settings. For example,
in the integration of new immigrants into a new country, the communication
between culture leaders serves as a bond connecting two initially isolated
communities (see Verdier and Zenou (2015, 2018)). For another example, a firm
can be viewed as a network among workers with synergies as a worker’s
productivity is influenced by his peers’ through knowledge sharing and skill
complementarity. Building up interfirm social connections creates further
economic values. For instance, Cai and Szeidl (2018) document the effects of
interfirm meetings among young Chinese firms on their business
performance.343434In a large-scale experimental study of network formation,
Choi et al. (2019) highlight the role of connectors and influencers.

######  Definition 4.

For any pair $(i,j)\in N_{1}\times N_{2}$, define the bridge index
$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$ as

$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)\equiv\frac{\delta
m_{jj}\left(\mathbf{N}^{2}\right)b_{i}^{2}\left(\mathbf{N}^{1}\right)+\delta
m_{ii}\left(\mathbf{N}^{1}\right)b_{j}^{2}\left(\mathbf{N}^{2}\right)+2b_{j}\left(\mathbf{N}^{2}\right)b_{i}\left(\mathbf{N}^{1}\right)}{1-\delta^{2}m_{jj}\left(\mathbf{N}^{2}\right)m_{ii}\left(\mathbf{N}^{1}\right)}.$
(25)

######  Proposition 4.

The key bridge pair $(i^{*},j^{*})$ must maximize the bridge index, i.e.,

$(i^{*},j^{*})\in\arg\max_{(i,j)\in N_{1}\times
N_{2}}L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)\text{.}$

This Proposition fully solve the key bridge problem using the bridge index. It
follows that, when $\mathbf{G}$ is the union of two isolated networks

$b\left(\mathbf{G+E}_{ij}\right)-b\left(\mathbf{G}\right)=\delta
L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right),~{}~{}~{}\forall i\in
N_{1},j\in N_{2}.$ (26)

Thus, this bridge index $L_{ij}$ summarizes all the walks passing bridge
$(i,j)$ at least once. Depending on the starting node, the end node, and how
many times such a new walk intersects with the bridge, we sort these
additional walks into different categories, and can provide a view from walk
counting for each category as shown in the bridge index (see the Appendix B
for details).

To obtain further insights on who exactly is the key bridge player using the
primitive information, we present the following Corollary. Let
$e_{i}=\sum_{j\in N}g_{ij}$ denote degree of player $i$.

######  Corollary 2.

The following properties about the bridge index
$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$ hold:

  1. (i)

For two nodes $i$ and $i^{\prime}$ in $N_{1}$ with
$b_{i}\left(\mathbf{N}^{1}\right)\geq
b_{i^{\prime}}\left(\mathbf{N}^{1}\right)$ and
$m_{ii}\left(\mathbf{N}^{1}\right)\geq
m_{i^{\prime}i^{\prime}}\left(\mathbf{N}^{1}\right)$, we have
$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)\geq
L_{i^{\prime}j}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$ for any $j\in
N_{2}$.

  2. (ii)

For nodes $i$, $i^{\prime}$ in $N_{1}$ and $j$, $j^{\prime}$ in $N_{2}$ such
that
$b_{i}\left(\mathbf{N}^{1}\right)=b_{i^{\prime}}\left(\mathbf{N}^{1}\right)$,
$m_{jj}\left(\mathbf{N}^{2}\right)=m_{j^{\prime}j^{\prime}}\left(\mathbf{N}^{2}\right)$,
$m_{ii}\left(\mathbf{N}^{1}\right)\geq
m_{i^{\prime}i^{\prime}}\left(\mathbf{N}^{1}\right)$ and
$b_{j}\left(\mathbf{N}^{2}\right)\geq
b_{j^{\prime}}\left(\mathbf{N}^{2}\right)$, we have

$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)-L_{ij^{\prime}}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)\geq
L_{i^{\prime}j}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)-L_{i^{\prime}j^{\prime}}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)\text{.}$

  3. (iii)

For two nodes $i$, $i^{\prime}$ in $N_{1}$ with $e_{i}>e_{i^{\prime}}$, there
exists $\bar{\delta}>0$ such that for any $0<\delta<\bar{\delta}$,
$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)>L_{i^{\prime}j}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$
for any $j\in N_{2}$.

Corollary 2 (i) implies that to find key bridge player $i^{\ast}$ in first
network $N_{1}$, it suffices to focus on the set of nodes in $N_{1}$ that lie
on the Pareto frontier of Katz-Bonacich centrality $b_{i}(\mathbf{N}^{1})$ and
self-loops $m_{ii}(\mathbf{N}^{1})$. Therefore, if the most active player (the
one with highest $b_{i}(\mathbf{N}^{1})$) also happens to the one with highest
$m_{ii}(\mathbf{N}^{1})$, it must be the key bridge player. The reason is that
$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$ increases with
$b_{i}(\mathbf{N}^{1})$ and $m_{ii}(\mathbf{N}^{1})$, fixing $j$. Meanwhile,
the intercentrality index,
$\frac{b_{i}^{2}(\mathbf{N}^{1})}{m_{ii}(\mathbf{N}^{1})}$, increases in
$b_{i}(\mathbf{N}^{1})$ but decreases in $m_{ii}(\mathbf{N}^{1})$. Therefore,
the key player may differ from the key bridge player.

Moreover, when the player with largest $b_{i}(\mathbf{N}^{1})$ differs from
the one with largest $m_{ii}(\mathbf{N}^{1})$ in $N_{1}$, the selection of the
key bridge player in $N_{1}$ crucially depends who is chosen as the bridge
player $j$ in the other network $\mathbf{N}^{2}$. In other words, the
selection of the key bridge pair is not independent. As suggested by Corollary
2 (ii), the role of node $i$’s self-loops in determining the bridge index
$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$ becomes more significant if
a node $j$ with larger Katz-Bonacich centrality is selected. Correspondently,
$i$’s Katz-Bonacich centrality plays a more important role than self-loops
when a node $j$ with larger self-loops is selected. Consider a scenario in
which these two networks are highly imbalanced, in the sense that the largest
Bonacich centrality in network $\mathbf{N}^{2}$ is much larger than the one in
network ${\mathbf{N}^{1}}$.353535This could be the case when network
$\mathbf{N}^{2}$ involves much more network members, who have denser
connections among each other. Then the key bridge pair may consist of the
central node in $\mathbf{N}^{2}$ and the node with largest self-loop in
network $\mathbf{N}^{1}$ (even if such node may not be the most central one).
It is because the self-loop of the player in $\mathbf{N}^{1}$ contributes more
than Katz-Bonacich centrality on the bridge index
$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$ when Katz-Bonacich
centrality of the bridge player in $\mathbf{N}^{2}$ is significantly large.
Furthermore, when $\delta$ is below a threshold, the degree centrality plays
the dominant role in the bridge index by item (iii). We illustrate these
observations using the following example.

######  Example 3.

Consider two isolated networks depicted in Figure 3.

Figure 3: Connecting $\mathbf{N}^{1}$ and $\mathbf{N}^{2}$ by adding a bridge

Table 3: Measures $\delta=0.25$ Players | $m_{ii}$ | $b_{i}$
---|---|---
$a_{1}$ | 1.5686 | 4.7059
$a_{2}$ | 1.5980 | 4.6765
$a_{3}$ | 1.2686 | 3.2059
$a_{4}$ | 1.4255 | 4.1471
$a_{5}$ | 1.0980 | 2.1765
$h$ | 1.7778 | 4.8889
$l$ | 1.1111 | 2.2222

Table 4: Bridges with $\delta=0.25$ bridge $i$-$j$ | $L_{ij}\left(\mathbf{G}\right)$
---|---
$h$-$a_{1}$ | 78.9970
$h$-$a_{2}$ | 79.0258

Table LABEL:tab3 gives the Katz-Bonacich centrality $b_{i}$ and self-loops
$m_{ii}$ measures for $\delta=0.25$. In the first network
$\left(N_{1},\mathbf{N}^{1}\right)$, the hub player $h$ is more important than
any of the periphery node both in terms of centrality and self-loops measures.
In the second network $\left(N_{2},\mathbf{N}^{2}\right)$, $a_{1}$ dominates
$a_{2}$ in terms of Katz-Bonacich centrality $b_{i}$, while $a_{2}$ dominates
$a_{1}$ in terms of self-loops $m_{ii}$. All the other nodes in $N_{2}$ are
dominated by $a_{1}$ and $a_{2}$ in both $m_{ii}$ and $b_{i}$. By Corollary 2
(i), the key bridge pair is either $(h,a_{1})$ or $(h,a_{2})$. Table
LABEL:tab4 demonstrates that the bridge index
$L_{ha_{2}}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)>L_{ha_{1}}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)$,
thus $a_{2}$ is the key bridge player in $\left(N_{2},\mathbf{N}^{2}\right)$,
yet $a_{2}$ is neither the most active player (in terms of $b_{i}$) nor the
key player (in terms of the inter-centrality $b_{i}^{2}/m_{ii}$) in
$\left(N_{2},\mathbf{N}^{2}\right)$.

Next, we consider $\delta=0.23$ (see Tables LABEL:tab5 and LABEL:tab6). By the
same logic, it suffices to consider connecting the hub $h$ in the first
network to either $a_{1}$ or $a_{2}$ in the second network. However, for
$\delta=0.23$, the $b_{i}$ plays a more prominent role in the bridge index
than $m_{ii}$, and indeed $a_{1}$ is now the key bridge player. This
observation is consistent with Corollary 2 (iii): the key bridge player is the
player with highest degree when $\delta$ is relatively small (the degree of
$a_{1}$ is larger than that of $a_{2}$).

Keeping $\delta=0.23$. Suppose we increase the periphery nodes in
$\left(N_{1},\mathbf{N}^{1}\right)$ from $7$ to $17$. The Katz-Bonacich
centrality of hub player $b_{h}=48.76$ is significantly larger than that of
players in $N_{2}$. Thus, the self-loops $m_{jj}$ of the bridge player $j$ in
$N_{2}$ is more pronounced, compared with his Katz-Bonacich centrality $b_{j}$
in shaping the relative values of $L_{hj}$. As a result, $(h,a_{2})$ is the
key bridge (indeed,
$L_{ha_{2}}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)=4744>L_{ha_{1}}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)=4680$).

Table 5: Measures with $\delta=0.23$ Players | $m_{ii}$ | $b_{i}$
---|---|---
$a_{1}$ | 1.4213 | 3.8423
$a_{2}$ | 1.4300 | 3.7545
$a_{3}$ | 1.1969 | 2.6348
$a_{4}$ | 1.3063 | 3.3533
$a_{5}$ | 1.0752 | 1.8837
$h$ | 1.5881 | 4.1448
$l$ | 1.0840 | 1.9533

Table 6: Bridges with $\delta=0.23$ bridge $i$-$j$ | $L_{ij}\left(\mathbf{G}\right)$
---|---
$h$-$a_{1}$ | 48.6711
$h$-$a_{2}$ | 47.6461

###  4.2 The value of an existing link and the value of a potential link

Instead of considering two isolated networks, in this subsection we consider a
general network and explore the effects of link creation and deletion.

######  Lemma 4.

For any network $\mathbf{G}$,

  * (i)

Suppose $g_{ij}=0$, then

$b(\mathbf{G}+\mathbf{E}_{ij})-b(\mathbf{G})=\delta{L}_{ij}\left(\mathbf{G}\right)$
(27)

where

${L}_{ij}\left(\mathbf{G}\right)=\frac{\delta
m_{ii}\left(\mathbf{G}\right)b_{j}^{2}\left(\mathbf{G}\right)+\delta
m_{jj}\left(\mathbf{G}\right)b_{i}^{2}\left(\mathbf{G}\right)+2\left(1-\delta
m_{ij}\left(\mathbf{G}\right)\right)b_{i}\left(\mathbf{G}\right)b_{j}\left(\mathbf{G}\right)}{\left(1-\delta
m_{ij}\left(\mathbf{G}\right)\right)^{2}-\delta^{2}m_{ii}\left(\mathbf{G}\right)m_{jj}\left(\mathbf{G}\right)}\text{.}$

  * (ii)

Suppose $g_{ij}=1$, then

$b(\mathbf{G}-\mathbf{E}_{ij})-b(\mathbf{G})=-\delta
l_{ij}\left(\mathbf{G}\right)$ (28)

where

$l_{ij}\left(\mathbf{G}\right)=\frac{2\left(1+\delta
m_{ij}\left(\mathbf{G}\right)\right)b_{i}\left(\mathbf{G}\right)b_{j}\left(\mathbf{G}\right)-\left(\delta
m_{ii}\left(\mathbf{G}\right)b_{j}^{2}\left(\mathbf{G}\right)+\delta
m_{jj}\left(\mathbf{G}\right)b_{i}^{2}\left(\mathbf{G}\right)\right)}{\left(1+\delta
m_{ij}\left(\mathbf{G}\right)\right)^{2}-\delta^{2}m_{ii}\left(\mathbf{G}\right)m_{jj}\left(\mathbf{G}\right)}\text{,}$

The index $L_{ij}$ measures the value of a potential new link $(i,j)$ in the
network $\mathbf{G}$, while $l_{ij}$ measures the value of an existing link
$(i,j)$ in $\mathbf{G}$. Therefore, the index $L_{ij}$ is useful in
determining the optimal location for a new link (for instance, the key bridge
problem). Meanwhile, $l_{ij}$ measures the contribution of an existing link
$\left(i,j\right)$ to the total Katz-Bonacich centralities. For instance,
Ballester et al. (2010) derives the same measure in a different method (see
their Lemma 2), and use it to study the most important existing link (the key
link). Both indices $L_{ij}$ and $l_{ij}$ share some similar properties as the
bridge index in Corollary 2, hence we omit the details.

Both results in Lemma 4 follow directly from Proposition 1: we set
$\mathbf{C}=\mathbf{E}_{ij}$ in case (i) and set $\mathbf{C}=-\mathbf{E}_{ij}$
in case (ii). Note that in both cases, $m_{ij}$ and $b_{i}$ in the expressions
of $L_{ij}$ and $l_{ij}$ are evaluated at the existing network $\mathbf{G}$.
Since removing the newly added link $(i,j)$ in $\mathbf{G}+\mathbf{E}_{ij}$
results in the original network $\mathbf{G}$, Lemma 4 reveals the following
relationship between two indices:

$l_{ij}(\mathbf{G}+\mathbf{E}_{ij})=L_{ij}(\mathbf{G}).$ (29)

This identity enables us to express $L_{ij}(\mathbf{G})$ using the centrality
measures of the new network $\mathbf{G}+\mathbf{E}_{ij}$. Lemma 4 (i)
generalizes the bridge index in equation (25). Indeed, when $\mathbf{G}$ is
the union of two isolated networks $\mathbf{N}^{1}$ and $\mathbf{N}^{2}$, we
have $m_{ij}=0$ for $i\in\mathbf{N}^{1},j\in\mathbf{N}^{2}$, and the index
$L_{ij}$ in equation (27) reduces to $L_{ij}(\mathbf{N}^{1},\mathbf{N}^{2})$
in equation (25).

Unlike the bridge index which does not depend on $m_{ij}$, the general link
index $L_{ij}$ increases with $m_{ij}$ (note that in a general network,
$m_{ij}$ can be positive even when $i$ and $j$ are not directly connected). So
the designer may prefer connecting nodes who has already been well connected
in the original network to adding bridges connecting separated groups. The
next Example illustrates when it is desirable to add intra-group link(s) vs.
inter-group link(s).

######  Example 4.

Consider a original network $\mathbf{G}$ composed of two separated cycles,
each with size four. We search for the optimal way to add one or two links,
where the links can be formed between or within two circles.

  * (a)

Consider adding one link. By symmetry, it suffices to compare
$\hat{\mathbf{G}}_{1}$ and $\hat{\mathbf{G}}_{2}$ in Figure 4. Given
$m_{2,3}>m_{2,5}=0$ and all other measures are equal, adding the intra-group
link $(2,3)$ strictly dominates adding the inter-group link $(2,5)$, i.e.,
$\hat{\mathbf{G}}_{2}$ dominates $\hat{\mathbf{G}}_{1}$ (see Table 7).

Figure 4: Adding a single link between two separated networks

  * (b)

What if we can add one additional link? It is easy to see that the optimal
network is among the following three networks: $\bar{\mathbf{G}}_{1}$,
$\bar{\mathbf{G}}_{2}$, and $\bar{\mathbf{G}}_{3}$ (see Figure 5).363636All
other ways of forming two links are dominated. Denote $((i,j),(k,l))$ as an
intervention of adding two links. For instance, $((2,5),(4,7))$ is strictly
dominated by $((2,5),(2,7))$ since $b_{2}>b_{4}$, $m_{2,2}>m_{4,4}$ and
$m_{2,7}>m_{4,7}$ once a bridge $(2,5)$ is added. $((2,5),(2,7))$ strictly
dominates $((2,5),(2,8))$ since $m_{2,7}>m_{2,8}$ once a bridge $(2,5)$ is
added. $((2,3),(6,7))$ is strictly dominated by $((1,4),(2,3))$ since
$b_{1}>b_{6}$, $m_{1,1}>m_{6,6}$ and $m_{1,4}>m_{6,7}$ once $(2,3)$ is added.
$((2,5),(6,7))$ is strictly dominated by $((5,8),(6,7))$ since $b_{8}>b_{2}$,
$m_{8,8}>m_{2,2}$ and $m_{5,8}>m_{2,5}$ once $(6,7)$ is added. Among these
three, see Table 7 shows that $\bar{\mathbf{G}}_{3}$ is the optimal. In other
words, connecting two inter-group bridges $((2,5),(2,7))$ strictly dominates
building up two intra-group links $((1,4),(2,3))$, even though building up one
intra-group link is myopically optimal as in part (a).373737 Starting with
$\hat{\mathbf{G}}_{2}$, the optimal network with one extra link by part (a).
Conditioning on adding $(2,3)$ as the first link, $(1,4)$ strictly dominates
$(2,5)$ as the second link as $\bar{\mathbf{G}}_{2}$ has higher aggregate
Katz-Bonacich centralities than $\bar{\mathbf{G}}_{1}$ in terms of (see Table
7). However, neither $\bar{\mathbf{G}}_{1}$ nor $\bar{\mathbf{G}}_{2}$ is
optimal. Nevertheless, starting with the dominated network,
$\hat{\mathbf{G}}_{1}$ in part (a), we can reach the optimal network
$\bar{\mathbf{G}}_{3}$ by adding the link $(2,7)$.

Figure 5: Adding two links between two separated networks Table 7: Aggregate Katz-Bonacich centralities ($\delta=0.21$) Add one link | $b\left(\right)$ | Add two links | $b\left(\right)$
---|---|---|---
$\hat{\mathbf{G}}_{1}$ | 15.4198 | $\bar{\mathbf{G}}_{1}$ | 17.7010
$\hat{\mathbf{G}}_{2}$ | 15.4689* | $\bar{\mathbf{G}}_{2}$ | 17.7074
|  | $\bar{\mathbf{G}}_{3}$ | 17.7547*

##  5 Extensions and concluding remarks

###  5.1 Alternative network models

Our analysis so far focuses on the impact of the structural interventions on
the Katz-Bonacich centralities in the baseline model of Ballester et al.
(2006). Since Katz-Bonacich centrality plays a critical role for many network
models, so our results (and subsequent applications) naturally extend to these
alternative models. For instance, Currarini et al. (2017) extend the single-
activity network model of Ballester et al. (2006) with direct complements to
incorporate indirect substitutes among players with distance two, and
characterize the equilibrium using both $\mathbf{G}$ and $\mathbf{G}^{2}$. In
the Appendix, we show that the equilibrium in Currarini et al. (2017) can be
written as a linear combination of two Katz-Bonacich centralities. Ballester
et al. (2006) extend the baseline model in equation (1) to allow global
substitution and show that the aggregate action is a monotone transformation
of Katz-Bonacich centralities. In addition, Chen et al. (2018b) consider a
network game with multiple activities, and show that the equilibrium can be
represented as the weights sum of two Katz-Bonacich centralities (with
different synergy parameters and characteristics). See Appendix C for details.

###  5.2 Hybrid interventions

We can study the effect of general interventions combining both structural and
characteristic interventions in networks. A general hybrid intervention is
given by $\left(\mathbf{C},\Delta\boldsymbol{\theta}\right)$, where
$\mathbf{C}$ is the structural intervention and $\Delta\boldsymbol{\theta}$ is
the characteristic intervention. The hybrid intervention
$\left(\mathbf{C},\Delta\boldsymbol{\theta}\right)$ on network game
$\Gamma\left(\mathbf{G},\boldsymbol{\theta}\right)$ can be viewd as a
structural intervention $\mathbf{C}$ on network game
$\Gamma\left(\mathbf{G},\boldsymbol{\theta+}\Delta\boldsymbol{\theta}\right)$.
By Proposition 1, this hybrid intervention
$\left(\mathbf{C},\Delta\boldsymbol{\theta}\right)$ is outcome equivalent to a
characteristic intervention

$\widetilde{\Delta\boldsymbol{\theta}^{\ast}}=\Delta\boldsymbol{\theta}+\begin{bmatrix}\mathbf{0}\\\
\delta\mathbf{C}_{SS}\left(\mathbf{I}-\delta\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{C}_{SS}\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}+\Delta\boldsymbol{\theta}\right)\end{bmatrix}\text{,}$

of $\Gamma\left(\mathbf{G},\boldsymbol{\theta}\right)$. Thus, the new
equilibrium after this hybrid intervention is given by

$\mathbf{\hat{x}}^{\ast}=\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta}\right)+\mathbf{M}\left(\mathbf{G}\right)\widetilde{\Delta\boldsymbol{\theta}^{\ast}}.$

This characterization of equilibrium effects of hybrid interventions enables
us to study optimal combinations of intervention policies in networks.

###  5.3 Concluding remarks

In this paper, we present a theory of interventions in network. By showing an
equivalence between a structural intervention and an _endogenously determined_
characteristic intervention, we analyze how these two types of interventions
affect the equilibrium actions and offer new insights regarding the optimal
interventions in a range of applications.

We discuss several venues for future work. First, this paper mainly focuses on
the benefit of structural interventions without explicitly modelling the cost
of cutting/building links and nodes. It is interesting to study the optimal
intervention policy with some budget on the cost of interventions (see
Galeotti et al. (2020)). Second, we treat two instruments, i.e,
characteristics and social links, independently in our analysis. In some
contexts, intervention in one space (say the characteristics) may induce
endogenous responses in the other space (the network links). For instance,
Banerjee et al. (2018) show that new links are formed and existing links are
removed after exposure to formal credit markets. Extending hybrid
interventions to accomodate interdependence between two instruments is an
intriguing subject. Finally, It is natural to extend our approach to network
games with non-linear responses (see, for instance, Allouch (2017) and Elliott
and Golub (2018)). These and other generalizations will enrich our
understanding of optimal interventions in economic settings involving
networks.

Appendix

##  Appendix A Proofs

Proof of Lemma 1: In the game $\Gamma\left(\mathbf{G,\theta}\right)$, the
equilibrium action profile is
$\mathbf{x}^{\ast}=\mathbf{M}\left(\mathbf{G}\right)\boldsymbol{\theta}$, and
the aggregate equilibrium action is
${x}^{\ast}=\mathbf{1}^{\prime}\mathbf{M}\left(\mathbf{G}\right)\boldsymbol{\theta}=\mathbf{b}^{\prime}(\mathbf{G})\boldsymbol{\theta}$.
Since the network $\mathbf{G}$ is fixed for a characteristic intervention, the
results directly follow. $\Box$

Proofs of Lemma 2: The equilibrium actions of
$\Gamma\left(\mathbf{G},\boldsymbol{\theta}\right)$ satisfies
$\mathbf{x}^{\ast}=\boldsymbol{\theta}+\delta\mathbf{Gx}^{\ast}$. Under the
structural intervention $\mathbf{C}$, the new equilibrium action profile
$\mathbf{\hat{x}}^{\ast}$ satisfies

$\mathbf{\hat{x}}^{\ast}=\boldsymbol{\theta}+\delta\left(\mathbf{G}+\mathbf{C}\right)\mathbf{\hat{x}}^{\ast}=\left(\boldsymbol{\theta}+\underbrace{\delta\mathbf{C\hat{x}}^{\ast}}_{=\mathbf{\Delta}\boldsymbol{\theta}^{\ast}}\right)+\delta\mathbf{G\hat{x}}^{\ast}\text{.}$

That is, the structural intervention $\mathbf{C}$ is outcome equivalent to a
change of players’ intrinsic marginal utilities from $\boldsymbol{\theta}$ to
$\boldsymbol{\theta}+\mathbf{\Delta}\boldsymbol{\theta}^{\ast}=\boldsymbol{\theta}+\delta\mathbf{C\hat{x}}^{\ast}$.
Given $\mathbf{C}=\begin{bmatrix}\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&\mathbf{C}_{SS}\end{bmatrix}$, we obtain

$\mathbf{\Delta}\boldsymbol{\theta}^{\ast}=\delta\mathbf{C\hat{x}}^{\ast}=\delta\begin{bmatrix}\mathbf{0}&\mathbf{0}\\\
\mathbf{0}&\mathbf{C}_{SS}\end{bmatrix}\begin{bmatrix}\mathbf{\hat{x}}_{S^{C}}^{\ast}\\\
\mathbf{\hat{x}}_{S}^{\ast}\end{bmatrix}=\begin{bmatrix}\mathbf{0}\\\
\delta\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{\ast}\end{bmatrix}\text{.}$

That is, the structural intervention $\mathbf{C}$ is outcome equivalence to
changing the characteristics of players in $S$ by
$\mathbf{\Delta}\boldsymbol{\theta}_{S}^{\ast}=\delta\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{\ast}$.
Moreover, from equation (5), $\mathbf{\hat{x}}_{S}^{\ast}$ must satisfy the
following:

$\mathbf{\hat{x}}_{S}^{\ast}=\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)+\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{\Delta}\boldsymbol{\theta}_{S}^{\ast}=\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)+\delta\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{\ast}\text{.}$

Solving it yields
$\mathbf{\hat{x}}_{S}^{\ast}=\left(\mathbf{I}-\delta\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{C}_{SS}\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right).$
Consequently, we obtain

$\mathbf{\Delta}\boldsymbol{\theta}_{S}^{\ast}=\delta\mathbf{C}_{SS}\mathbf{\hat{x}}_{S}^{\ast}=\delta\mathbf{C}_{SS}\left(\mathbf{I}-\delta\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{C}_{SS}\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right).$

$\square$

Proofs of Proposition 1: It directly follows from Lemmas 1 and 2. $\square$

Proof of Corollary 1: Define
$\eta(t)=\mathbf{1}^{\prime}(\mathbf{I}-\delta(\mathbf{G}+t\mathbf{C}))^{-1}\mathbf{1},t\in[0,1]$.
Since we have assumed that $\mathbf{I}-\delta\mathbf{G}$ and
$\mathbf{I}-\delta(\mathbf{G}+\mathbf{C})$ are both symmetric positive
definite, $(\mathbf{I}-\delta(\mathbf{G}+t\mathbf{C}))$ is positive definite
for any $t\in[0,1]$, hence $\eta$ is well-defined. Given
$\boldsymbol{\theta}=\mathbf{1}$,

$\eta(0)=\mathbf{1}^{\prime}(\mathbf{I}-\delta(\mathbf{G})^{-1}\mathbf{1}=b(\mathbf{G},\mathbf{1})$

is the equilibrium aggregate action before the intervention, and

$\eta(1)=\mathbf{1}^{\prime}(\mathbf{I}-\delta(\mathbf{G}+\mathbf{C})^{-1}\mathbf{1}=b(\mathbf{G+C},\mathbf{1})$

is the equilibrium aggregate action after the intervention. Direct computation
shows that383838We use the fact that $d(A^{-1})=-A^{-1}(dA)A^{-1}$.

$\begin{split}\eta^{\prime}(0)=\eta^{\prime}(t)|_{t=0}&=\mathbf{1}^{\prime}(\mathbf{I}-\delta(\mathbf{G}+t\mathbf{C}))^{-1}\delta\mathbf{C}(\mathbf{I}-\delta(\mathbf{G}+t\mathbf{C}))^{-1}\mathbf{1}|_{t=0}\\\
&=\mathbf{1}^{\prime}(\mathbf{I}-\delta\mathbf{G})^{-1}\delta\mathbf{C}(\mathbf{I}-\delta\mathbf{G})^{-1}\mathbf{1}=\delta\mathbf{b}^{\prime}(\mathbf{G})\mathbf{C}\mathbf{b}(\mathbf{G}).\end{split}$

Critically, $\eta(\cdot)$ is convex in $t$ by Lemma 5 below, therefore,
$\eta(1)-\eta(0)\geq\eta^{\prime}(0)(1-0).$ In other words,
$b(\mathbf{G+C},\mathbf{1})-b(\mathbf{G},\mathbf{1})\geq\delta\mathbf{b}^{\prime}(\mathbf{G})\mathbf{C}\mathbf{b}(\mathbf{G}),$
which implies Corollary 1.393939As seen from the proof, Corollary 1 holds for
weighted undirected networks as well. $\Box$

######  Lemma 5.

Let $\mathcal{O}$ denote the set of $n$ by $n$ symmetric positive definite
matrices. Then the function
$V(\mathbf{A}):=\mathbf{1}^{\prime}\mathbf{A}^{-1}\mathbf{1}$ is convex in
$\mathbf{A}\in\mathcal{O}$.

Proof of Lemma 5: Define
$H(\mathbf{A},\mathbf{x})=2\mathbf{1}^{\prime}x-\mathbf{x}^{\prime}\mathbf{A}\mathbf{x}$,
where $\mathbf{A}\in\mathcal{O},\mathbf{x}\in\mathbf{R}^{n}$. Fixing a
positive definite matrix $\mathbf{A}\in\mathcal{O}$, $H(\mathbf{A},\cdot)$ is
strictly concave in $x$ with the maximum value

$\max_{\mathbf{x}\in\mathbf{R}^{n}}H(\mathbf{A},\mathbf{x})=\mathbf{1}^{\prime}\mathbf{A}^{-1}\mathbf{1}=V(\mathbf{A}),$

obtained at $\mathbf{x}^{\ast}=\mathbf{A}^{-1}\mathbf{1}$. Moreover,
$H(\mathbf{A},\mathbf{x})$ is linear in $\mathbf{A}$ for fixed $\mathbf{x}$,
so $V(\mathbf{A})=\max_{\mathbf{x}\in\mathbf{R}^{n}}H(\mathbf{A},\mathbf{x})$
is convex in $\mathbf{A}\in\mathcal{O}$, as the maximum of a family of linear
functions is convex (see Boyd and Vandenberghe (2004)). $\Box$

Proof of Lemma 3: As demonstrated in the main text,
$d_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)$ exactly equals the effect
of the characteristic intervention
$\Delta\boldsymbol{\theta}_{S}=\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)$
on the aggregate action. Therefore, by Lemma 1,
$d_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)=\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\Delta\boldsymbol{\theta}_{S}=\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right)$.
$\Box$

Proof of Proposition 2: Part (i) is obvious. For part (ii), we first define
$\mathbf{v}:=\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{1}\right)$.
We first show that $\mathbf{v}$ is a positive vector, i.e,
$\mathbf{v}\succeq\mathbf{0}$:

$\displaystyle\mathbf{v}$ $\displaystyle=$
$\displaystyle\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{1}\right)=\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\left(\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)\mathbf{1}_{|S^{C}|}+\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{1}_{|S|}\right)$
$\displaystyle=$
$\displaystyle\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)\mathbf{1}_{|S^{C}|}+\mathbf{1}_{|S|}=\underbrace{\delta\mathbf{G}_{SS^{C}}\left(\mathbf{I}-\delta\mathbf{G}_{S^{C}S^{C}}\right)^{-1}\mathbf{1}_{|S^{C}|}}_{\succeq\mathbf{0}}+\mathbf{1}_{|S|}\succeq\mathbf{0},$

where in the last equality we use the identity
$\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{M}_{SS^{C}}=\delta\mathbf{G}_{SS^{C}}\left(\mathbf{I}-\delta\mathbf{G}_{S^{C}S^{C}}\right)^{-1}$.
Moreover, given
$\mathbf{b}_{S}\left(\mathbf{G}\right)\preceq\mathbf{b}_{S^{\prime}}\left(\mathbf{G}\right)$,
and
$\mathbf{M}_{SS}\left(\mathbf{G}\right)\succeq\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)$,
and $\mathbf{v}\succeq\mathbf{0}$, we have

$d_{S}\left(\mathbf{G},\mathbf{1}\right)=2\mathbf{b}_{S}\left(\mathbf{G}\right)\mathbf{v}-\mathbf{v}^{\prime}\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{v}\leq
2\mathbf{b}_{S^{\prime}}^{\prime}\left(\mathbf{G}\right)\mathbf{v}-\mathbf{v}^{\prime}\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)\mathbf{v},$
(30)

Solving the following concave programming yields404040As a principle submatrix
of positive definite matrix $\left(\mathbf{I}-\delta\mathbf{G}\right)^{-1}$,
$\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)$ is also positive
definite.

$\underset{\mathbf{x\in}\mathbb{R}^{|S|}}{\max}\left\\{2\mathbf{b}_{S^{\prime}}^{\prime}\left(\mathbf{G}\right)\mathbf{x}-\mathbf{x}^{\prime}\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)\mathbf{x}\right\\}=\mathbf{b}_{S^{\prime}}^{\prime}\left(\mathbf{G}\right)\left(\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)\right)^{-1}\mathbf{b}_{S^{\prime}}\left(\mathbf{G}\right)=d_{S^{\prime}}\left(\mathbf{G},\mathbf{1}\right).$
(31)

By optimality,

$\underset{\mathbf{x\in}\mathbb{R}^{|S|}}{\max}\left\\{2\mathbf{b}_{S^{\prime}}^{\prime}\left(\mathbf{G}\right)\mathbf{x}-\mathbf{x}^{\prime}\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)\mathbf{x}\right\\}\geq
2\mathbf{b}_{S^{\prime}}^{\prime}\left(\mathbf{G}\right)\mathbf{v}-\mathbf{v}^{\prime}\mathbf{M}_{S^{\prime}S^{\prime}}\left(\mathbf{G}\right)\mathbf{v}.$
(32)

Combing equation (30), (31), and (32) yields
$d_{S}\left(\mathbf{G},\mathbf{1}\right)\leq
d_{S^{\prime}}\left(\mathbf{G},\mathbf{1}\right)$. $\square$

Proof of Proposition 3:

######  Remark 1.

We can have alternative expressions for blocks of the matrix $\mathbf{W}$ as
follows

$\displaystyle\mathbf{W}_{S^{C}S^{C}}\left(\mathbf{G},S\right)$
$\displaystyle=$
$\displaystyle\left(\mathbf{I}-\delta\mathbf{G}_{S^{C}S^{C}}\right)^{-1}\text{;}$
$\displaystyle\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)$ $\displaystyle=$
$\displaystyle\left(\mathbf{I}-\delta\mathbf{G}_{S^{C}S^{C}}\right)^{-1}\delta\mathbf{G}_{S^{C}S}\text{;}$
$\displaystyle\mathbf{W}_{SS}\left(\mathbf{G},S\right)$ $\displaystyle=$
$\displaystyle\delta\mathbf{G}_{SS^{C}}\left(\mathbf{I}-\delta\mathbf{G}_{S^{C}S^{C}}\right)^{-1}\delta\mathbf{G}_{S^{C}S}+\delta\mathbf{G}_{SS}+\mathbf{I}\text{.}$

These expressions directly follow from the definition of $\mathbf{W}$. Unlike
Proposition 3, these expressions use the centralities in the remaining network
$\mathbf{G}_{S^{C}S^{C}}$.

The Leontief inverse matrix can be written in the block form

$\left(\mathbf{I}-\delta\mathbf{G}\right)^{-1}=\left[\begin{array}[]{cc}\mathbf{I}-\delta\mathbf{G}_{S^{C}S^{C}}&-\delta\mathbf{G}_{S^{C}S}\\\
-\delta\mathbf{G}_{SS^{C}}&\mathbf{I}-\delta\mathbf{G}_{SS}\end{array}\right]^{-1}=\left[\begin{array}[]{cc}\mathbf{M}_{S^{C}S^{C}}\left(\mathbf{G}\right)&\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\\\
\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)&\mathbf{M}_{SS}\left(\mathbf{G}\right)\end{array}\right].$

For easy notation let $\mathbf{I}-\delta\mathbf{G}_{S^{C}S^{C}}=\mathbf{A}$,
$-\delta\mathbf{G}_{S^{C}S}=\mathbf{B}$,
$-\delta\mathbf{G}_{SS^{C}}=\mathbf{C}$ and
$\mathbf{I}-\delta\mathbf{G}_{SS}=\mathbf{D}$. Then by the remark above, we
have $\mathbf{W}_{S^{C}S^{C}}\left(\mathbf{G},S\right)=\mathbf{A}^{-1}$,
$\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)=-\mathbf{A}^{-1}\mathbf{B}$ and
$\mathbf{W}_{SS}\left(\mathbf{G},S\right)=\mathbf{CA}^{-1}\mathbf{B-D+}2\mathbf{I}$.
Using the block matrix inversion,

$\displaystyle\left[\begin{array}[]{cc}\mathbf{A}&\mathbf{B}\\\
\mathbf{C}&\mathbf{D}\end{array}\right]^{-1}$ $\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc}\mathbf{A}^{-1}\mathbf{+A}^{-1}\mathbf{B}\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}\mathbf{CA}^{-1}&-\mathbf{A}^{-1}\mathbf{B}\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}\\\
\mathbf{-\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}CA}^{-1}&\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}\end{array}\right]$
$\displaystyle=$
$\displaystyle\left[\begin{array}[]{cc}\mathbf{M}_{S^{C}S^{C}}\left(\mathbf{G}\right)&\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\\\
\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)&\mathbf{M}_{SS}\left(\mathbf{G}\right)\end{array}\right]\text{.}$

Thus,
$\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}=\mathbf{M}_{SS}\left(\mathbf{G}\right)$,
which implies

$\mathbf{W}_{SS}\left(\mathbf{G},S\right)=\mathbf{CA}^{-1}\mathbf{B-D+}2\mathbf{I}=2\mathbf{I+}\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\text{.}$

We further have
$-\mathbf{A}^{-1}\mathbf{B}\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}=\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)$.
Therefore,

$\mathbf{A}^{-1}\mathbf{B=\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)=-M}_{S^{C}S}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\text{.}$

In addition,
$\mathbf{A}^{-1}\mathbf{B}\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}\mathbf{CA}^{-1}=\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)$.
Substituting in the identity
$\mathbf{A}^{-1}\mathbf{+A}^{-1}\mathbf{B}\left(\mathbf{D}-\mathbf{CA}^{-1}\mathbf{B}\right)^{-1}\mathbf{CA}^{-1}=\mathbf{M}_{S^{C}S^{C}}\left(\mathbf{G}\right)$,
we can get

$\mathbf{A}^{-1}=\mathbf{W}_{S^{C}S^{C}}\left(\mathbf{G},S\right)=\mathbf{M}_{S^{C}S^{C}}\left(\mathbf{G}\right)-\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right)\text{.}$

Let $S=A\cup B$, then the inverse of matrix $\boldsymbol{M}_{SS}$ is given as

$\begin{aligned}
(\boldsymbol{M}_{SS})^{-1}=&\left[\begin{array}[]{cc}\boldsymbol{M}_{AA}&\boldsymbol{M}_{AB}\\\
\boldsymbol{M}_{BA}&\boldsymbol{M}_{BB}\end{array}\right]^{-1}\\\
=&\left[\begin{array}[]{cc}(\boldsymbol{M}_{AA})^{-1}\left(\boldsymbol{I}+\boldsymbol{M}_{AB}\left(\boldsymbol{W}_{BB}(\boldsymbol{G},A)\right)^{-1}\boldsymbol{M}_{BA}(\boldsymbol{M}_{AA})^{-1}\right)&-(\boldsymbol{M}_{AA})^{-1}\boldsymbol{M}_{AB}\left(\boldsymbol{W}_{BB}(\boldsymbol{G},A)\right)^{-1}\\\
-\left(\boldsymbol{W}_{BB}(\boldsymbol{G},A)\right)^{-1}\boldsymbol{M}_{BA}(\boldsymbol{M}_{AA})^{-1}&\left(\boldsymbol{W}_{BB}(\boldsymbol{G},A)\right)^{-1}\end{array}\right]\\\
=&\left[\begin{array}[]{cc}\left(\boldsymbol{W}_{AA}(\boldsymbol{G},B)\right)^{-1}&-\left(\boldsymbol{W}_{AA}(\boldsymbol{G},B)\right)^{-1}\boldsymbol{M}_{AB}(\boldsymbol{M}_{BB})^{-1}\\\
-(\boldsymbol{M}_{BB})^{-1}\boldsymbol{M}_{BA}\left(\boldsymbol{W}_{AA}(\boldsymbol{G},B)\right)^{-1}&(\boldsymbol{M}_{BB})^{-1}\left(\boldsymbol{I}+\boldsymbol{M}_{BA}\left(\boldsymbol{W}_{AA}(\boldsymbol{G},B)\right)^{-1}\boldsymbol{M}_{AB}(\boldsymbol{M}_{BB})^{-1}\right)\end{array}\right]\end{aligned}.$

Using (20), we obtain that

$\displaystyle\boldsymbol{W}_{AB}(\boldsymbol{G},A\cup B)$
$\displaystyle=\left(2\boldsymbol{I}-(\boldsymbol{M}_{SS})^{-1}\right)_{AB}=-\left((\boldsymbol{M}_{SS})^{-1}\right)_{AB}$
$\displaystyle=(\boldsymbol{M}_{AA})^{-1}\boldsymbol{M}_{AB}\left(\boldsymbol{W}_{BB}(\boldsymbol{G},A)\right)^{-1}$
$\displaystyle=\left(\boldsymbol{W}_{AA}(\boldsymbol{G},B)\right)^{-1}\boldsymbol{M}_{AB}(\boldsymbol{M}_{BB})^{-1}.$

Proof of Proposition 4: To Proposition 4, it suffices to show equation (26).
Indeed, when the bridge link between $i\in N_{1}$ and $j\in N_{2}$ is added,
the new equilibrium efforts of $i$ and $j$ satisfy

$\begin{cases}\hat{x}_{i}^{\ast}{{=b_{i}\left(\mathbf{N}^{1}\right)+m_{ii}\left(\mathbf{N}^{1}\right)\underbrace{\delta\hat{x}_{j}^{\ast}}_{=\Delta\theta_{i}^{\ast}}}}\\\
\hat{x}_{j}^{\ast}{{=b_{j}\left(\mathbf{N}^{2}\right)+m_{jj}\left(\mathbf{N}^{2}\right)\underbrace{\delta\hat{x}_{i}^{\ast}}_{=\Delta\theta_{j}^{\ast}}}}\end{cases}\text{.}$
(35)

Here we have translated the structural intervention (adding the link $i-j$)
into the corresponding characteristic intervention:
$\Delta\theta_{i}^{\ast}=\delta\hat{x}_{j}^{\ast}$,
$\Delta\theta_{j}^{\ast}=\delta\hat{x}_{i}^{\ast}$ and
$\Delta\theta_{k}^{\ast}=0$ for all $k\notin\left\\{i,j\right\\}$ (see Lemma
2). Note that $m_{ij}=m_{ji}=0$ as two networks are initially isolated. Simple
algebra yields

$\displaystyle\hat{x}_{i}^{\ast}$ $\displaystyle=$
$\displaystyle\frac{b_{i}\left(\mathbf{N}^{1},\boldsymbol{\theta}^{1}\right)+\delta
m_{ii}\left(\mathbf{N}^{1}\right)b_{j}\left(\mathbf{N}^{2},\boldsymbol{\theta}^{2}\right)}{1-\delta^{2}m_{ii}\left(\mathbf{N}^{1}\right)m_{jj}\left(\mathbf{N}^{2}\right)}\text{,~{}~{}~{}}\hat{x}_{j}^{\ast}=\frac{b_{j}\left(\mathbf{N}^{2},\boldsymbol{\theta}^{2}\right)+\delta
m_{jj}\left(\mathbf{N}^{2}\right)b_{i}\left(\mathbf{N}^{1},\boldsymbol{\theta}^{1}\right)}{1-\delta^{2}m_{ii}\left(\mathbf{N}^{1}\right)m_{jj}\left(\mathbf{N}^{2}\right)}\text{.}$

By Proposition 1, the change in aggregate action equals

$b\left(\mathbf{G+E}_{ij}\right)-b\left(\mathbf{G}\right)=b_{i}\left(\mathbf{N}^{1}\right)\underbrace{\delta\hat{x}_{j}^{\ast}}_{=\Delta\boldsymbol{\theta}_{i}^{\ast}}+b_{j}\left(\mathbf{N}^{2}\right){{\underbrace{\delta\hat{x}_{i}^{\ast}}_{=\Delta\boldsymbol{\theta}_{j}^{\ast}}}}=\delta
L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right).$

Proof of Corollary 2: For item (i), we first note that by Definition 4,
$L_{ij}$ clearly increases with $b_{i}$ and $m_{ii}$ for each given $j$. The
claim just follows.

For item (ii), given $m_{jj}=m_{j^{\prime}j^{\prime}}$ and $b_{j}\geq
b_{j^{\prime}}$, we have

$\displaystyle L_{ij}-L_{ij^{\prime}}$ $\displaystyle=$
$\displaystyle\frac{\delta
m_{ii}\left(b_{j}^{2}-b_{j^{\prime}}^{2}\right)}{1-\delta^{2}m_{ii}m_{jj}}+\frac{2b_{i}\left(b_{j}-b_{j^{\prime}}\right)}{1-\delta^{2}m_{ii}m_{jj}}=\frac{\delta\left(b_{j}^{2}-b_{j^{\prime}}^{2}\right)}{\frac{1}{m_{ii}}-\delta^{2}m_{jj}}+\frac{2b_{i}\left(b_{j}-b_{j^{\prime}}\right)}{1-\delta^{2}m_{ii}m_{jj}}\text{.}$

which clearly increases in $m_{ii}$. The result just follows by noting that
$b_{i}=b_{i^{\prime}}$ and $m_{ii}\geq m_{i^{\prime}i^{\prime}}$.

For item (iii), we apply the Taylor expansions to obtain that

$b_{k}\left(\mathbf{N}^{1}\right)=1+\delta
e_{k}\left(\mathbf{N}^{1}\right)+O\left(\delta^{2}\right),m_{kk}\left(\mathbf{N}^{1}\right)=1+O\left(\delta^{2}\right),~{}~{}k\in
N_{1},$

where $O\left(\delta^{2}\right)$ denotes a real-valued function such that
$\lim\sup_{\delta\rightarrow
0}|\frac{\mathcal{O}\left(\delta^{2}\right)}{\delta^{2}}|<\infty$.
Consequently,

$L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)=2+2\delta\left(1+e_{i}\left(\mathbf{N}^{1}\right)+e_{j}\left(\mathbf{N}^{2}\right)\right)+\mathcal{O}\left(\delta^{2}\right)\text{.}$

Thus, when $\delta$ is sufficiently small, only the degree centrality matters
for the bridge index $L_{ij}$. $\square$

Proof of Lemma 4:  The proof is similar to that of Proposition 4 with the
exception that $m_{ij}$ is not necessarily zero. For item (i), applying
Proposition 1 with $S=\\{i,j\\}$ and $\mathbf{C}_{SS}=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}$ yields

$\Delta
x^{*}=\mathbf{b}_{S}^{\prime}\left(\mathbf{G}\right)\Delta\boldsymbol{\theta}_{S}^{\ast}=\mathbf{b}_{S}^{\prime}\delta\mathbf{C}_{SS}\left(\mathbf{I}-\delta\mathbf{M}_{SS}\left(\mathbf{G}\right)\mathbf{C}_{SS}\right)^{-1}\mathbf{b}_{S}\left(\mathbf{G},\boldsymbol{\theta}\right).$

which reduces to $\delta L_{ij}$ after some algebra.

For item (ii), we apply Proposition 1 with $S=\\{i,j\\}$,
$\mathbf{C}_{SS}=-\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$. The analysis is
similar, hence omitted. $\Box$

##  Appendix B A walk-counting interpretation

###  B.1 Intercentrality of group

In this subsection, we show that any block of
$\mathbf{W}\left(\mathbf{G},S\right)$ can be decomposed by the idea of walk
concatenations.We first introduce some notation.

######  Definition 5.

A walk $\mathcal{P}$ in network $\mathbf{G}$ is a finite sequence of nodes
$(i_{1},i_{2},\cdots,i_{t+1})$ such that
$g_{i_{1}i_{2}}=g_{i_{2}i_{3}}=\cdots=g_{i_{t}i_{t+1}}=1$. The node $i_{1}$ is
the starting node and $i_{t+1}$ is the ending node. The length of the path is
denoted by $\\#(\mathcal{P})=t$. A path of length zero is supposed to be a
one-tuple $(i_{1})$.

Fixing the parameter $\delta$, we define
$\vee_{\delta}(\mathcal{P}):=\delta^{\\#(\mathcal{P})}$ for a walk
$\mathcal{P}$. This definition is linearly extended to a set of walks
$\mathbb{P}$:$\vee_{\delta}(\mathbb{P}):=\sum_{\mathcal{P}\in\mathbb{P}}\vee_{\delta}(\mathcal{P})=\sum_{\mathcal{P}\in\mathbb{P}}\delta^{\\#(\mathcal{P})}.$
(We often drop the subscription $\delta$ in $\vee$ when the context is clear.)

Given two walks $\mathcal{P}=(i_{1},i_{2},\cdots,i_{t+1})$,
$\mathcal{Q}=(j_{1},j_{2},\cdots,j_{s+1})$ with $i_{t+1}=j_{1}$, we construct
the concatenation of $\mathcal{P}$ and $\mathcal{Q}$ as
$\mathcal{P}\odot\mathcal{Q}=(i_{1},i_{2},\cdots,i_{t+1},j_{2},\cdots,j_{s+1})$.
Clearly, we have

$\vee(\mathcal{P}\odot\mathcal{Q})=\vee(\mathcal{P})\cdot\vee(\mathcal{Q})\mbox{~{}and~{}
}\\#(\mathcal{P}\odot\mathcal{Q})=\\#(\mathcal{P})+\\#(\mathcal{P}).$ (36)

These definitions are convenient. For instance, let
$\mathbb{M}_{ij}(\mathbf{G})$ denote the set of walks which starts with $i$
and ends at $j$ in network $\mathbf{G}$. Then, we have
$m_{ij}(\mathbf{G})=\vee(\mathbb{M}_{ij}(\mathbf{G}))$.

######  Definition 6.

Fixing a non-empty proper subset $S$ of $N$ in the network
$\left(N,\mathbf{G}\right)$, for any $i$, $j\in N$, we define
$\mathbb{W}_{ij}\left(\mathbf{G},S\right)$ as the set of walks in
$\mathbb{M}_{ij}(\mathbf{G})$ that do not contain any node in $S$ with the
possible exception for the starting node $i$ and the ending node $j$.

By the definition, it is obvious that
$w_{ij}\left(\mathbf{G},S\right)=\vee(\mathbb{W}_{ij}\left(\mathbf{G},S\right))$.
Now, we are in the position to show the equations in Proposition 3 using walk
counting.

Given $i\in S^{C},j\in S$, any walk $\mathcal{Q}$ in $\mathbb{M}_{ij}$ can be
_uniquely_ decomposed as the concatenations of two walks, $\mathcal{P}^{il}$
and $\mathcal{P}^{lj}$ for some $l\in S$, where $l$ is the _first_ node along
the walk $\mathcal{Q}$ that that node is in $S$. This walk $\mathcal{Q}$
contains at least one node in $S$ as the ending node $j$ is in $S$. By this
definition of $l$, we have $\mathcal{P}^{il}\in\mathbb{W}_{il}(\mathbf{G},S)$.
Clearly, $\mathcal{P}^{lj}\in\mathbb{M}_{lj}$. Furthermore, such a
decomposition is unique. Consequently, we have the following decomposition

$\mathbb{M}_{ij}=\bigcup_{l\in
S}\bigcup_{\mathcal{P}^{il}\in\mathbb{W}_{il}(\mathbf{G},S)}\bigcup_{\mathcal{P}^{lj}\in\mathbb{M}_{lj}}\mathcal{P}^{il}\odot\mathcal{P}^{lj}.$

Taking $\vee$ on both sides and applying the properties of $\vee$ yield the
following linear equations

$m_{ij}=\sum_{l\in S}w_{il}m_{lj}$

for any $i\in S^{C},j\in S$. In matrix form, we obtain that
$\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)=\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)$.
Hence,
$\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)=\mathbf{M}_{S^{C}S}\left(\mathbf{G}\right)\left(\mathbf{M}_{SS}\left(\mathbf{G}\right)\right)^{-1}$.

Now we turn to equation (18). It suffices to show the following

$\mathbf{M}_{S^{C}S^{C}}\left(\mathbf{G}\right)=\mathbf{W}_{S^{C}S^{C}}\left(\mathbf{G},S\right)+\mathbf{W}_{S^{C}S}\left(\mathbf{G},S\right)\mathbf{M}_{SS^{C}}\left(\mathbf{G}\right),$
(37)

which holds as for $i,j\in S^{C}$, the walks $\mathbb{M}_{ij}$ can be
decomposed into disjoint unions:

$\mathbb{M}_{ij}=\mathbb{W}_{ij}\bigcup\left(\bigcup_{l\in
S}\bigcup_{\mathbb{P}^{il}\in\mathbb{W}_{il}}\bigcup_{\mathbb{P}^{lj}\in\mathbb{M}_{lj}}\mathbb{P}^{il}\odot\mathbb{P}^{lj}\right).$

The intuition follows from a simple counting exercise. For a walk
$\mathcal{Q}$ in $\mathbb{M}_{ij}$, either it does not contain any node in
$S$, or it contain at least one node in $S$. The set of walks in the former
case is precisely $\mathbb{W}_{ij}$, while the set of walks in the latter case
is precisely $\left(\bigcup_{l\in
S}\bigcup_{\mathbb{P}^{il}\in\mathbb{W}_{il}}\bigcup_{\mathbb{P}^{lj}\in\mathbb{M}_{lj}}\mathbb{P}^{il}\odot\mathbb{P}^{lj}\right)$
(note that $l$ is the first node in a walk $\mathcal{Q}$ such that this node
is in $S$). Taking operator $\vee$ on both sides yields equation (37).

To show equation (20), it suffices to show that

${{\mathbf{M}}_{SS}}({\mathbf{G}})=\underbrace{{{\mathbf{W}}_{SS}}({\mathbf{G}},S)}_{{\text{Walks
never passing
}}S}+\underbrace{\left({{{\mathbf{W}}_{SS}}({\mathbf{G}},S)-{\mathbf{I}}}\right)\left({{{\mathbf{M}}_{SS}}({\mathbf{G}})-{\mathbf{I}}}\right)}_{{\text{Walks
always passing }}S}\hfill\\\ $ (38)

which follows from the following decomposition414141The intuition for the
decomposition is similar, hence omitted. Here $k$ is the first node of a walk
in $\mathbb{M}_{ij}(\mathbf{G})\backslash\mathbb{W}_{ij}(\mathbf{G},S)$ so
that that node is in $S$. We must remove the walk with length zero in
$\mathbb{W}_{ik}$ and $\mathbb{M}_{kj}$ to guarantee uniqueness of
concatenation decomposition, which explains the identity matrix in equation
(38).

$\mathbb{M}_{ij}(\mathbf{G})\backslash\mathbb{W}_{ij}(\mathbf{G},S)=\bigcup_{k\in
S}\bigcup_{\mathcal{P}^{ik}\in\mathbb{W}_{ik}(\mathbf{G},S)\backslash\\{(i)\\}}\bigcup_{\mathcal{P}^{kj}\in\mathbb{M}_{kj}(\mathbf{G})\backslash\\{(k)\\}}\mathcal{P}^{ik}\odot\mathcal{P}^{kj}.$

for $i,j\in S$. Taking $\vee$ on both sides yields

$m_{ij}-w_{ij}=\sum_{k\in
S}{[w_{ik}(\mathbf{G},S)-\mathbf{1}_{\\{k=i\\}}][m_{kj}(\mathbf{G})-\mathbf{1}_{\\{k=j\\}}]},$

which holds for any $i,j\in S$, thus is equivalent to equation (38).

###  B.2 Key bridge index

In this Section we prove the following identity:

$b\left(\mathbf{G+E}_{ij}\right)-b\left(\mathbf{G}\right)=\delta
L_{ij}\left(\mathbf{N}^{1},\mathbf{N}^{2}\right)=\frac{\delta^{2}m_{jj}\left(\mathbf{N}^{2}\right)b_{i}^{2}\left(\mathbf{N}^{1}\right)+\delta^{2}m_{ii}\left(\mathbf{N}^{1}\right)b_{j}^{2}\left(\mathbf{N}^{2}\right)+2\delta
b_{j}\left(\mathbf{N}^{2}\right)b_{i}\left(\mathbf{N}^{1}\right)}{1-\delta^{2}m_{jj}\left(\mathbf{N}^{2}\right)m_{ii}\left(\mathbf{N}^{1}\right)}$
(39)

$\forall i\in N_{1},j\in N_{2},$ where $\mathbf{G}$ is in the union of two
isolated networks. For ease of notation we drop the network variable in
$m_{ii},b_{i},b_{j},m_{jj}$.

Define $\mathbb{W}_{.i}=\bigcup_{i\in N}\mathbb{W}_{ji}$ as the set of walks
ending at $i$. Define $\mathbb{W}_{i.}=\bigcup_{l\in N}\mathbb{W}_{il}$ as the
set of walks starting with $i$ Clearly,
$\vee(\mathbb{W}_{.i})=\vee(\mathbb{W}_{i.})=\sum_{j\in N}m_{ij}=\sum_{l\in
N}m_{il}=b_{i}$. Note that the term on the left-hand side of equation (39) is
the discounted sum of additional walks due to the new link $(i,j)$. We will
divide these new walks into four types, and contribute each type to a term on
the right-hand side of equation (39).

(Type I) The new walks starting a node in $\mathbf{N}^{1}$ and ending at a
node in $\mathbf{N}^{2}$.

Take such a walk $\mathcal{Q}$. Suppose it passes the bridge link $(i,j)$ only
once, it can be uniquely written as
$\mathcal{P}^{.i}\odot(i,j)\odot\mathcal{P}^{j.}$, where
$\mathcal{P}^{.i}\in\mathbb{W}_{.i}(\mathbf{N}^{1})$ and
$\mathcal{P}^{j.}\in\mathbb{W}_{j.}(\mathbf{N}^{2})$ (see Figure 6 for such an
example). We have

$\vee\left(\bigcup_{\mathcal{P}^{.i}\in\mathbb{W}_{.i}(\mathbf{N}^{1})}\bigcup_{\mathcal{P}^{j.}\in\mathbb{W}_{j.}(\mathbf{N}^{2})}\mathcal{P}^{.i}\odot(i,j)\odot\mathcal{P}^{j.}\right)=\vee\left(\mathbb{W}_{.i}\right)\times\delta\times\vee\left(\mathbb{W}_{j.}\right)=\delta
b_{i}b_{j}.$

However, $\mathcal{Q}$ can also pass the bridge link $(i,j)$ three times, give
times, etc. We can apply similar exercise to show that the set of walks
originating from nodes in $\mathbf{N}^{1}$ and stopping at nodes in
$\mathbf{N}^{2}$ which pass $\left(i,j\right)$ for exactly three times is
given by

$\bigcup_{\left(k,l\right)\in N_{1}\times
N_{2}}\bigcup_{(\mathcal{P}^{ki},\mathcal{P}^{jj},\mathcal{P}^{ii},\mathcal{P}^{jl})\in(\mathbb{M}_{ki}(\mathbf{N}^{1}))\times(\mathbb{M}_{jj}(\mathbf{N}^{2}))\times(\mathbb{M}_{ii}(\mathbf{N}^{1}))\times(\mathbb{M}_{jl}(\mathbf{N}^{2}))}(\mathcal{P}^{ki}\odot\left(i,j\right)\odot\mathcal{P}^{jj}\odot\left(j.i\right)\odot\mathcal{P}^{ii}\odot\left(i,j\right)\odot\mathcal{P}^{jl})$

(Figure 7 gives a walk that passes the bridge three times.) Taking $\vee$
yields

$\displaystyle\sum_{k\in
N_{1}}\vee\left(\mathbb{M}_{ki}(\mathbf{N}^{1})\right)\cdot\delta\cdot\vee\left(\mathbb{M}_{jj}(\mathbf{N}^{2})\right)\cdot\delta\cdot\vee\left(\mathbb{M}_{ii}(\mathbf{N}^{1})\right)\cdot\delta\cdot\sum_{l\in
N_{2}}\vee\left(\mathbb{M}_{jl}(\mathbf{N}^{2})\right)$ $\displaystyle=$
$\displaystyle\delta b_{i}b_{j}(\delta^{2}m_{ii}m_{jj}).$

Similarly, $\delta b_{i}b_{j}(\delta^{2}m_{ii}m_{jj})^{2}$ captures type I
walks that pass the link $(i,j)$ five times. Taking sum yields

$\delta b_{i}b_{j}+\delta b_{i}b_{j}(\delta^{2}m_{ii}m_{jj})+\delta
b_{i}b_{j}(\delta^{2}m_{ii}m_{jj})^{2}+\cdots=\delta
b_{i}b_{j}\frac{1}{1-\delta^{2}m_{ii}m_{jj}}.$ (40)

Figure 6: New walk from one network to another by passing bridge once Figure
7: New walk from one network to another by passing bridge three times

(Type II) For the same reason, the new walks starting a node in
$\mathbf{N}^{2}$ and ending at a node in $\mathbf{N}^{1}$ contribute $\delta
b_{i}b_{j}\frac{1}{1-\delta^{2}m_{ii}m_{jj}}$ in equation (39).

(Type III) The new walks starting a node in $\mathbf{N}^{1}$ and ending at a
node in $\mathbf{N}^{1}$. By definition, such a walk must pass the bridge
$(i,j)$ two times, four times, etc. To pass the bridge twice, the walk must be
decomposed into the concatenations of the following walks:
$\mathcal{P}^{.i}\odot\left(i,j\right)\odot\mathcal{P}^{jj}\odot\left(j,i\right)\odot\mathcal{P}^{i.}$
where
$\mathcal{P}^{.i}\in\mathbb{W}_{.i},\mathcal{P}^{jj}\in\mathbb{W}_{ii}\mathcal{P}^{i.}\in\mathbb{W}_{.i}$
(See Figure 8 for an example). Taking $\vee$ of these walks yields
$\delta^{2}b_{i}^{2}m_{jj}$. To take into account the facts that such walks
can pass the bridge four times, six times, etc, we should multiply
$\delta^{2}b_{i}^{2}m_{jj}$ by $\frac{1}{1-\delta^{2}m_{ii}m_{jj}}$( the
underlying logic is similar to the exercise for type I). Together, type III
walks contribute exactly
$\delta^{2}b_{i}^{2}m_{jj}\frac{1}{1-\delta^{2}m_{ii}m_{jj}}$ in equation
(39).

Figure 8: New walk starting and ending at a same network

(Type IV) The new walks starting a node in $\mathbf{N}^{2}$ and ending at a
node in $\mathbf{N}^{2}$. This part is similar to type III and it contributes
$\delta^{2}b_{j}^{2}m_{ii}\frac{1}{1-\delta^{2}m_{ii}m_{jj}}$ in equation
(39).

##  Appendix C Interventions in alternative network models

Our paper is applicable to many other network models in which the Katz-
Bonacich centrality plays an important role in shaping the equilibrium. We
list several models. A common theme is that the Katz-Bonacich centrality,
similar to Ballester et al. (2006), is a building block of the equilibrium
objective.

  1. 1.

(Multiple activities) Chen et al. (2018b) consider a network model with
multiple interdependent activities. In the network
$\left(N,\mathbf{G}\right)$, each player $i$ can choose the levels of two
activities $\left(a_{i}^{A},a_{i}^{B}\right)=\mathbf{a}_{i}$ with utility

$\displaystyle u_{i}\left(\mathbf{a}_{i},\mathbf{a}_{-i}\right)$
$\displaystyle=$
$\displaystyle\theta_{i}^{A}a_{i}^{A}+\theta_{i}^{B}a_{i}^{B}-\left\\{\frac{1}{2}\left(a_{i}^{A}\right)^{2}+\frac{1}{2}\left(a_{i}^{B}\right)^{2}+\beta
a_{i}^{A}a_{i}^{B}\right\\}+\delta\underset{j}{\sum}g_{ij}a_{i}^{A}a_{j}^{A}+\delta\underset{j}{\sum}g_{ij}a_{i}^{B}a_{j}^{B}\text{,}$

where $\boldsymbol{\theta}_{i}=\left(\theta_{i}^{A},\theta_{i}^{B}\right)$ is
$i$’s characteristics,
$\frac{1}{2}\left(a_{i}^{A}\right)^{2}+\frac{1}{2}\left(a_{i}^{B}\right)^{2}+\beta
a_{i}^{A}a_{i}^{B}$ is the cost of action $\mathbf{a}_{i}$ and
$\delta\underset{j}{\sum}g_{ij}a_{i}^{A}a_{j}^{A}+\delta\underset{j}{\sum}g_{ij}a_{i}^{B}a_{j}^{B}$
captures the network externalities. Chen et al. (2018b) show that if
$0\leq\delta\leq\frac{1-|\beta|}{\lambda_{\max}\left(\mathbf{G}\right)}$,
there exists a unique Nash equilibrium given by

$\begin{bmatrix}\mathbf{x}^{A}\\\
\mathbf{x}^{B}\end{bmatrix}=\begin{bmatrix}\frac{1}{2\left(1+\beta\right)}\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta}^{A}+\boldsymbol{\theta}^{B},\frac{\delta}{1+\beta}\right)+\frac{1}{2\left(1-\beta\right)}\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta}^{A}-\boldsymbol{\theta}^{B},\frac{\delta}{1-\beta}\right)\\\
\frac{1}{2\left(1+\beta\right)}\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta}^{A}+\boldsymbol{\theta}^{B},\frac{\delta}{1+\beta}\right)-\frac{1}{2\left(1-\beta\right)}\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta}^{A}-\boldsymbol{\theta}^{B},\frac{\delta}{1-\beta}\right)\end{bmatrix}\text{,}$

where
$\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta},\frac{\delta}{1+\beta}\right)=\left(\mathbf{I}-\frac{\delta}{1+\beta}\mathbf{G}\right)^{-1}\boldsymbol{\theta}$.
That is, the equilibrium profile is the weighted sum of two Katz-Bonacich
centralities.

  2. 2.

(Direct complements and indirect substitutes)

Currarini et al. (2017) introduce a linear quadratic network games in which
each agent faces peer effects from the distance-one neighbors but also
exhibits local congestion effects from distance-two neighbors. Specifically,
the payoff of individual $i$ is given by

$u_{i}\left(a_{i},\mathbf{a}_{-i}\right)=\theta_{i}a_{i}-\frac{1}{2}a_{i}^{2}+\delta\sum_{k=1}^{n}g_{ik}a_{i}a_{k}-\gamma\sum_{k=1}^{n}g_{ik}^{\left[2\right]}a_{i}a_{k}\text{,}$

where the last term
$-\gamma\Sigma_{k=1}^{n}g_{ik}^{\left[2\right]}a_{i}a_{k}>0$ is new compared
with Ballester et al. (2006) and captures the strategic substitution effect
between players at distance-two in the network. Note that $\gamma\geq 0$ and
$g_{ik}^{\left[2\right]}$ is the $ik$-th element of matrix $\mathbf{G}^{2}$.
Under some regularity assumptions on $\delta$ and $\gamma$, Currarini et al.
(2017) show that the unique equilibrium equals

$\mathbf{x}^{\ast}=\left(\mathbf{I}-\delta\mathbf{G}+\gamma\mathbf{G}^{2}\right)^{-1}\boldsymbol{\theta}\text{.}$

In fact, we can rewrite the above equilibrium succinctly as a linear
combination of two Katz-Bonacich centralities:

$\mathbf{x}^{\ast}=\frac{\beta_{1}}{\beta_{1}-\beta_{2}}\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta,}\beta_{1}\right)-\frac{\beta_{2}}{\beta_{1}-\beta_{2}}\mathbf{b}\left(\mathbf{G},\boldsymbol{\theta,}\beta_{2}\right)\text{.}$
(41)

where $\beta_{1}=\frac{\delta+\sqrt{\delta^{2}-4\gamma}}{2}$ and
$\beta_{2}=\frac{\delta-\sqrt{\delta^{2}-4\gamma}}{2}$. Note that $\beta_{1}$
and $\beta_{2}$ satisfy
$\beta_{1}+\beta_{2}=\delta,\beta_{1}\beta_{2}=\gamma$. Equation (41) directly
follows from the following mathematical identity:

$\displaystyle\left(\mathbf{I}-\delta\mathbf{G}+\gamma\mathbf{G}^{2}\right)^{-1}$
$\displaystyle\boldsymbol{=}$
$\displaystyle\left(\mathbf{I}-\left(\beta_{1}+\beta_{2}\right)\mathbf{G}+\beta_{1}\beta_{2}\mathbf{G}^{2}\right)^{-1}=\frac{\beta_{1}}{\beta_{1}-\beta_{2}}\left(\mathbf{I-}\beta_{1}\mathbf{G}\right)^{-1}-\frac{\beta_{2}}{\beta_{1}-\beta_{2}}\left(\mathbf{I-}\beta_{2}\mathbf{G}\right)^{-1}\text{.}$

That is, the equilibrium in Currarini et al. (2017) equals the weighted sum of
two Katz-Bonacich centralities.

  3. 3.

(Local complementarity and global substitution) In addition to local
complementaries, players might experience global competitive effects. In one
extension, Ballester et al. (2006) consider the following utility function of
individual $i$

$u_{i}\left(a_{i},\mathbf{a}_{-i}\right)=a_{i}-\frac{1}{2}a_{i}^{2}-\phi\Sigma_{k\neq
i}a_{i}a_{k}+\delta\Sigma_{k=1}^{n}g_{ik}a_{i}a_{k}\text{.}$

where the term $\phi\Sigma_{k\neq i}a_{i}a_{k}$ is the global interaction
effect corresponds to a substitutability in efforts across all players.
$\phi\geq 0$ measures the intensity of the global interdependence. For
simplicty, we assume that each player’s intrinsic marginal utilities are
identical. Ballester et al. (2006) show that the equilibrium behavior in this
network game

$\mathbf{x}=\frac{1}{1-\phi+\phi
b\left(\mathbf{G},\frac{\delta}{1-\phi}\right)}\mathbf{b}\left(\mathbf{G},\frac{\delta}{1-\phi}\right)\text{.}$

Each player’s equilibrium strategy is a function of Katz-Bonacich
centralities. In particular, the aggregate equilibrium action,
$\mathbf{1}^{\prime}\mathbf{x=}\frac{b\left(\mathbf{G},\frac{\delta}{1-\phi}\right)}{1-\phi+\phi
b\left(\mathbf{G},\frac{\delta}{1-\phi}\right)}$, is a monotonic function of
$b\left(\mathbf{G},\frac{\delta}{1-\phi}\right)$.

Since the equilibrium in each of these model is either linear combinations or
transformations of the Katz-Bonacich centralities. We can directly apply
Proposition 1 to study the effects of structural and chracteristical
interventions, and study similar issues such as the key group and the key link
problems.

## References

  * Acemoglu et al. (2012) Acemoglu, D., V. M. Carvalho, A. Ozdaglar, and A. Tahbaz-Salehi (2012).  The network origins of aggregate fluctuations.  Econometrica 80(5), 1977–2016.
  * Allouch (2017) Allouch, N. (2017).  On the private provision of public goods on networks.  Journal of Economic Theory 157, 527–552.
  * Ballester et al. (2006) Ballester, C., A. Calvó-Armengol, and Y. Zenou (2006).  Who’s who in networks. wanted: The key player.  Econometrica 74(5), 1403–1417.
  * Ballester et al. (2010) Ballester, C., Y. Zenou, and A. Calvó-Armengol (2010).  Delinquent networks.  Journal of the European Economic Association 8(1), 34–61.
  * Banerjee et al. (2013) Banerjee, A., A. G. Chandrasekhar, E. Duflo, and M. O. Jackson (2013).  The diffusion of microfinance.  Science 341(6144).
  * Banerjee et al. (2018) Banerjee, A., A. G. Chandrasekhar, E. Duflo, and M. O. Jackson (2018).  Changes in social network structure in response to exposure to formal credit markets.  Available at SSRN 3245656.
  * Baqaee (2018) Baqaee, D. R. (2018).  Cascading failures in production networks.  Econometrica 86(5), 1819–1838.
  * Belhaj et al. (2016) Belhaj, M., S. Bervoets, and F. Deroïan (2016).  Efficient networks in games with local complementarities.  Theoretical Economics 11(1), 357–380.
  * Bloch et al. (2020) Bloch, F., M. O. Jackson, and P. Tebaldi (2020).  Centrality measures in networks.  Working paper.
  * Bloch and Quérou (2013) Bloch, F. and N. Quérou (2013).  Pricing in social networks.  Games and Economic Behavior 80, 243 – 261.
  * Bonacich (1987) Bonacich, P. (1987).  Power and centrality: A family of measures.  American Journal of Sociology 92(5), 1170–1182.
  * Boyd and Vandenberghe (2004) Boyd, S. and L. Vandenberghe (2004).  Convex optimization.  Cambridge university press.
  * Bramoullé et al. (2016) Bramoullé, Y., A. Galeotti, and B. Rogers (2016).  The Oxford handbook of the economics of networks. Oxford University Press.
  * Bramoullé et al. (2016) Bramoullé, Y., A. Galeotti, B. Rogers, and Y. Zenou (2016).  Key players.
  * Bramoullé and Garance (2018) Bramoullé, Y. and G. Garance (2018).  Diffusion centrality: Foundations and extensions.  Working paper.
  * Bramoullé and Kranton (2007) Bramoullé, Y. and R. Kranton (2007).  Public goods in networks.  Journal of Economic Theory 135(1), 478 – 494.
  * Bramoullé et al. (2014) Bramoullé, Y., R. Kranton, and M. D’Amours (2014).  Strategic interaction and networks.  American Economic Review 104(3), 898–930.
  * Cai and Szeidl (2018) Cai, J. and A. Szeidl (2018).  Interfirm relationships and business performance.  The Quarterly Journal of Economics 133(3), 1229–1282.
  * Calvó-Armengol and Jackson (2004) Calvó-Armengol, A. and M. O. Jackson (2004, June).  The effects of social networks on employment and inequality.  American Economic Review 94(3), 426–454.
  * Calvó-Armengol et al. (2009) Calvó-Armengol, A., E. Patacchini, and Y. Zenou (2009).  Peer effects and social networks in education.  The Review of Economic Studies 76(4), 1239–1267.
  * Candogan et al. (2012) Candogan, O., K. Bimpikis, and A. Ozdaglar (2012).  Optimal pricing in networks with externalities.  Operations Research 60(4), 883–905.
  * Chen et al. (2018a) Chen, Y.-J., Y. Zenou, and J. Zhou (2018a).  Competitive pricing strategies in social networks.  The RAND Journal of Economics 49(3), 672–705.
  * Chen et al. (2018b) Chen, Y.-J., Y. Zenou, and J. Zhou (2018b).  Multiple activities in networks.  American Economic Journal: Microeconomics 10(3), 34–85.
  * Choi et al. (2019) Choi, S., S. Goyal, and F. Moisan (2019).  Connectors and influencers.
  * Currarini et al. (2017) Currarini, S., E. Fumagalli, and F. Panebianco (2017).  Peer effects and local congestion in networks.  Games and Economic Behavior 105, 40 – 58.
  * David and Dina (2004) David, G. and M. Dina (2004).  Using online conversations to study word-of-mouth communication.  Marketing Science 23(4), 545–560.
  * Demange (2017) Demange, G. (2017).  Optimal targeting strategies in a network under complementarities.  Games and Economic Behavior 105, 84 – 103.
  * Elliott and Golub (2018) Elliott, M. and B. Golub (2018).  A network approach to public goods.  Journal of Political Economy forthcoming.
  * Elliott et al. (2019) Elliott, M. L., S. Goyal, and A. Teytelboym (2019).  Networks and economic policy.  Oxford Review of Economic Policy 35(4), 565–585.
  * Galeotti et al. (2020) Galeotti, A., B. Golub, and S. Goyal (2020).  Targeting interventions in networks.  Econometrica 88(6), 2445–2471.
  * Galeotti and Goyal (2010) Galeotti, A. and S. Goyal (2010).  The law of the few.  American Economic Review 100(4), 1468–1492.
  * Golub and Lever (2010) Golub, B. and C. Lever (2010).  The leverage of weak ties how linking groups affects inequality.  Working paper.
  * Goyal and Moraga-González (2001) Goyal, S. and J. L. Moraga-González (2001).  R&D networks.  The RAND Journal of Economics, 686–707.
  * Jackson et al. (2017) Jackson, M. O., B. W. Rogers, and Y. Zenou (2017).  The economic consequences of social-network structure.  Journal of Economic Literature 55(1), 49–95.
  * Jerzy (2001) Jerzy, S. (2001).  Delinquent Networks: Youth Co-Offending in Stockholm.  Cambridge Studies in Criminology. Cambridge University Press.