Introduction
In modern security environments, defenders must effectively allocate a heterogeneous mix of resources to protect critical targets. While traditional Stackelberg Security Games (SSGs) focus on human patrollers ("boots on the ground"), the proliferation of low-cost mobile sensors, such as Unmanned Aerial Vehicles (UAVs), presents new opportunities and challenges. This paper, presented at AAAI-18, introduces Sensor-Empowered security Games (SEG), a formal framework designed to jointly optimize the deployment of human patrollers and mobile sensors while leveraging strategic signaling to deter potential attackers.
The Problem: Sensors as "Half-Resources"
The primary challenge in integrating sensors into security games is that they are essentially "half-resources." Unlike human patrollers, sensors can detect an intrusion but cannot perform an intervention. Their effectiveness is contingent upon the proximity of a human patroller who can respond to a sensor-detected alert.
Furthermore, sensors enable strategic signaling (a form of Bayesian Persuasion). A sensor can emit a signal (e.g., flashing lights or sirens) to indicate an alert. If the defender uses a clever signaling policy, they can "bluff" the attacker into believing a patroller is nearby even when one is not, thereby maximizing deterrence.
The SEG Model and Strategic Signaling
The authors model the environment as a graph where edges represent the "intervention distance"—the maximum range a patroller can cover within the time required to intercept an attack after a sensor alert.
The SEG model categorizes target states into four types: covered by a patroller, uncovered, covered by a sensor with a patroller nearby, or covered by a sensor with no patroller nearby. In the latter two cases, the defender employs a signaling scheme. By sending "Alert" or "Quiet" signals, the defender aims to influence the attacker's beliefs. A successful "Alert" signal must be sufficiently credible to deter a rational attacker, even if it is occasionally a bluff.
Algorithmic Framework: SEGer and TailoredGreedy
Solving the SEG problem is NP-hard. To address this, the authors developed SEGer, a branch-and-price algorithm. SEGer utilizes column generation, where a Master Problem selects the optimal mix of strategies and a Slave Problem (formulated as a Mixed-Integer Linear Program) generates new high-utility strategies.
For large-scale deployments, the authors introduced TailoredGreedy. Although the defender's utility function is not strictly submodular, the researchers identified a submodular "proxy" function. This allows for a polynomial-time approximation with a provable $1/2(1-1/e)$ bound in zero-sum scenarios.
Experimental Results
The framework was evaluated using synthetic covariant games and various graph structures, including Erdős–Rényi random graphs and cycle graphs.
Utility and Signaling Effectiveness
The results demonstrate that the SEG model with signaling consistently outperforms baselines. A key finding is the relationship between payoff correlation and signaling utility. In strictly zero-sum games (correlation -1), signaling offers no advantage because the attacker's and defender's interests are diametrically opposed. However, in general-sum games (correlation approaching 0), strategic signaling becomes a powerful tool for increasing defender utility.
Scalability and Heuristics
The exact SEGer algorithm can handle up to 100 targets within a reasonable timeframe. In contrast, the TailoredGreedy heuristic scales to over 340 targets. Remarkably, TailoredGreedy achieved objective values nearly identical to the exact MILP solver while being approximately six times faster, proving its viability for real-world applications.
Conclusion and Future Work
This research quantifies the value of sensors as force multipliers in security games. By coordinating humans and sensors through strategic signaling, defenders can achieve higher security levels with fewer human resources.
Future research directions include relaxing the assumption of perfect sensor detection to account for false alarms, and integrating dynamic patrol path planning to move beyond static resource allocation.
Summary updated