28. Game Theory & Adversarial Thinking

Level: Expert You'll use this for: reasoning formally about attacker/defender dynamics, adversarial ML, and any system with competing incentives.

Nash equilibrium

A Nash equilibrium is a set of strategies where no player can improve their outcome by unilaterally changing their own strategy, given what everyone else is doing. Classic example — the Prisoner's Dilemma:

Verifying it's an equilibrium, by checking every possible unilateral switch. A cell is a Nash equilibrium only if neither player can do better by changing just their own move, holding the other's move fixed:

Start at (defect, defect) = payoffs (-2, -2).

Would Alice switch to cooperate, if Bob keeps defecting?
  Alice's payoff would become -3 (worse than -2)  -> no, she won't switch.

Would Bob switch to cooperate, if Alice keeps defecting?
  Bob's payoff would become -3 (worse than -2)    -> no, he won't switch.

Neither player benefits from switching alone -> (defect, defect) IS a
Nash equilibrium.

Now check (cooperate, cooperate) = payoffs (-1, -1), the jointly better outcome:
  Would Alice switch to defect, if Bob keeps cooperating?
    Alice's payoff would become 0 (better than -1) -> YES, she'd switch.

Since at least one player benefits from switching, (cooperate, cooperate)
is NOT a Nash equilibrium — it's unstable, even though it's better for both.

Both defecting is the Nash equilibrium (neither benefits from unilaterally switching), even though both cooperating would be better for both of them jointly — the mathematical core of why purely self-interested security investment decisions across organizations (e.g., ISPs not filtering spoofed traffic because it costs them money but benefits everyone else) tend to under-invest relative to the collective optimum. This is literally why some security problems (BGP route hijacking, DDoS amplification via spoofing) persist for decades despite known technical fixes — it's a game-theory/incentive problem, not a technical one.

Zero-sum vs. non-zero-sum framing of security

Classic security thinking often (wrongly) treats attacker/defender as purely zero-sum (attacker's gain = defender's loss). In reality, many security investments are non-zero-sum: raising the attacker's cost (e.g., MFA) can deter an attacker entirely (redirecting them to an easier target) without any actual "loss" transferred — both the specific defender and the broader ecosystem can be better off.

Adversarial ML as a minimax game

Adversarial example generation is literally: find the smallest input perturbation δ that maximizes the model's loss:

δ* = argmax_δ  Loss(model(x + δ), true_label)   subject to |δ| < ε

This is a direct callback to gradient ascent from Ch. 21 (instead of descending the loss w.r.t. weights, you ascend it w.r.t. the input), framed as an adversary optimizing against your model. Adversarial training (a defense) turns this into a full minimax game: the defender trains to minimize loss even under the worst-case attacker perturbation:

min_θ  max_δ  Loss(model_θ(x + δ), true_label)

GAN (Generative Adversarial Network) training is the same minimax structure applied generatively — a generator and discriminator playing an adversarial game against each other until they reach (ideally) a Nash equilibrium.

The attack, derived: FGSM from a norm and a tangent line

How do you find the δ that maximizes the loss? Take the first-order Taylor approximation of the loss around the clean input x (Ch. 12, 13):

Loss(x + δ) ≈ Loss(x) + ∇ₓLossᵀ · δ

So the attacker wants to maximize the dot product ∇ₓLossᵀ · δ subject to ‖δ‖∞ ≤ ε (no pixel changed by more than ε, using the L∞ norm from Ch. 10). A dot product is maximized term by term by making each δᵢ as large as allowed, ±ε, with the same sign as the gradient component:

δ* = ε · sign(∇ₓ Loss)                  the Fast Gradient Sign Method (Goodfellow et al., 2015)

Why tiny changes work: dimensionality. The loss increases by about ε · ‖∇ₓLoss‖₁, and the L1 norm grows with the number of inputs. For a 224 × 224 × 3 image (d = 150,528) with ε = 1/255 and an average gradient size of 0.01, the first-order change is about 150,528 · 0.0039 · 0.01 ≈ 5.9 logits. That's enough to flip a confident prediction, even though no single pixel changed visibly. Many imperceptible changes add up in high dimensions, which is the same d-scaling as the attention variance argument in Ch. 20. PGD (projected gradient descent) repeats small FGSM steps and clips back into the ε-ball each time. It's the standard attack used in adversarial training and in LLM jailbreak research (GCG optimizes adversarial token suffixes the same way).

Mixed strategies: why security patrols should be random

In many games the equilibrium is not a single action but a probability distribution over actions, a mixed strategy. The defender randomizes so the attacker can't exploit any pattern.

Worked example: one guard, two targets. Target A is worth 10 to an attacker and target B is worth 5. The defender covers A with probability c and B with probability 1 - c. An attack on a covered target fails (payoff 0), and an attack on an uncovered target succeeds:

attacker's expected payoff at A:  10 · (1 - c)
attacker's expected payoff at B:   5 · c

If the defender always guards A (c = 1), the attacker hits B for 5. The defender's best randomization makes the attacker indifferent between the targets, leaving nothing predictable to exploit:

10 · (1 - c) = 5 · c   ->   c = 2/3          attacker's best payoff = 10/3 ≈ 3.3

Randomizing cuts the attacker's expected gain from 5 to 3.3 with the same single guard. Because the defender commits first and the attacker observes the strategy (but not each day's roll), this is a Stackelberg security game. Systems built on it have scheduled real patrols: ARMOR at LAX airport checkpoints (2007), the US Coast Guard's PROTECT in Boston harbour, and US Federal Air Marshal scheduling. Moving-target defences (ASLR, rotating credentials, randomized honeypot placement) apply the same idea in software. ASLR's strength, for example, is the min-entropy (Ch. 23) of the randomized address bits.

The defender's dilemma, quantified

An attacker needs one way in. A defender has to close all of them. If a system has n independent weaknesses, each exploitable with probability p:

P(breach) = 1 - (1 - p)ⁿ

With 100 weaknesses at 1% each, 1 - 0.99¹⁰⁰ ≈ 63%. That's the same formula as Ch. 14's tail-at-scale fan-out, now working against the defender. Two strategic consequences follow. Removing whole classes of weakness (memory-safe languages, parameterized queries) reduces n and beats patching instances one by one. And defence in depth turns the attacker's problem into a series chain, where they must beat every layer: three independent layers that each stop 90% of attempts let through only 0.1³ = 0.1%, as long as the layers really are independent (Ch. 8).

Real-life engineering ties

• Security: threat modeling is applied game theory — reasoning about a rational, adaptive adversary is fundamentally different from reasoning about random failures (Ch. 14), and mixing up the two framings is a common root cause of security controls that look good on paper but fail against a motivated attacker who simply routes around them.
• AI: adversarial robustness, GAN training, multi-agent reinforcement learning, and RLHF's reward-model/policy dynamic are all game-theoretic.
• Network/SWE: auction-based systems (real-time bidding for ads, cloud spot-instance pricing) are direct game-theory applications; incentive design for decentralized systems (peer-to-peer networks, blockchain consensus mechanisms) is applied mechanism design (game theory in reverse: design the game so the equilibrium is the outcome you want).

More real-life examples:

• Google Ads and most real-time ad exchanges use second-price (Vickrey) auction mechanisms, chosen specifically because they make "bid your true value" the dominant strategy for advertisers, unlike a naive first-price auction.
• Bitcoin's proof-of-work design is deliberate mechanism design: a "51% attack" is technically possible but game-theoretically irrational for a large miner, because acquiring enough hash power to attack the network is more expensive than the profit from honestly mining.
• Coordinated vulnerability disclosure and bug bounty programs shift the game-theoretic payoff for a researcher who finds a bug: paying a bounty makes responsible disclosure competitive with selling the exploit on a gray/black market, changing the equilibrium outcome.
• Braess's paradox — where adding a new road (or network link) can increase overall congestion because individually rational routing no longer aligns with the system optimum — has been documented in real city traffic studies (Seoul reported reduced congestion after removing a highway in the 2000s).

Common mistake

Modeling an attacker as a fixed, non-adaptive probability distribution (e.g., "attacks happen with 1% probability per day" — pure Ch. 14 thinking) instead of a rational actor who will adapt strategy in response to your defenses. This is why purely statistical anomaly detection (Ch. 26) is necessary but insufficient — a game-theoretically savvy attacker learns your detection thresholds and deliberately stays under them.