https://orcid.org/0000-0002-8939-6456
Abstract
Network games are commonly used to capture the strategic interactions among interconnected agents in simultaneous moves. The agents’ actions in a Nash equilibrium must take into account the mutual dependencies connecting them, which is typically obtained by solving a set of fixed point equations. Stackelberg games, on the other hand, model the sequential moves between agents that are categorized as leaders and followers. The corresponding solution concept, the subgame perfect equilibrium, is typically obtained using backward induction. Both game forms enjoy very wide use in the (cyber)security literature, the network game often as a template to study security investment and externality—also referred to as the interdependent security games—and the Stackelberg game as a formalism to model a variety of attacker–defender scenarios. In this study, we examine a model that combines both types of strategic reasoning: the interdependency as well as sequential moves. Specifically, we consider a scenario with a network of interconnected first movers (firms or defenders, whose security efforts and practices collectively determine the security posture of the eco-system) and one or more second movers, the attacker(s), who determine how much effort to exert on attacking the many potential targets. This gives rise to an equilibrium concept that embodies both types of equilibria mentioned above. We will examine how its existence and uniqueness conditions differ from that for a standard network game. Of particular interest are comparisons between the two game forms in terms of effort exerted by the defender(s) and the attacker(s), respectively, and the free-riding behavior among the defenders.
Introduction
Network games are commonly used to capture the strategic interactions among interconnected agents. As a special type of strategic game, network games highlight the critical role physical or logical connectivity can play in determining the outcomes of social, technological, and economic interactions [1–7]; this is seen in many real-world scenarios such as trade, exchange and spread of information, and the marketing and adoption of technology, to name a few. This framework is widely used in the context of local provision of public goods [5, 8, 9]. One of the primary goals of this line of research has been to identify how properties of the connectivity, i.e., the underlying interaction graph that represents mutual dependencies and influences among the agents, impact the equilibrium outcomes of such games in terms of their analysis, computation, as well as the conditions under which an equilibrium solution exists, is unique and/or is stable. Network games are almost always studied as a strategic, simultaneous-move game, with the notion of Nash equilibrium (NE) used to study their outcomes.
In the security context, public good provision games are often utilized as a framework to model strategic defense decisions; examples include airline security [10] and cybersecurity [5, 11–14], where network games have often been referred to as interdependent security (IDS) games. These models are used to study the provision of security and defense mechanisms by a set of interconnected and interdependent entities (representing companies, agencies, and organizations). Typically, the impact of security effort in such a model is captured through the agents’ utility function, which is an increasing function of effort (or more precisely, some type of total weighted effort to reflect its dependency on other agents’ effort); an adverse event or the existence of an attacker or adversary is not explicitly modeled, with the exception of the seminal work by Bracken and McGill [15, 16] (and studies that followed) on the two-stage modeling of the defense-assault application. Bracken and McGill also pioneered the rich field of bilevel programming, which has found broad applicability in adversarial security games.
In this paper, we are interested in understanding more explicitly the interaction between interconnected defenders and similarly interconnected attackers. The differentiation between the defenders and the attackers not only lies in the dependence relationship (e.g., a defender may benefit from a fellow defender’s effort, but will suffer harm from an attacker’s effort), but also in the sequentiality of their actions; i.e., a (targeted) attack often takes into account some knowledge of the state of the defender. In practical terms, this assumption is supported by the observation that cyber criminals, in order to accomplish their attack goals, often conduct pre-attack exploration of vulnerable systems, employing techniques such as device finger-printing, port scanning [17, 18], social engineering [19], and similar methods.
Toward this end, we propose a Stackelberg game played among a set of interconnecting agents that include both defenders and attackers. The defenders are simultaneous first movers and the attackers are simultaneous second movers best responding to the defenders. The defenders’ actions are both in anticipation of the attackers’ best response and in anticipation of the impact from other defenders’ actions through the interaction graph. This leads to the investigation of a special type of Subgame Perfect Equilibrium (SPE) as the solution concept, and is obtained through the backward induction, which now involves solving a set of fixed point equations in both stages of the induction (by the defenders and the attackers, respectively).
It’s worth noting that Stackelberg games as a formalism also enjoys very wide use in the cybersecurity literature. While the network game (or IDS game) is often used to study security effort and externality, the Stackelberg game has been used to model a variety of attacker–defender scenarios [15, 20]. To the best of our knowledge, this study is the first attempt at overlaying a Stackelberg game on top of a network game. Our main findings are as follows:
We first show that for a special class of interior SPE, the defenders’ first stage game in the sequential network game is equivalent to a simultaneous-move network game played by the defenders on the Schur complement [21] of the interdependency (sub)matrix of the attackers in the full interdependency matrix (Theorem 1). We refer to this as the reduced network game and use its properties to gain insights into defenders’ behavior in the SPE of the sequential network game.
We then study a sequential network game with multiple defenders and multiple attackers, and contrast the sequential game (i.e., defenders move first and the attackers move second) with a simultaneous-move game (i.e., all players choose actions simultaneously). We identify conditions under which the sequential nature of the game induces lower free-riding behavior and lower effort by the defenders (Propositions 2). We show that the magnitude of this decrease aligns with the alpha-centrality of defenders in the reduced network (Proposition 2).
We further identify instances under which the opposite happens, i.e., when sequentiality leads some defenders to increase their effort, which may, in turn, lead the attacker to also increase its attack effort. Specifically, we illustrate a situation where severe free riders (those substantially “supported” by other defenders’ efforts in the simultaneous-move game) are “exposed”, with a diminished ability to free ride in the sequential setting (Section “‘Exposed’ free rider”). Intuitively, such defenders invest more in the SPE than the corresponding NE due to losing support from other defenders who invest less in the sequential game. We then show that as a result of this increase in effort by exposed free riders, the attacker may best respond by increasing its attack effort (Section “Exposed free-riders could lead to higher attacker effort”).
Lastly, we investigate the efficiency of the interior equilibrium solution (in terms of the defenders’ welfare). In particular, we show that for certain network structures, defenders overinvest in the interior sub-game perfect equilibrium (I-SPE) compared to socially optimal efforts. We highlight how this can be attributed to the sequential nature of the game, where the presence of attackers can “turn allies into adversaries” (Section “Comparing the I-SPE with socially optimal efforts”).
The remainder of the paper is organized as follows. We review the literature most closely related to this work in the section “Related literature.” We present the network-Stackelberg game model in the section “The model,” followed by its equilibrium analysis in the section “Equilibrium analysis.” We then contrast sequential vs. simultaneous-move multi-defender multi-attacker games in the section “Network security: how sequentiality affects players’ behavior.” We discuss the limitations of our model and directions of future works in the section “Discussions,” and conclude the paper in the section “Conclusion.”
Related literature
Of the literature on Stackelberg games, the most closely related to the present work are those that have studied Stackelberg public good provision, exploring the benefits to the leaders and/or contrasting the outcomes with those of simultaneous-move games. Sherali [22] studied a sequential game in the oligopoly market with identical firms which differ only in the sequence of participation. Sherali observed that leaders always make higher profit than followers, and each leader’s profit is maximized when it is the only leader of the game. These results shed light on the leaders’ sequential exploitation of the followers, but focus only on competitive relationship between agents. Varian [23] constructed a quasilinear model on two-agent sequential public-good games and examined subsidy mechanisms that can yield Lindahl allocations. Varian concluded that without mechanisms, the provision of public good and the sum of utilities would be less than those in the simultaneous counterpart. However, opposite results are observed in several papers in experimental economics on sequential step-level public good games, such as Erev and Rapoport [24] and Normann [25]. Both experiments show that sequential step-level games actually improve public-good provision, even though second movers often punish first movers for insufficient effort. The reason for the improvement, as suggested by Normann, is the role model effect: when the first mover tends to invest more in the public good, it serves as a role model for the second mover, who in turn would invest more. These different observations on the impact of a sequential setting on the provision of public goods are, to an extent, due to the difference of the models, where Varian [23] considers continuous and quasilinear utilities, while Erev and Rapoport, and Normann’s utilities are discrete. Additionally, these models only account for positive externalities between players and do not adequately incorporate a combination of positive and negative externalities, which can be effectively modeled through the framework of network games [1, 4–6].
To the best of our knowledge, our work is the first to analyze network games played in sequential order, and to contrast them with their simultaneous-move counterparts. Our model uses classical network game as a building block. More specifically, our modeling technique is a continuation of linear best response network games found in the vast literature [1, 5, 8, 14, 26, 27], although the introduction of sequential moves in our model effectively leads to non-linear best responses. The construction of our proof is based on the P-matrix theory [5, 6] to characterize the existence and uniqueness of NE in simultaneous-move network games.
The broader network games literature is a rich one, and goes beyond those most relevant and cited above. We note some examples of how the present study differs from prominent network game formalisms found in this literature: Elliott and Golub [9] modeled the underlying dependence structure as a non-static network whose edge weights vary with agent actions, while edge weights in our model are static; Galeotti et al. [28] examined the information asymmetry over networks, while ours is a complete information model; finally, Acemoglu, Malekian, and Ozdaglar [29] modeled security attacks as a contagion spreading over a network, which led to a very different utility function where agents’ efforts are multiplicative, whereas in our model (and those cited earlier), the efforts are (weighted but) additive.
The model
We consider an IDS game played in a sequence of two sets of moves, the first by a set of simultaneous defenders |$\mathcal {D}$| and the second by a set of simultaneous attackers |$\mathcal {A}$|.
Each player or agent |$i$| chooses an action |$x_i\in \mathbb {R}_+$| denoting its level of effort in the public good. All players are interconnected by the game matrix |$G$|, the |$(i,j)^{th}$| entry of which denotes the dependence of player |$i$|’s utility on player |$j$|’s action. Thus, it is sometimes called a dependence matrix and conversely, |$G^T$| is sometimes called an influence matrix. Accordingly, whenever there is an edge pointing from i to j, we say player i depends on player j, or player j influences player i. Without the loss of generality, we assume all diagonals of G are 1, i.e., |$g_{ii}=1, \forall i$|. The matrix G is equivalent to a directed graph with edge weights representing both the connectivity among agents and the strengths of their connections. In graph theory terminology, the matrix |$G-I$| is the adjacency matrix of the network with I being the identity matrix.
Since the agents separate into defenders and attackers, it makes sense to divide the matrix G in blocks as follows:
where D and A represent the dependency within each player set |$\mathcal {D}$| and |$\mathcal {A}$|, respectively, while B and C represent the (cross-)dependency between player sets |$\mathcal {D}$| and |$\mathcal {A}$|. For the most part, we will use notations like |$d_{ij}$| and |$b_{ij}$| so as to make it clear the types of agents the edge weight is connecting; occasionally we will use |$g_{ij}$| to refer to a generic element in the full matrix.
Let |$\mathbf {x}_d$| be the action profile (a column vector) of all defenders and |$\mathbf {x}_a$| be the action profile of all attackers. Denote by |$\mathbf {x}:=(\mathbf {x}_d^T,\mathbf {x}_a^T)^T$| the joint action profile of all players. In this two-stage setting, the defenders can be viewed as solving an equilibrium problem in a standard network game played on the network D, anticipating the attackers’ reaction to their own choices, i.e., |$\mathbf {x}_a(\mathbf {x}_d)$|, while the attackers can be seen as solving an equilibrium problem in another standard network game played on A but with |$\mathbf {x}_d$| as fixed parameters. More precisely, we adopt the following players’ utility functions: for each |$i\in \mathcal {D}\cup \mathcal {A}$|,
where |$f_i(\cdot )$| is the benefit function of player i and |$\beta _i\gt 0$| is player i’s unit cost of effort. We will assume |$f_i(\cdot )$| is continuously differentiable, strictly increasing, and strictly concave for all i. We also assume that |$f_i^{\prime }(\cdot )$| is a convex function. This type of utility is also commonly known as the total weighted effort model in the literature of public good games, see, e.g., Grossklags et al. [11] and Varian [14], where the argument of the utility function |$f_i(\sum _{j}g_{ij}x_j)$| is called the total weighted effort received by player i. Note that this benefit function is a generalization of public good provision games with a linear best response, which has been widely used in the literature [5, 8, 30].
Before proceeding, we introduce the following assumption to make our problem more tractable.
For every player |$i\in \mathcal {D}\cup \mathcal {A}$|, |$f_i^{\prime }(-\infty ) = \infty$| and |$f_i^{\prime }(\infty )=0$|. This implies the existence of |$q_i\in \mathbb {R}$| such that |$f_i^{\prime }(q_i)=\beta _i$|. We will denote |$\mathbf {q}_d:=(q_i)_{i\in \mathcal {D}}$| and |$\mathbf {q}_a:=(q_i)_{i\in \mathcal {A}}$|, and assume |$\mathbf {q}_d,\mathbf {q}_a\ge 0$| for simplicity.
In words, |$q_i$| is player i’s optimal effort when it is disconnected from everyone. This quantity is also known as the autarkic value [26] of player i, which is determined exclusively by its own type. When a player is also impacted by its neighbors’ aggregate effort, it chooses its effort such that its total weighted effort reaches the autarkic value. If the player’s own effort ends up being lower than its autarkic value because it is benefiting from its neighbors’ effort, we say the player free rides.
A few comments are in order. First, in this model each agent has a scalar action, interchangeably termed the effort. This scalar action should be interpreted as a generic, non-targeted effort: common broad-based security mechanisms for a defender (such as firewalls, intrusion detection systems, etc.), and for an attacker, effort in attack technology, which is then applied to all defenders. How susceptible a specific defender is to a specific attacker (the edge weights hard-coded in the game parameters) encapsulates factors not explicitly modeled; e.g., an entity with a large number of employees may be particularly susceptible to an attacker specializing in phishing, but less so to an attacker specializing in exploiting unpatched system vulnerabilities.
Secondly, there are two sets of terminologies frequently used in such a network setting that deserve some clarification, as we will repeatedly use these later on: positive vs. negative externality, and whether one’s effort acts as a strategic complement or strategic substitute to that of another. In general, an action by a player is said to carry positive externality if the same, self-serving action also benefits others that depend on it. In the context of a network game with total weighted effort utility functions, this is often associated with a positive edge weight on an incoming edge to the player taking the action, where an increase in effort by this player benefits its neighbor who depends on this player; this is clearly seen in the total weighted effort model given above. Conversely, negative externality is typically associated with a negative edge weight. Whether the effort being provisioned is a strategic substitute or strategic complement has to do with whether the increase in a player’s effort would lead a dependent neighboring player to decrease or increase its own effort, strategic substitute in the former and strategic complement in the latter. This, too, is indirectly associated with the signs of the edge weights in the total weighted effort model: often a positive edge weight means strategic substitute and negative means strategic complement. It is because, in total weighted effort models, the edge weights also appear as the (negative) coefficients of the peers’ efforts in the best response functions, a point to be clear in the following examples. However, the interpretation of both sets of concepts and their association with the edge weights ultimately depends on the utility function one adopts. Suffice to say that the total weighted effort model presented above does allow us to associate positive (resp. negative) edge weights with both positive (resp. negative) externality and actions being strategic substitutes (resp. strategic complements) as described above.
Figure 1 depicts the relationship between these concepts and the autarkic value in a two-player example, where a single edge points from player |$1$| to player |$2$| with an edge weight of |$e$|. This is shown through the best response (BR) of player 1 to player 2’s action |$x_2$|, which is taken as given in this example. In total weighted effort models with linear costs, this best response function is linear and given by |$BR_1(x_2)=\max \lbrace 0,q_1-ex_2\rbrace$|. This is shown in two cases: when |$e\gt 0$| (the orange curve) and when |$e\lt 0$| (the blue curve). Specifically, when |$e\gt 0$|, the amount that 1 has to invest to reach its autarkic value is reduced by |$|e|x_2$|, the share in player 1’s total weighted effort that comes from player 2. Therefore, player |$1$| would always select an effort level less than |$q_1$|, free riding on player 2. In the extreme case, when |$x_2\ge \frac{q_1}{|e|}$| (the flat segment of the orange curve), then player |$1$|’s total weighted effort has already reached its autarkic value |$q_1$| and hence has no incentive to take any positive action. This is a case of player 2’s action |$x_2$| substituting for 1’s own action. In the opposite case, when |$e\lt 0$|, any positive |$x_2$| lowers player 1’s total weighted effort, forcing it to invest an additional |$|e|x_2$| to compensate for this loss, resulting in a |$x_1$| higher than |$q_1$|, forming a strategic complement relationship.
Saturation point and strategic substitute/complement.
In the context of cybersecurity, the total weighted effort model captures the fact that one player’s security effort generally contributes to another, connected player’s security posture. Sometimes this contribution is positive, e.g., a more secure service provider enhances the security of a customer that depends on its service. Other times this can be negative, e.g., strong defense by one player could induce threats to be directed at other players. In our analysis, we will generally take the view that security effort has positive externality among defenders, whereas attack effort carries negative externality for defenders.
Our goal with the two-stage network game model laid out in Eq. (2) is to understand how the resulting equilibrium compares to that of a typical, simultaneous-move public goods game, to which our model is a natural extension. In a standard total weighted effort game, the NE is obtained by finding the fixed point of all agents’ linear best response functions. It is worth noting that this step is much more complicated in the proposed sequential network game. This is because the best response mappings for the defenders are no longer linear, which will be discussed at length in the section “Equilibrium analysis”.
Equilibrium analysis
The problem outlined in the previous section is a two-stage dynamic (Stackelberg) game with perfect information, where the standard solution concept is the SPE. An action profile |$\mathbf {x}^{*}$| is a SPE if every sub-game with |$\mathbf {x}^{*}$| constrained to that sub-game forms an NE. SPE in Stackelberg games is commonly solved using backward induction. We will limit our attention to an (easier) sub-class of SPE and utilize the backward-induction technique to resolve it.
Interior subgame-perfect equilibrium
Provided the defenders’ profile |$\mathbf {x}_d$|, the attackers’ game becomes a standard (simultaneous-move) network game. Naghizadeh and Liu showed that due to the strict concavity of utility functions in the second stage, |$\mathbf {x}_a^{*}(\mathbf {x}_d)$| is an NE among the attackers if and only if the following system of equations holds simultaneously [5]:
for every |$i\in \mathcal {A}$|. We shall call |$\mathbf {x}_a^{*}(\mathbf {x}_d)$| the attackers’ equilibrium response function to |$\mathbf {x}_d$|.
Using backward induction and substituting Eq. (3) for the defenders’ utility functions in Eq. (2), we obtain a simultaneous-move game among the defenders, referred to as the reduced game, formally defined below.
A reduced game is the simultaneous-move game among the defenders, obtained after one step of backward induction, i.e., replacing the terms |$\lbrace x_j:j\in \mathcal {A}\rbrace$| in the defenders’ utility functions (2) with the attackers’ equilibrium response functions |$\lbrace x_j^{*}(\mathbf {x}_d):j\in \mathcal {A}\rbrace$|.
By the standard definition, a Nash equilibrium (NE) of the reduced game is a sub-game perfect equilibrium (SPE) of the original sequential game. However, the fact that the attackers can choose boundary actions, i.e., |$x_j=0$| for some |$j\in \mathcal {A}$|, complicates the application of standard results on the existence and computation of an NE.
This is because the utility functions in the reduced game may become non-differentiable and non-concave due to the max operator in Eq. (3). Both properties are essential for classical results on the existence and uniqueness of NE, such as fixed-point theorems and variational inequalities, to apply.
In light of this difficulty, we will focus on a sub-class of the SPE, where all players choose interior actions, referred to as an interior sub-game perfect equilibrium (I-SPE) defined as follows.
An action profile |$\mathbf {x}:=(\mathbf {x}_d^T,\mathbf {x}_a^T)^T$| is called an interior sub-game perfect equilibrium (I-SPE) if it is sub-game perfect with |$\frac{\partial u_i}{\partial x_i}(\mathbf {x})+\sum _{j\in \mathcal {A}}\frac{\partial u_i}{\partial x_j}(\mathbf {x})\cdot \frac{\partial x_j^{*}}{\partial x_i}(\mathbf {x}_d)=0$| for every |$i\in \mathcal {D}$| and |$\frac{\partial u_j}{\partial x_j}(\mathbf {x})=0$| for every |$j\in \mathcal {A}$|.
A similar concept, interior Nash equilibrium (I-NE), arises when players from both |$\mathcal {D}$| and |$\mathcal {A}$| choose actions simultaneously rather than sequentially.
An action profile |$\mathbf {x}$| is called an interior Nash equilibrium (I-NE) if it is a Nash equilibrium and |$\frac{\partial u_i}{\partial x_i}(\mathbf {x})=0$| for every player |$i\in \mathcal {D}\cup \mathcal {A}$|.
Conditions on the network structure
In this subsection, we introduce a set of conditions on the network structure and their interpretations in the cybersecurity context. We will show how these conditions help mitigate the technical challenge discussed above, and lead to the existence of interior subgame-perfect equilibrium, which are analyzed in the next subsection.
The game matrix G satisfies the following conditions:
G is a P-matrix, i.e., a matrix for which the determinant of all its principal minors are positive;
B and C are non-positive matrices, i.e, |$b_{ij},c_{ij}\le 0$| for all |$i,j$|;
A is a Z-matrix, i.e., |$a_{ij}\le 0$| for all |$i\ne j$|.
Intuitively, the P-matrix assumption in Condition 1-(1) restricts the magnitude of mutual dependencies of the same type (strategic substitute or strategic complement) between any subset of players. Specifically, the P-matrix condition requires that |$g_{ij}g_{ji}\lt g_{ii}g_{jj}=1$|. If the mutual dependence |$g_{ij}$| and |$g_{ji}$| have the same sign (positive for strategic substitute and negative for strategic complement), then this requires that the magnitude of their product should always be bounded above by 1. Thus, the P-matrix property can be interpreted as stating that the magnitude of mutual dependencies of the same type cannot be too large. Notice that this applies to all players in the game rather than just defenders or attackers.
Condition 1-(2) captures the attackers’ damaging effect on the defenders: each attacker’s effort decreases the utility of every defender and therefore serves to counter the efforts exerted by the defenders. Similarly, it captures the defenders’ deterrence effect on the attackers. This modeling assumption was similarly adopted in Varian’s seminal work [14], where both defenders and attackers move simultaneously in a total effort model.
Condition 1-(3) states that the attackers’ efforts can decrease other attackers’ utilities. This may arise in real-world situations when attackers compete against each other to profit from victims. A special case of Condition 1-(3) is when the attackers are mutually independent, whereby A becomes the identity matrix.
Restricting A to be a Z-matrix has the additional benefit of preventing the attackers from exerting boundary efforts. We illustrate this point through the following example.
It can be checked that all principal minors of G are positive and thus G is a P-matrix. This example illustrates a case where attackers are strategic substitutes to each other [thus not satisfying Condition 1-(3)] and attacker 2 benefits more from attacker 3’s effort than the other way round.
The above functions imply that when the defender invests high effort (|$x_1\gt 4$|), both attackers exert positive efforts that increase in the defender’s effort; when the defender invests lower effort (|$x_1\le 4$|), attacker 3 still invests effort that is increasing in the defender’s effort, but attacker 2 now free rides on attacker 3’s effort. The (positive) coefficients of |$x_1$| imply the strategic complement relationship between the defender and the attackers. Notice how each coefficient equals the negative edge weight between the related pair of players in the network.
Player 1’s utility in the reduced game in Example 1. The range of |$x_1$| is restricted to (2,5.5) to emphasize the region of non-concavity.
The problem arises because the piecewise linearity of the attackers’ responses in (4) introduces convexity into the defender’s received aggregated effort. This type of non-concavity can be remedied when A is a Z-matrix, because the mutual strategic complement relationships between the attackers can rule out boundary efforts; as a result |$x_2^{*}(x_1)$| and |$x_3^{*}(x_1)$| would both be purely linear in |$x_1$|.
Main result
First define |$G/A:=D-BA^{-1}C$| as the Schur complement [21] of the block |$A$| in G. For each |$i\in \mathcal {D}$|, if |$(G/A)_{ii}\gt 0$|, then define |$\tilde{q}_i$| such that |$f_i^{\prime }(\tilde{q}_i) = \frac{\beta _i}{(G/A)_{ii}}$|. This is the autarkic value of defender i in the reduced game. If every |$\tilde{q}_i$| exists, we stack them into a column vector |$\tilde{\mathbf {q}}_d:=(\tilde{q}_i)_{i\in \mathcal {D}}$| and call this the reduced autarkic value: it is the autarkic value of the reduced game, and as we will see later it is also smaller in quantity.
Let Condition 1 hold. Then, |$\tilde{\mathbf {q}}_d$| is well defined and there exists a unique SPE. Also, this SPE is an I-SPE, given by |$\mathbf {x}^{*}=G^{-1}[\tilde{\mathbf {q}}_d^T,\ \mathbf {q}^T_a]^T$|, if |$G^{-1}[\tilde{\mathbf {q}}_d^T,\ \mathbf {q}^T_a]^T\ge 0$|.
Step 1. We first show that all attackers are going to play interior actions. It is known that matrices that are both Z-matrices and P-matrices are nonsingular M-matrices and that any principal submatrix of a P-matrix is also a P-matrix [31]. This, together with condition 1-(3), imply that A is a nonsingular M-matrix. Furthermore, the inverse of a nonsingular M-matrix is a non-negative matrix [31]. Therefore, due to the positivity of |$\mathbf {q}_a$| (Assumption 1) and |$-C$|, we know |$\mathbf {x}_a^{*}(\mathbf {x}_d)=A^{-1}(\mathbf {q}_a-C\mathbf {x}_d)$| is the unique solution to the system (3) for every |$\mathbf {x}_d\ge 0$|. It can be verified that this is always an interior solution, i.e., |$\frac{\partial u_i}{\partial x_i}(\mathbf {x}_d,\mathbf {x}_a^{*}(\mathbf {x}_d))=0$| for every |$i\in \mathcal {A}$| and |$\mathbf {x}_d\ge 0$|.
Since |$G$| is a P-matrix, |$G/A$| is also a P-matrix [31]. Thus, |$(G/A)_{ii}\gt 0$| for all |$i\in \mathcal {D}$| since they are the |$1\times 1$| principal minors of |$G/A$|, and hence |$\tilde{\mathbf {q}}_d$| is well-defined. Furthermore, by replacing |$f_i(\cdot )$| with |$\tilde{f}_i(\cdot ):=f_i(\cdot -t_i)$| where |$t_i=[BA^{-1}\mathbf {q}_a]_i$|, one can recover a standard simultaneous-move network game played over the network |$G/A$|. Since |$G/A$| is a P-matrix, this game has a unique NE.
By the stated conditions, |$\mathbf {v}_1,\mathbf {v}_2$| are both non-negative. One can easily verify that |$\mathbf {v}_1$| is the solution to Eq. (6). Thus, it is the unique NE of the reduced game. Furthermore, |$\mathbf {v}_2$| is exactly the equilibrium reaction of the attackers to the defenders’ action profile |$\mathbf {v}_1$|. Thus, |$[\mathbf {v}_1^T,\mathbf {v}_2^T]^T$| constitutes the unique SPE. Besides, since |$\frac{\partial \tilde{u}_i}{\partial x_i}(\mathbf {v}_1,\mathbf {v}_2)=0$| for |$i\in \mathcal {D}$| and |$\frac{\partial u_j}{\partial x_j}(\mathbf {v}_1,\mathbf {v}_2)=0$| for |$j\in \mathcal {A}$|, it is also the unique I-SPE of this game.
Theorem 1 reveals an interesting connection between the sequential game and the simultaneous-move game on a network. When the attackers are known to play interior actions, the defenders’ reduced game is equivalent to a simultaneous-move game with game matrix |$G/A$| (the Schur complement of A in G). With a slight abuse of terminology, we will also refer to the latter as the reduced game and |$G/A$| as the reduced game matrix for the rest of the paper. Note also the dimensionality reduction in the game matrix from the original game, i.e., |$dim(G/A)=dim(A)\lt dim(G)$|.
The proof of Theorem 1 also implies that the second term of the reduced game matrix |$BA^{-1}C$| is non-negative. This indicates that the edge weights in the reduced game matrix |$G/A$| are no more than those in D, i.e., the original edge weights among defenders. Thus, we immediately see a strategic complement effect induced by the presence of the attackers. When defenders increase their effort, the attackers, in response, increase their effort which in turn incentivizes the defenders to increase their effort even more. This additional path of dependency through attackers yields this strategic complement effect. The overall strategic effect between any two defenders is a combination of the direct network effect reflected by the edge weights, and the indirect strategic complement effect through attackers, depending on which one dominates. Interestingly, if some edges are positive in the original game but become negative in the reduced game, then it means that the presence of the attackers has turned strategic substitutes into strategic complements, or in other words, allies into adversaries.
We next compare the autarkic values in the simultaneous-move game and the sequential (represented by the reduced form according to Theorem 1) game.
|$\tilde{\mathbf {q}}_d\le \mathbf {q}_d$|.
According to the proof of Theorem 1, |$A^{-1}$| is a non-negative matrix. Thus, the matrix |$BA^{-1}C$| is also non-negative. Then, |$(G/A)_{ii}=1-[BA^{-1}C]_{ii}\le 1$|. Thus, for every |$i\in \mathcal {D}$|, |$\frac{\beta _i}{(G/A)_{ii}}\ge \beta _i$|. At the same time, the concavity of |$f_i$| implies that |$f_i^{\prime }(\cdot )$| is decreasing. This, combined with the definition |$f_i^{\prime }(q_i)=\beta _i$| and |$f_i^{\prime }(\tilde{q}_i)=\frac{\beta _i}{(G/A)_{ii}}$|, implies |$\tilde{q}_i\le q_i$|.
The decrease in the autarkic value reflects the defenders’ tendency to invest less in the sequential game, as a result of each defender’s internalization of the indirect effect of its own efforts through the attackers. This can be recognized by the definition of |$\tilde{q}_i:=(f_i^{\prime })^{-1}\big (\frac{\beta _i}{(G/A)_{ii}}\big )$| where |$(G/A)_{ii}=1-[BA^{-1}C]_{ii}$|. The “1” is the original effect of defender i’s effort on its own utility and |$[BA^{-1}C]_{ii}$| is the indirect effect through the attackers. This indirect effect lowers the effectiveness of the defenders’ efforts as if they perceive a higher cost per unit effort. As a consequence, the defender becomes indifferent earlier at a smaller effort level. An explanation is depicted in Fig. 3.
The drop in the autarkic value in the sequential setting.
The following example illustrates the main takeaways of Theorem 1 and Lemma 1 intuitively in a two defenders and one attacker situation.1
from which we observe that defenders efforts are strategic substitutes to each other (|$-d_{ij}\lt 0$|), while the attacker’s effort is strategic complement to the defenders (|$-b_i\gt 0$|).
for every |$i\in \mathcal {D}$| and |$j\in \mathcal {D}\backslash \lbrace i\rbrace$|, where |$\tilde{q}_i=\big [f_i^{\prime }\big ]^{-1}\big (\frac{\beta _i}{1-b_ic_i}\big )$|.
The change of strategic relationship is evident through the comparison of |$x_2$|’s coefficients between Eqs. (7) and (9)—how |$d_{ij}$| compares to |$b_ic_j$|. The former is the direct network effect encoded in the edge weights, while the latter is the indirect strategic complement effect considering how the attacker would respond to other defenders’ efforts. Interestingly, the coefficient in front of Eq. (9) illustrates the defender’s consideration of the attacker’s strategic response to itself: if the defender exerts more effort, the attacker would also respond with higher effort, which in turn induces the defender to exert even more. This process tends to boost the defender’s effort level and therefore |$\frac{1}{1-b_ic_i}\gt 1$|. The sign of the overall strategic effect depends on the tradeoff between the positive direct network effect (|$d_{ij}\gt 0$|) and the negative indirect strategic complement effect (|$-b_ic_j\lt 0$|), whichever dominates. The magnitude of the overall strategic effect, however, is affected additionally by the attacker’s response to the defender’s own effort and determined exclusively by the term |$\big |\frac{d_{ij}-b_ic_j}{1-b_ic_i}\big |$|.
The decrease in the autarkic value is reflected in the change of |$q_i$| in Eq. (7) to |$\tilde{q}_i$| in Eq. (9). It indicates the change in the effectiveness of defenders’ efforts on their own utilities and how they internalize this effect into higher perceived marginal costs.
For the remainder of the paper, we shall assume the following: according to Theorem 1, the game always has a unique (interior) SPE.
Condition 1 holds, and |$G^{-1}[\tilde{\mathbf {q}}_d^T,\ \mathbf {q}^T_a]^T\ge 0$|.
Network security: how sequentiality affects players’ behavior
We next leverage Theorem 1 (which characterizes the I-SPE of the interdependent Stackelberg security game) to investigate how the sequentiality affects players’ equilibrium actions and free-riding behaviors under different network topologies, including the strategic complement effect mentioned above. Specifically, the subsection “Interplay between sequentiality and dependence” examines general conditions under which the defenders’ free riding and equilibrium efforts are reduced. The subsection “‘Exposed’ free riders” shows an opposite instance where sequentiality exposes free riders by inducing them to invest more. Then, the subsection “Alpha-centrality: whose effort will go down?” studies the connection between equilibrium effort changes and the alpha-centrality of defenders in the network. The subsection “Exposed free-riders could lead to higher attacker effort” examines the impact of the free-riding behavior among defenders on the attacker’s equilibrium response. Finally, the subsection “Comparing the I-SPE with socially optimal efforts” explores conditions under which an equilibrium profile also maximizes the social welfare.
Interplay between sequentiality and dependence
In this section, we examine how the presence of a strategic second-stage attacker may increase the free-riding patterns among defenders, due to the strategic complement effect (as discussed following Theorem 1), as well the reduced autarkic value in the sequential move game (Lemma 1).
To this end, we begin with a definition of free riding. Recall that due to network effects, each defender experiences the effects from the aggregated efforts consisting of both the defender’s own effort, as well as spillovers from its neighbors’ efforts. We measure individual free riding by the extent of the latter.
The individual free-riding score of a defender |$i\in \mathcal {D}$| under the defenders’ security effort profile |$\mathbf {x}_d$| is defined as |$s_i:=\sum _{j\in \mathcal {D}\backslash \lbrace i\rbrace }d_{ij}x_j$|—the spillover from efforts made by its neighbors.
We say a defender i is a free rider (or, is supported) if |$s_i \gt 0$|, and is a supporter if |$s_i \le 0$|. Note, in particular, that |$s_i$| can take on negative values when there are strategic complement effects in the network.
Note that the above definition is local to each defender—hence the term “individual.” This is different from a system/efficiency perspective of free riding, where players’ efforts are compared with the socially optimal effort profile. Free riding in that sense is a measure of the defenders’ insufficient efforts relative to the efficient outcome. We will compare the individual free-riding score and system efficiency metrics in Section “Comparing the I-SPE with socially optimal efforts,” and discuss alternative definitions in the section “Discussions.”
We now compare the individual free-riding score between sequential and simultaneous-move games. According to Theorem 1, the unique I-SPE of the sequential game is given by
We aim to contrast this with the alternative simultaneous-move scenario, where all players (all the defenders and the attackers) move simultaneously with the same set of game parameters. Then, assuming |$G^{-1}[\mathbf {q}_d^T,\mathbf {q}_a^T]^T\ge 0$|, there exists a unique (interior) NE given by Eq. (10) with |$\tilde{\mathbf {q}}_d$| replaced by |$\mathbf {q}_d$|. We will denote these, respectively, as |$\mathbf {x}_d^{NE}$| and |$\mathbf {x}_a^{NE}$|. The I-SPE and NE profiles for all players are denoted, respectively, as |$\mathbf {x}^{SPE}$| and |$\mathbf {x}^{NE}$|.
Let |$\mathbf {s}^{SPE}$| be the individual free-riding vector with the I-SPE profile |$\mathbf {x}^{SPE}$| defined by Definition 4, and |${\mathbf {s}}^{NE}$| with the I-NE profile |$\mathbf {x}^{NE}$|. We are interested in the difference |$\Delta \mathbf {s}:=\mathbf {s}^{SPE}-{\mathbf {s}}^{NE}$|, the increment in the individual free-riding score (the amount of benefits received from the neighbors) induced by sequentiality. If |$\Delta s_i$| is positive, then defender i’s individual free riding is amplified (more benefits from neighbors) in the sequential setting; otherwise, it is reduced (less benefits from neighbors).
Let A be a non-negative matrix (i.e., the defenders are strategic substitutes to each other), with its edge weights satisfying |$d_{ij}\le \sum \limits _{k,l\in \mathcal {A}}b_{ik}\big [A^{-1}\big ]_{kl}c_{lj}$| for every |$i,j\in \mathcal {D}$| (i.e., the direct network effect is smaller than the sum of indirect strategic complement effects). Then, compared to the simultaneous-move version, defenders in the sequential game
invest (weakly) less, i.e., |$\mathbf {x}_d^{SPE}\le \mathbf {x}_d^{NE}$|,
have (weakly) lower individual free-riding scores, i.e., |$\mathbf {s}^{SPE}\le {\mathbf {s}}^{NE}$|, and
enjoy higher utilities.
To show (1), note that |$\Delta \mathbf {x}:=\mathbf {x}_d^{SPE}-\mathbf {x}_d^{NE}=(D- BA^{-1}C)^{-1}(\tilde{\mathbf {q}}_d-\mathbf {q}_d)$|. Under the provided conditions, |$D-BA^{-1}C$| is a Z-matrix, which is also a nonsingular M-matrix [31] whose inverse is a non-negative matrix. Thus, given |$\tilde{\mathbf {q}}_d-\mathbf {q}_d\le 0$| as shown in Lemma 1, we have |$\Delta \mathbf {x}\le 0$|. To show (2), note that the drop in individual free-riding scores is given by |$\Delta \mathbf {s}=(D-I)(\mathbf {x}_d^{SPE}-\mathbf {x}_d^{NE})=(D-I)(D- BA^{-1}C)^{-1}(\tilde{\mathbf {q}}_d-\mathbf {q}_d)$|. Here, |$D-I\ge 0$| since D is assumed to be a non-negative matrix. Thus, since |$\Delta \mathbf {x}\le 0$| by (1), we will have |$\Delta \mathbf {s}\le 0$|.
Notice that both |$K^{-1}$| and |$(D-BA^{-1}C)^{-1}$| are non-negative matrices. Given |$\mathbf {q}_d-\tilde{\mathbf {q}}_d\ge 0$| by Lemma 1, it suffices to show that |$K-D+BA^{-1}C\ge 0$|, which readily follows from the edge weight condition in the proposition statement.
Proposition 1 shows an interesting phenomenon where the strategic substitute network with small dependencies induces lower efforts in sequential games but also less free riding. In fact, the reduced game consists of no positive dependencies, that is, no free riding at all! This is because the strategic complement effect of the attacker turns off-diagonal values of the Schur complement of D in G from non-negative to non-positive. This is exactly the “turning-allies-into-adversaries” situation mentioned earlier.
In this situation, every defender invests less in the sequential game compared to the simultaneous-move counterpart.
This results from the combination of three factors: the effect of reduced autarkic value for both the defender and its neighbors, and the strategic complement effect. To see this, consider a free-riding defender—the supported, who depends on the effort of another defender—the supporter. If the supporter’s sequential effort drops due to the decrease in its autarkic value, the supported receives less external efforts and now has to invest more by itself to compensate for it. To make matters worse, the strategic complement effect makes the supported benefits even less on every unit of the supporter’s effort. Therefore, the actual change in any defender’s equilibrium effort depends on the balance among these three factors. The conditions in Proposition 1 limit the defenders’ original reliance on free riding (on other defenders) such that the effect of reduced autarkic value dominates, leading to lower effort by all defenders in the sequential setting. Conversely, if a defender’s sequential effort increases, it indicates that the external effects (reduced neighbors’ autarkic values and strategic complement effect) dominates, which may help identify heavy free riders, as will be presented in the subsection “‘Exposed’ free riders”.
Interestingly, Proposition 1 indicates that the sequential nature of the game can induce lower effort by the defenders, and yet higher utilities for all of them. This implies that defenders are able to exploit the attackers to their own advantage, even though they are unable to free ride on each other at the same time. The former is a common yet important observation in most sequential economic games [14,22,23], where the defenders’ advantage arises as they no longer face the “threat of strategic uncertainty” posed by the attackers. Consider, for instance, the single-defender and single-attacker case, whereby the defender’s utility in an SPE is no lower than that in an NE as the former comes from a larger set that includes the latter. In this case, the defender’s equilibrium utility in SPE is always higher than that in NE.
“Exposed” free riders
The subsection “Interplay between sequentiality and dependence” identifies the combined effect of reduced autarkic values and strategic complement effect, and in particular, conditions under which all defenders invest less despite less individual free riding at the same time. We now look at instances of the game where (some) defenders’ efforts increase as a result of their diminished ability to free ride on other defenders in a sequential game. We say the change from simultaneity to sequentiality exposes these free riders; the following example illustrates this phenomenon.
In this example, we illustrate a situation where free riders (those “supported” by other defenders’ efforts in the simultaneous-move game) are exposed by the sequential setting. We will see that such defenders invest more in the SPE than the corresponding NE due to losing support from other defenders who invest less in the sequential game. Let there be two defenders |$\mathcal {D}=\lbrace 1,2\rbrace$| and one attacker |$\mathcal {A}=\lbrace 3\rbrace$|.
Let the game matrix be such that |$D=\left[ {_{d_{21}}^{\ 1}}\quad {_{\ \ \,1}^{1+d_{12}}} \right]$|, |$B=[-b, -b]^T$|, |$C=[-b, -b]$|, and |$A=1$|. Assume |$d_{12},d_{21},b\in (0,1)$| and the game matrix satisfy Condition 12 and Assumption 2 with suitable autarkic values. The connection in D indicates that defender 1 marginally benefits from defender 2’s effort more than its own effort, but not the other way round. Thus, defender 1 is a heavy free rider. For a real-world example, this network could model the dependence relationship between a small software company and another where the former’s services are primarily based on the latter’s provision of digital infrastructures, such as cloud, client management, email system, etc. The small company may have limited ability to invest in its own security and its peer’s effort is more efficient. In an extreme case of such “single-direction” supply chain, |$d_{21}$| approaches zero, and thus |$d_{12}$| can take values even larger than 1 without violating Condition 1.
If defender 1 and 2 have similar benefit functions and unit costs, then |$\Delta q_1\approx \Delta q_2$|. It directly follows that defender 1 invests more in the sequential game, while defender 2 invests less (notice that |$\Delta q_i=\tilde{q}_i-q_i\le 0$|). Thus, we say defender 1 is exposed in the sequential game. For the extreme case described in the above paragraph, defender 2 is much larger and defender 1 is a consumer of defender 2’s infrastructure services. If we assume defender 2’s marginal benefit is smaller than defender 1 (due to larger systems to protect), then according to Fig. 3, we expect |$|\Delta q_2| \gt |\Delta q_1|$|, which also leads to the same observation.
Notice that the above two equations analytically depict the three effects on the change of security efforts discussed in the section “Interplay between sequentiality and dependence”. Take defender 1 as an example. Its own reduction in autarkic value is captured by the term |$(1-b^2)\Delta q_1$|; the strategic complement effect is represented by the term |$-(1-b^2)\Delta q_2$|; and the direct network effect combined with the neighbor’s reduced autarkic value effect is represented by the last term |$-d_{12}\Delta q_2$|. The same applies to defender 2’s change of effort.
We conclude the above example with the following observation: whoever increases their effort will be worse off in the sequential version of the game. Let |$u_i$| (resp. |$\tilde{u}_i$|) and |$x_i$| (resp. |$\tilde{x}_i$|) be the I-NE (resp. I-SPE) utility and effort of defender i. Then, we have
where the first inequality comes from the definition of NE and that |$d_{ii}=1$| and the second inequality comes from |$\tilde{x}_i\ge x_i$| (higher sequential efforts) and |$\tilde{q_i}\le q_i$| (from Lemma 1). This observation implies that heavy free riders would have a preference for simultaneous-move games.
Alpha-centrality: whose effort will go down?
We now present a graph-theoretical method for identifying which defenders will tend to decrease or increase their efforts in the sequential game. Equation (10) suggests the following connection between such defenders and the alpha-centrality measure proposed by Bonacich and Lloyd [33]. Alpha-centrality is a centrality measure tailored for asymmetric matrices. Given parameters |$\alpha$|, |$\mathbf {v}$|, and a graph with adjacency matrix |$G$|, the alpha-centrality is defined as
where |$\alpha$| characterizes the strength of the transfer of “endogenous” status to vertices due to network connections with other vertices with high status, while |$\mathbf {v}$| is interpreted as some “exogenous” status characteristic that can be different among vertices.
Define the matrix |$K:=D-I-BA^{-1}C$| as the adjacency matrix of the defenders’ network subtracting the term representing the strategic complement effect. Define the vector of exogenous status as |$\Delta \mathbf {q}_d:= \mathbf {q}_d - \tilde{\mathbf {q}}_d\ge 0$|. Then, the effort of defenders with higher alpha-centrality |$c_\alpha (K,-1,\Delta \mathbf {q}_d)$| decreases more in the sequential game compared to the simultaneous-move game.
Subtracting |$\mathbf {x}_d^{SPE}$| from |$\mathbf {x}_d^{NE}$|, we obtain |$(D- BA^{-1}C)^{-1}\Delta \mathbf {q}_d$|, which is exactly the alpha-centrality with |$\alpha = -1$| and |$\mathbf {v} = \Delta \mathbf {q}_d$|.
Note that the phrase “decreases more” only suggests the direction of change in equilibrium efforts; it does not exclude the possibility that defenders may increase their sequential efforts, in which case the defender would have a negative alpha-centrality. A larger magnitude of such centrality would then indicate that the defender’s effort increases more than others.
Proposition 2 provides several important insights on how defenders can exploit the sequential nature of the game. First, we note that an alpha-centrality with transfer strength |$\alpha =-1$| induces an alternating sign effect as the influence of one node propagates along any path in the network [5]. For example, let |$i_0,i_1,\dots ,i_k$| be a path of length k in the network, with the associated edge weights |$g_{i_0i_1},g_{i_1i_2},\dots ,g_{i_{k-1}i_k}$|. Then, the effect of |$i_k$|’s exogenous status on |$i_0$|’s effort along this path is given by |$(-1)^k\Delta q_{i_k}\prod _{l=1}^kg_{i_{l-1}i_l}$|.3 If the path length is even, the influence of |$i_k$| on |$i_0$| along this path has the same sign as the product of the edge weights along the path, i.e., |$\prod _{l=1}^kg_{i_{l-1}i_l}$|; the effect is the opposite otherwise. This observation suggests two fundamental properties of the network which characterize the influence between any two, possibly non-neighboring, agents: the product of the edge weights along the path connecting the agents, as well as the length of the path. The influence of one agent on the other is, therefore, the combined effect of all paths from the former to the latter; the exhibited effort reduction for every agent can be viewed as a combined effect of (besides the exogenous status |$\Delta \mathbf {q}_d$|) such influence of all other agents.
Exposed free-riders could lead to higher attacker effort
In this subsection, we turn to study the change of the attackers’ efforts. The second in Eq. (10) can be expanded using the push-through identity [32] into
which implies that |$\mathbf {x}_d^{NE}-\mathbf {x}_d^{SPE}\ge 0\Rightarrow \mathbf {x}_a^{NE}-\mathbf {x}_a^{SPE}\ge 0$| (where |$\mathbf {x}_a^{NE}$| is obtained by replacing |$\tilde{\mathbf {q}}_d$| with |$\mathbf {q}_d$| as before).
That is, if all defenders’ efforts drop in the sequential game (as happens, e.g., under the conditions of Proposition 1), then all the attackers’ efforts will drop as well. Conversely, if the attackers exert more efforts in a sequential game instance, at least one defender must have increased its sequential effort. By the insights from subsection “‘Exposed’ free riders”, a defender who increases its effort in a sequential game is likely to be a heavy free rider in the simultaneous-move game. The following example elaborates on the relationship between the defenders’ free-riding behavior and the change of the attackers sequential effort.
In this example, we present two instances of the security game where the attacker’s sequential action increases in one and decreases in the other, compared to the simultaneous-move counterparts. We conclude from the example that the attacker may exert higher effort when there is more severe free riding among the defenders. Without loss of generality, we assume there is only one attacker in the game, i.e., |$A=1$|. Denote |$B=\mathbf {b}$| and |$C=\mathbf {c}^T$| for |$\mathbf {b}$| and |$\mathbf {c}$| being nonpositive vectors.
Thus, |$x_a^{NE}-x_a^{SPE} = \big (1+\frac{\mathbf {c}^TD^{-1}\mathbf {b}}{1- \mathbf {c}^TD^{-1}\mathbf {b}}\big )(-\mathbf {c})^TD^{-1}\Delta \mathbf {q}_d$|, where |$\Delta \mathbf {q}_d$| is the same vector of exogenous status in Proposition 2. Notice the term |$1+\frac{\mathbf {c}^TD^{-1}\mathbf {b}}{1- \mathbf {c}^TD^{-1}\mathbf {b}}$| is always positive, and therefore the change in the attacker’s effort only depends on the value of |$(-\mathbf {c})^TD^{-1}\Delta \mathbf {q}_d$|.
If the defenders are independent, i.e., |$A=I$|, then |$(-\mathbf {c})^TD^{-1}\Delta \mathbf {q}_d=(-\mathbf {c})^T\Delta \mathbf {q}_d\ge 0$|. Thus, the attacker would exert less effort in the sequential game. If, on the contrary, we choose the network matrix to have a one-way dependency, i.e., |$D=\left[ {_{{\ 0}}^{\ 1}}\quad {_{\,1}^{{\alpha}}} \right]$|, the attacker exerts strictly higher effort in the sequential game if |$(-\mathbf {c})^TD^{-1}\Delta \mathbf {q}_d = -c_1\Delta q_1 + (-c_2-\alpha c_1) \Delta q_2\lt 0$|. Thus, a sufficient condition for the attacker to exert higher effort in the sequential game is |$\alpha \gt \frac{\Delta q_1}{\Delta q_2}+\frac{c_2}{c_1}$|, providing |$\Delta q_2$| and |$c_1$| are nonzero.
Note that |$\frac{\Delta q_1}{\Delta q_2} + \frac{c_2}{c_1}$| is strictly positive. Thus, only positive dependency among defenders can induce higher attacker effort, and the more positive this dependency is, the more effort the attacker would exert. Recall that, as we have discussed in Proposition 2, a higher value of |$\alpha$| may lead to higher security effort of defender |$1$|; this is the defender that free rides on defender 2 in the simultaneous-move game, but is exposed in the sequential setting. Comparing these two findings, we conclude that the attacker is led to increase its effort in the sequential setting in response to the increase in effort of the “exposed” free-riding defender 1.
Comparing the I-SPE with socially optimal efforts
Lastly, we investigate the impact of sequentiality and the network structure on the equilibrium efforts compared to the socially optimal outcome. We show that for games of pure substitutes in which the interdependency between defenders is limited, the I-SPE equilibrium of the sequential-move game has both higher efforts and also more individual free riding than the socially optimal effort profile.
We begin by defining the defenders’ socially optimal effort profile for sequential-move games.
where |$x_k^{*}(\mathbf {x}_d)$| is attacker k’s equilibrium response to the defenders’ choice |$\mathbf {x}_d$|, as defined in Eq. (3).
Note that this takes into account the defenders’ ability to influence the attackers’ decision.
The following proposition contrasts the I-SPE profile with the socially optimal efforts in games satisfying the conditions of Proposition 1.
Assume the conditions in Proposition 1 hold. Let |$\mathbf {x}_d^{*}$| be the (sequential) socially optimal effort profile, and |$\mathbf {x}_d^{SPE}$| be the I-SPE profile among defenders. Denote |$\mathbf {s}^{*}$| (resp. |$\mathbf {s}$|) as the individual free-riding scores as given in Definition 4, under the effort profile |$\mathbf {x}_d^{*}$| (resp. |$\mathbf {x}_d^{SPE}$|). Then, |$\mathbf {x}^{*}_d\le \mathbf {x}^{SPE}_d$| and |$\mathbf {s}^{*}\le \mathbf {s}$|.
where |$\tilde{S}-S$| is a non-negative matrix with zero diagonals. Thus, |$\mathbf {x}^{*}_d\le \mathbf {x}^{SPE}_d$| and |$\mathbf {s}^{*}\le \mathbf {s}$| follows readily from the definition of the individual free-riding score.
This suggests that in networks with limited strategic substitute effects between the defenders, the sequential game’s equilibrium efforts are higher than the social optimum, indicating that all defenders are over-investing. Interestingly, this is similar to classical games of strategic complements, where the lack of efficiency stems from the adversarial (competitive) relationship that induces every agent to over-invest. In other words, this proposition again reveals the strategic complement effect due to the sequential nature of the game: defenders’ who had strategic substitute dependencies (were allies) have turned into adversaries (and over-invest compared to the socially optimal outcome).
Discussions
Our model provides a general framework for analyzing sequential network games and allows us to make a number of interesting observations, especially in a security game context and in comparison with a simultaneous-move game. In particular, the “Equilibrium analysis” section discussed conditions under which a sequential game results in less free riding than a simultaneous-move game. This type of comparison (first presented by Korzhyk et al. [20] in a classical security context, such as airport security and coastline patrol) is meaningful as in practice the defender-attacker strategic interaction is likely not a simultaneous move.
There are limitations to this model, which suggest possible directions for future research. First, under the present model, the attacker exerts a single (attack) effort, which is felt by all (connected) defenders, modulo the connection strength. Since the connection strength is taken as a fixed game parameter, this model does not adequately capture the cases where attacks on individual defenders are highly targeted, often as a function of the defender’s effort. This would require a different model. One possibility is to allow the attacker to choose optimal edge weights B and C as part of its strategic decisions.
Secondly, all our analysis is based on the assumption that an interior SPE exists. This means that our results do not directly apply to cases where some players may exert zero effort (inactive) or other boundary actions not captured by interior solutions. The former includes the total effort dependency model [14] where the aggregated effort is simply the sum of all other defenders. The latter is also important as effort levels in reality must ultimately be bounded due to budget constraints. We conjecture that, as long as the attacker remains interior, most of our insights should still hold because if we eliminate rows and columns of G corresponding to inactive defenders, we obtain exactly the same problem with a smaller graph. For instance, Varian [14] showed that at the NE of the simultaneous-move game, only two agents exert positive effort, these being the most cost-efficient agent from the defenders and attackers group, respectively, an outcome referred to as the “battle between the champions”. In this case, the total effort model, where |$d_{ij}=1$|, |$\forall i,j\in \mathcal {D}$|, does not satisfy the P-matrix condition. However, since only two agents exert nonzero effort in the equilibrium, we can eliminate all other agents and recover an equivalent two-palyer game between the two positive-action agents, where the network does satisfy the P-matrix condition, and the derived game possesses the same set of equilibrium as the original one. In this sense, our results can be viewed as a generalization of the total effort model.
The challenge arises when there are inactive attackers, e.g., when the condition on A in Theorem 1 does not hold. In this case, the defenders’ utility functions in the reduced game may not be concave, as we demonstrated in Example 1, and our results in Section 5 may not generalize.
One possible avenue is to formulate these problems as equilibrium problems with equilibrium constraints [34] and solve them numerically using algorithms for quasi-variational inequality [35,36], or iterated best-response dynamics with diagonalization [34]. A more comprehensive investigation of these methods is a direction of future work.
In terms of metrics on free riding, Miura-Ko et al. [13] studied a form of free-riding score defined as the proportion of benefits from the neighbors to the total amount of efforts that the defender should exert, but without the presence of attackers. Elliott and Golub [9] propose a measure of free riding based on the ratio of marginal benefit from the player’s neighbors leaving its own effort unchanged to the marginal cost that the player would otherwise bear by investing alone. Definition 4 follows a similar but simpler spirit that tries to capture the amount of effort that a defender takes without incurring a matching cost.
Conclusion
In this paper, we examine a sequential network game model that takes into account interdependency as well as sequential moves in the agents’ strategic reasoning. Similar to general sequential public good games, this model encounters difficulties in the non-concavity and non-differentiability of the leaders’ utility functions in the reduced games. We provide a sufficient condition under which an I-SPE can be solved analytically.
In applying this model to the cybersecurity context, we demonstrate the reduction in autarkic value and the strategic complement effect resulting from the presence of the following strategic attackers. We also identify network structures where defenders exert less effort and free ride less in the sequential game compared to its simultaneous counterpart. However, we show that, in general, severe free riders may have a diminished ability to free ride in a sequential game and are forced to exert more effort. We also show that the relative decrease of security efforts in the sequential game aligns with the notion of alpha-centrality in the reduced network. Lastly, we compare defenders’ effort levels at equilibrium to the social optimal solution.
Acknowledgement
This work is supported by the U.S. National Science Foundation under grants CNS-2012001 and CCF-2144283, and by the Army Research Office under contract W911NF1810208.
Author contributions
Ziyuan Huang (Conceptualization [Equal], Formal analysis [Lead], Investigation [Lead], Methodology [Lead], Project administration [Equal], Validation [Equal], Visualization [Lead], Writing - original draft [Lead], Writing - review and editing [Equal]), Parinaz Naghizadeh (Conceptualization [Equal], Formal analysis [Supporting], Funding acquisition [Equal], Investigation[Supporting], Methodology [Supporting], Project administration [Equal], Supervision [Equal], Validation [Equal], Writing - original draft [Equal], Writing - review and editing [Equal]), and Mingyan Liu (Conceptualization [Lead], Formal analysis [Supporting], Funding acquisition [Lead], Investigation [Supporting], Methodology [Supporting], Project administration [Lead], Resources [Lead], Supervision [Lead], Validation [Equal], Visualization [Supporting], Writing - original draft [Equal], Writing - review and editing [Equal]).
Data availability
No new data were generated or analysed in support of this research.
Footnotes
We are gratefully for the anonymous reviewer for suggesting this example.
The condition can be satisfied as long as |$d_{21}\lt \frac{1}{1+d_{12}}$| and |$|b|\lt \frac{1-d_{21}(1+d_{12})}{3+d_{12}-d_{21}}$|.
