Interdependent security games in a unidirectional network.

We consider directed tree networks with a single source, where there exists a positive probability of a disruptive event at any node. Such networks model security considerations in pipelines as well as in unidirectional digital networks. If a disruptive event occurs at a certain node, that node and its downstream nodes incur economic losses. Users thus have an incentive to invest in upstream locations as well as their own sites to reduce the probability of a disruptive event. The initial model we develop to reduce the expected investment plus disruption costs is a multiplicative model for which closed-form solutions cannot be obtained in general. We overcome this problem with an additive model that we show closely approximates the initial formulation. This model reduces the security problem to a public goods setting where we minimize the total expected cost at each node. The users then need to share these costs in an equitable fashion, which gives rise to a set of cooperative games. For the case where disutilities to all users are identical, the Shapley value can be computed efficiently, along the lines of an Airport Game. We also treat the case where risk reduction and disutility vary across the network. Finally, we prove that the cooperative game is concave in this general case, which guarantees that the core of the game is nonempty and that the Shapley value is an element of the core.