Unpredictable Patrol Routes

Stackelberg Security Game · Randomized Patrols

Design patrol paths that aliens cannot predict. The defender commits to a randomized patrol strategy; the attacker observes the probabilities and chooses their best target. The defender must maximize their guaranteed worst-case utility — a Stackelberg game solved via linear programming.

The Scenario

Randomized Defense

A perimeter has 5 vulnerable sectors (gates, rooftop access). You have m = 2 patrol units. If a patrol covers a sector when an alien attacks it, the defender gains utility U^d_c; if not, the defender suffers loss U^d_u. The attacker observes your patrol probabilities (not actual positions) and picks the target maximizing their payoff. You must choose coverage probabilities c_t that maximize your guaranteed worst-case utility. This is a Stackelberg Security Game — deployed operationally in ARMOR (LAX airport) and IRIS (US Federal Air Marshals).

Defense Domain	OR Element	Symbol	Example
Perimeter sector	Target	t ∈ T	Gate-South
Patrol unit	Coverage resource	m = 2	2 guards
Patrol probability	Coverage	c_t ∈ [0,1]	0.45
Reward if caught	Defender covered payoff	U^d_c	4
Loss if missed	Defender uncovered payoff	U^d_u	-15
Alien penalty	Attacker covered payoff	U^a_c	-6
Alien gain	Attacker uncovered payoff	U^a_u	18

Compact Coverage LP (Tambe 2011, avoids route enumeration): MAXIMIZE d // guaranteed minimum defender utility subject to: d ≤ c_t·U^d_c(t) + (1-c_t)·U^d_u(t) ∀ t ∈ T // worst case Σ_t c_t ≤ m // total coverage = m patrols 0 ≤ c_t ≤ 1 ∀ t ∈ T // Attacker best response (rational adversary): // t* = argmax_t [ c_t · Ua_c(t) + (1-c_t) · Ua_u(t) ] // At SSE: attacker is indifferent among targets they might attack // Real deployments (ARMOR, IRIS) use column generation for route constraints

Real-World Deployments

ARMOR (2007): Deployed at Los Angeles International Airport to randomize checkpoint deployments across terminals. IRIS (2009): Used by the US Federal Air Marshal Service to schedule air marshals on flights. Both systems solve Stackelberg security games to generate unpredictable but strategically optimal schedules. The key insight: pure randomness (uniform coverage) is suboptimal because high-value targets should receive more coverage than low-value ones.

Interactive Solver

Coverage Optimizer

★★☆ Heuristic (LP-based)

5 Targets · m=2 Patrol Units

Payoff structure: higher |U^d_u| means more loss if uncovered. The LP allocates coverage proportional to vulnerability.

References

Published Tambe, M. (2011). Security Games: Applying Game Theory to Counterterrorism. Cambridge University Press. — Comprehensive treatment of Stackelberg security games and deployed systems.

Operational Pita, J., Jain, M., Marecki, J., et al. (2008). “Deployed ARMOR protection: the application of a game theoretic model for security at LAX.” AAMAS. — First deployed security game system.

Published Paruchuri, P., Pearce, J.P., Marecki, J., et al. (2008). “Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games.” AAMAS. — DOBSS algorithm for computing SSE.

Preparing for First Contact

We do recommend the Hungarian algorithm. It works on any planet.

All Defense Applications GitHub

👽🛸⚠️

Educational Fiction Disclaimer

This is a fictional educational scenario.

All data and parameters are entirely fictional
No military applications intended
The author advocates for peace