Abstract
This research addresses the challenge of coordinating multiple independent defenders in Stackelberg Security Games (SSGs). In scenarios where different agencies or nations protect a shared set of targets, individual strategies often lead to suboptimal outcomes due to externalities and heterogeneous valuations. This paper explores the application of cooperative game theory to identify stable coalition structures. We prove that a stable "grand coalition" always exists and provide a polynomial-time algorithm for its computation, even though the general problem of characterizing all stable structures remains NP-hard.
Introduction
Standard Stackelberg Security Games typically model a single defender allocating resources against a strategic attacker. However, real-world security often involves multiple defenders with varying resources and priorities. This introduces two primary complications:
- Externalities: A defender's protection of one target may displace the attacker toward targets prioritized by others.
- Heterogeneity: Defenders possess different resource capacities and assign different values to the same targets.
Non-cooperative behavior in these settings often results in "over-coverage" of some targets and dangerous gaps in others. This paper investigates whether defenders can form stable coalitions—groups that will not fragment due to individual self-interest—to achieve more efficient security outcomes.
Methodology: The $\alpha$-Core and Tank-Filling
The authors model the interaction as a Non-Transferable Utility (NTU) game with externalities. Stability is defined using the concept of the $\alpha$-core. In this framework, a coalition is stable if no sub-group can deviate to a strategy that guarantees a better outcome for its members, assuming the remaining defenders coordinate to "punish" the deviators (the "revenge" assumption).
A central conceptual tool in this analysis is the Tank-Filling Model. This model visualizes targets as "tanks" with widths determined by the potential payoffs. Coverage resources are treated as "water" poured into these tanks.
In a stable equilibrium, the "water level"—representing the attacker's utility—must be equalized across all targets that are actively attacked. The paper introduces Algorithm 1, a greedy polynomial-time approach that distributes defender resources to reach a "maximal level coverage," ensuring the stability of the grand coalition.
Key Insights and Results
The research yields several critical findings regarding the feasibility of cooperation:
- Existence of the Grand Coalition: The authors prove that the "grand coalition" (where all defenders cooperate) is always a member of the $0^+$-core. This ensures that a mutually beneficial, stable agreement is always theoretically possible.
- The Role of "Revenge": Stability is maintained by the credible threat that if a subgroup deviates, the remaining defenders will act to minimize the deviators' utility.
- Computational Complexity: While the grand coalition's strategy can be found in polynomial time (P), determining if any other stable coalition structure exists is NP-hard, even with as few as two defenders.
- Efficiency: Solutions within the core are shown to be weakly Pareto efficient, meaning no alternative arrangement can improve the utility of every defender simultaneously.
Discussion and Future Directions
While the paper establishes a strong theoretical foundation for multi-defender cooperation, several avenues for future research remain. The current model assumes "revenge" strategies are always executed, which may not be credible if the punishers also harm themselves. Future work could explore the $\gamma$-core, where defenders act residually rather than punitively. Additionally, incorporating target dependencies (where protecting one target indirectly benefits another) and accounting for the communication costs of negotiation would enhance the model's real-world applicability.
Summary updated