Decentralized Defence of a (Directed) Network Structure

ABSTRACT

We model the decentralized defence choice of agents connected in a directed graph and exposed to an external threat. The network allows players to receive goods from one or more producers through directed paths. Each agent is endowed with a finite and divisible defence resource that can be allocated to their own security or to that of their peers. The external threat is represented by either a random attack on one of the nodes or by an intelligent attacker who aims to maximize the flow-disruption by seeking to destroy one node. We show that under certain conditions a decentralized defence allocation is efficient when we assume the attacker to be strategic: a centralized allocation of defence resources which minimizes the flow-disruption coincides with a decentralized equilibrium allocation. On the other hand, when we assume a random attack, the decentralized allocation is likely to diverge from the central planner’s allocation.

KEYWORDS:

• Networks
• network defence
• security

JEL CLASSIFICATION:

• C72

Acknowledgments

I thank Arupratan Daripa for his insightful comments that were essential to the development of this paper. I am also grateful to the two anonymous referees, Emanuela Sciubba, Nizar Allouch, Arina Nikandrova, Christian Ghiglino, Todd Sandler, Ron Smith, Francesco Cerigioni, and many seminar participants for helpful comments. All mistakes are mine.

Disclosure statement

No potential conflict of interest was reported by the author.

Notes

1. See Kovenock and Roberson (2010), Bier (2006) and Sandler and Enders (2004) for surveys and the works by Bier, Oliveros, and Samuelson (2007), Lapan and Sandler (1993), Sandler et al. (2003), Keohane and Zeckhauser (2003), Kunreuther and Heal (2003), and Heal and Kunreuther (2004).

2. See Jackson et al. (2008).

3. As we will show in the next sections, a node is more critical if by removing it from the network it has relatively larger impact on the utility of the rest of the nodes.

4. Variations of the same problem have been studied by Varian (2004) and Aspnes, Chang, and Yampolskiy (2006).

5. There are other notable studies about network flow interdiction problems such as Hong (2011), Wood (1993), Washburn and Wood (1995), Reijnierse et al. (1996), Kalai and Zemel (1982), Israeli and Wood (2002). There also exists a vast literature in operations research and computer science about network defence, for instance Alpcan and Başar (2010), Smith (2010), and Zhu and Levinson (2012).

6. This definition of middleman may coincide with the widely studied betweenness centrality. However, this is not necessary. The betweenness centrality is measured by considering the shortest paths between two nodes, if more than one, while a node is a jq-middleman if any path from $j$ to $q$ passes through him. In other words, a jq-middleman would necessarily score a positive betweenness centrality level while a node with positive betweenness centrality score may not be a middleman.

7. To exclude trivial cases, we can assume that any producer has strictly positive out-degree and any non-producer strictly positive in-degree.

8. See Tullock (2001).

9. This may well describe the cases of trade networks, or infrastructure networks for example. Few countries own and export natural resources. The value of belonging to the trade network of a natural resource is linked exclusively to the existence of a trade path from the producer to the final country-consumer.

10. If the set of producers $O$ is singleton, this condition is trivially satisfied.

11. It is enough to assume $p_i>0$ for at least one node $i$ essential to $j$ to be connected to any producer to guarantee $d_{jq}^{\ast }=0$. If there is no such node, sending resources to $q$ would never affect the payoff of $j$, thus we cannot exclude an equilibrium where $d_{jq}^{\ast }>0$.