Equilibrium Analysis of Multi-Defender Security Games

Jian Lou, Yevgeniy Vorobeychik

Abstract

Traditional security game models often focus on a single defender protecting multiple targets against a strategic attacker. This paper extends this framework to multi-defender environments where independent agencies manage distinct asset subsets. We analyze the resulting non-cooperative dynamics, focusing on the "negative externalities" created when one defender's security investments shift risk to others. While simpler models predict an unbounded Price of Anarchy (PoA) that scales linearly with the number of defenders, we demonstrate that in more generalized utility models, the PoA is bounded and converges to a constant, suggesting that decentralized security is more efficient than previously theorized.

1. Introduction

Security resource allocation is frequently modeled as a Stackelberg Security Game (SSG). While effective for single-agency scenarios like the TSA, these models fail to capture the complexities of multi-defender environments common in cybersecurity and critical infrastructure protection. In these settings, defenders act independently, often leading to a "race to the top" in security spending. This behavior is driven by negative externalities: as Defender A hardens their targets, the attacker is incentivized to pivot toward the relatively softer targets of Defender B. This paper quantifies the social cost of this lack of coordination using the Price of Anarchy (PoA) metric.

2. Methodology and Models

The study evaluates three distinct mathematical frameworks of increasing complexity:

  1. Baseline Model: Each of $n$ defenders protects exactly one target.
  2. Multi-Target Model: Each of $n$ defenders manages $k$ targets.
  3. General Model: A flexible framework where utilities for various attack outcomes (protected vs. unprotected) and the utility of no attack are treated as arbitrary variables.

The primary solution concept is the Nash Equilibrium. However, because pure Nash equilibria do not always exist in multi-defender Stackelberg settings, the authors also employ $\epsilon$-equilibrium—a state where no player can improve their utility by more than a marginal value $\epsilon$.

3. The Incentive to Over-Protect

A core finding across all models is the systemic incentive for defenders to over-invest in security. Because defenders prioritize minimizing their own losses without accounting for the increased risk shifted to neighbors, they protect targets at levels significantly higher than the social optimum. This uncoordinated "over-protection" is the primary driver of the Price of Anarchy.

4. Analysis of the Price of Anarchy

The research reveals a critical distinction between simplified and generalized models regarding system inefficiency.

4.1 Linear Inefficiency in Simple Models

In the baseline and multi-target models, where the value of a target ($v$) exceeds the cost of protection ($c$), a unique Nash equilibrium often results in 100% protection probability for all targets. In these cases, the PoA scales linearly with the size of the game ($O(n)$ or $O(nk)$).

Figure 1: Price of Anarchy as a function of the number of defenders (n) for various cost-to-value (c/v) ratios in the baseline model.

4.2 Bounded Inefficiency in General Models

The authors argue that the unbounded PoA found in earlier literature is often a consequence of overly restrictive utility assumptions. By introducing a non-zero utility for "not being attacked," the PoA behavior changes dramatically. Instead of growing indefinitely, the PoA converges to a constant as the number of defenders or targets increases.

Figure 3: Approximate Price of Anarchy relative to the number of targets per defender (k), illustrating the leveling off of inefficiency in multi-target scenarios.

5. Conclusion and Future Work

This work provides a more optimistic view of decentralized security than previous models. While negative externalities do lead to over-investment, the resulting social inefficiency is bounded in realistic scenarios. Future research should address the limitations of the current symmetric models by incorporating heterogeneous target values and interdependent risks, where a failure in one defender's domain physically impacts another. Additionally, exploring policy mechanisms like security subsidies or taxes could help align individual incentives with the social optimum.

Summary updated

Abstract

Stackelberg game models of security have received much attention, with a number of approaches for computing Stackelberg equilibria in games with a single defender protecting a collection of targets. In contrast, multi-defender security games have received significantly less attention, particularly when each defender protects more than a single target. We fill this gap by considering a multidefender security game, with a focus on theoretical characterizations of equilibria and the price of anarchy. We present the analysis of three models of increasing generality, two in which each defender protects multiple targets. In all models, we find that the defenders often have the incentive to overprotect the 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. Surprisingly, when we consider a more general model, this results obtains only in a "corner" case in the space of parameters; in most cases, however, the price of anarchy converges to a constant when the number of defenders increases.
BibTeX
@inproceedings{lou2015equilibrium,
  author = {Jian Lou and Yevgeniy Vorobeychik},
  title = {{Equilibrium Analysis of Multi-Defender Security Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure