🛡️

Airport police cannot cover every terminal at once. Guard the obvious target every day and an attacker who watches simply hits the one you left open. The fix is a randomized patrol, and the schedules at LAX and for federal air marshals are computed by solving a game.

Security games and multi-agent AI

A defender with too few resources commits first to a patrol; an attacker observes the coverage policy, then chooses a target. This is a Stackelberg security game. The lesson’s zero-sum example uses a minimax mix. Real security systems and poker agents require different models and different solution methods.

From earlier lessons

Two quick ones before we start.

In a Stackelberg security game, the defender commits to a patrol...

A perfectly predictable patrol is something a surveilling attacker can...

Predict, then play

Allocate one patrol unit as coverage probabilities across two targets. First find the minimax mix against a perfect best response. Then switch to the noisy QRE attacker and change its response precision. Watch how the behavioral assumption changes both attack probabilities and your best coverage.

Why did that happen?

Take a guess, then reveal the reason

Because the attacker moves second, after watching, any deterministic patrol is a gift: the attacker simply strikes wherever you are not. Committing to a random schedule denies that. The optimal coverage makes the attacker indifferent across targets, so there is no soft spot to aim at, and this minimizes the worst-case loss. Guarding only the top target seems prudent but is the most exploitable choice, since it leaves a lesser but undefended target for a guaranteed hit. The defender commits first precisely to shape the attacker’s best response. Real deployments add a twist: attackers are not perfectly rational, so a quantal-response (QRE) model of a noisy attacker often fits better and changes the optimal mix.

The real deployments

Definition, Stackelberg security games (Tambe)

Milind Tambe’s group developed deployed systems including ARMOR for LAX, IRIS for federal air marshals, and PROTECT for Coast Guard patrols. These systems model a defender committing to randomized coverage before an attacker responds. Some behavioral security models use quantal response rather than a perfect best response. Poker is a separate application: counterfactual regret minimization (CFR) is an iterative regret-minimization algorithm for large extensive-form imperfect-information games. Low regret can approximate Nash play in two-player zero-sum settings. QRE and CFR are not the same solution concept or algorithm.

Two targets worth $10$ and $5$ , one patrol unit split as coverage $c_1 + c_2 = 1$ . Equalize the attacker’s payoff across targets: an attack on target $i$ succeeds only when uncovered, so set $(1 - c_1)\cdot 10 = (1 - c_2)\cdot 5$ . With $c_2 = 1 - c_1$ this gives $c_1 = 2/3$ and $c_2 = 1/3$ , and the expected loss is $(1 - 2/3)\cdot 10 = 10/3 \approx 3.33$ . Compare “always guard the $10$ ”: the attacker hits the undefended $5$ for a certain loss of $5 > 3.33$ . Randomizing to equalize the attacker’s options is strictly better.

For a noisy attacker, let $a_i = (1-c_i)v_i$ be the payoff from attacking target $i$ . A logit QRE assigns attack probability

p_i = \frac{e^{\lambda a_i}}{\sum_j e^{\lambda a_j}},

where response precision $\lambda=0$ means random choice and a larger $\lambda$ puts more weight on the better target. The defender now minimizes $\sum_i p_i(1-c_i)v_i$ . The best coverage need not equalize the two target payoffs because a noisy attacker sometimes chooses the worse one. Behavioral security research uses models of this kind to tune coverage to observed responses.

Work it out

Why randomize, and by how much

Targets worth $10$ and $5$ , one unit of patrol to allocate as probabilities. Try the intuitive rule first: always cover the $10$ . Then the $5$ is never guarded, and a surveilling attacker takes it for a sure loss of $5$ . That is worse than it looks, because the whole point of the $10$ -guard was to protect value, yet you have handed over the $5$ with certainty.

Now equalize. Cover the $10$ with probability $c_1$ and the $5$ with $c_2 = 1 - c_1$ , and choose $c_1$ so the attacker gains equally either way: $(1 - c_1)\cdot 10 = (1 - c_2)\cdot 5$ . Solving gives $c_1 = 2/3$ , $c_2 = 1/3$ , and either attack now yields the attacker an expected $10/3 \approx 3.33$ , which is the defender’s expected loss. Since $3.33 < 5$ , randomization beats the deterministic guard, and because the attacker is indifferent, there is no weak point to exploit. This is the logic behind LAX checkpoints and air-marshal scheduling, and with a QRE attacker the coverage is retuned to the attacker’s actual, noisy responses.

Key idea

When a defender commits first and an attacker observes coverage, randomization removes a guaranteed soft target. In this zero-sum example, equalizing the attacker’s options gives the minimax mix. Behavioral security models may use QRE; poker agents may use CFR. Those are distinct tools.

Check yourself

Check yourselfapply

With one patrol unit and targets worth 10 and 5, why not just always guard the target worth 10?

Check yourselfanalyse

What coverage minimizes the defender's worst-case loss with targets 10 and 5?

Check yourselfbrings back: quantal response

Why do fielded systems like PROTECT model the attacker with quantal response (QRE) rather than perfect rationality?

Sources

Tambe, M. (2011). Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned. Cambridge University Press.
Shieh, E., An, B., Yang, R., Tambe, M., Baldwin, C., DiRenzo, J., Maule, B., and Meyer, G. (2012). PROTECT: An application of computational game theory for the security of the ports of the United States. Proceedings of the AAAI Conference on Artificial Intelligence, 26(1), 2173-2179.