Stackelberg security game models and associated computational tools have seen deployment in a number of high-consequence security settings, such as LAX canine patrols and Federal Air Marshal Service. These models focus on isolated systems with only one defender, despite being part of a more complex system with multiple players. Furthermore, many real systems such as transportation networks and the power grid exhibit interdependencies between targets and, consequently, between decision makers jointly charged with protecting them. To understand such multidefender strategic interactions present in security, we investigate game theoretic models of security games with multiple defenders. Unlike most prior analysis, we focus on the situations in which each defender must protect multiple targets, so that even a single defender's best response decision is, in general, highly non-trivial. We start with an analytical investigation of multidefender security games with independent targets, offering an equilibrium and price-of-anarchy analysis of three models with increasing generality. In all models, we find that defenders have the incentive to over-protect targets, at times significantly. Additionally, in the simpler models, we find that the price of anarchy is unbounded, linearly increasing both in the number of defenders and the number of targets per defender. Considering interdependencies among targets, we develop a novel mixed-integer linear programming formulation to compute a defender's best response, and make use of this formulation in approximating Nash equilibria of the game. We apply this approach towards computational strategic analysis of several models of networks representing interdependencies, including real-world power networks. Our analysis shows how network structure and the probability of failure spread determine the propensity of defenders to over- or under-invest in security.
Another somewhat related line of work considers the problem of coordination and teamwork among multiple defenders in a purely cooperative setting @cite_3 @cite_2 . This work, however, is entirely unlike ours: in particular, our primary focus is on the impact of among the defenders with different (though certainly related) motivations, rather than coordination issues and teamwork. While often effective coordination among multiple defenders can be achieved, just as often (if not predominantly) decentralization of decision making processes and resources inherently give rise to distinct, and often conflicting, incentives among defenders.
@cite_3 @cite_2
2150744284 1818018820
We examine security domains where defenders choose their security levels in the face of a possible attack by an adversary who attempts to destroy as many of them as possible. Though the attacker only selects one target, and only has a certain probability of destroying it depending on that defender's security level, a successful attack may infect other defenders. By choosing a higher security level the defenders increase their probability of survival, but incur a higher cost of security. We assume that the adversary observes the security levels chosen by the defenders before selecting whom to attack. We show that under this assumption the defenders over-protect themselves, exhausting all their surplus, so optimal policy requires taxing security, as opposed to the subsidies recommended by alternative models for contagious attacks which do not take into account the attacker's ability to observe the defenders' choices. We study security games with multiple defenders. To achieve maximum security, defenders must perfectly synchronize their randomized allocations of resources. However, in real-life scenarios (such as protection of the port of Boston) this is not the case. Our goal is to quantify the loss incurred by miscoordination between defenders, both theoretically and empirically. We introduce two notions that capture this loss under different assumptions: the price of miscoordination, and the price of sequential commitment. Generally speaking, our theoretical bounds indicate that the loss may be extremely high in the worst case, while our simulations establish a smaller yet significant loss in practice.