Stackelberg Games and Commitment

A Stackelberg game takes an ordinary two-player game and adds one asymmetry: the leader picks a strategy, the follower observes it, and only then responds. Nothing about the payoffs changes — only who knows what, when. The consequence is the finding that generalises far beyond the duopoly it was named for: the ability to commit is worth something, and it is a different thing from the ability to play well. In a two-player game, optimally committing to a mixed strategy never leaves the leader worse off than any Nash equilibrium of the simultaneous-move game and often leaves her strictly better off (von Stengel & Zamir 2004); committing to a pure strategy can help or hurt. The Nobel committee’s one-sentence summary of Schelling’s contribution says the strange part out loud: “a party can strengthen its position by overtly worsening its own options” (Nobel press release, 10 October 2005). And computationally the model is easier than the one it replaces — a two-player Stackelberg mixed strategy is one linear program per follower action, while a Nash equilibrium is PPAD-complete.

What this note is and is not

This note covers the leader–follower model, the value of commitment, why removing your own options can pay, the algorithms, and the security-games line of work that deployed it. The credibility problem — why a threat you would not carry out changes nothing — belongs to Subgame Perfect Equilibrium, which this note leans on constantly. Every numeric claim below was computed here in exact rational arithmetic; the code and the measured results are in-line.

---

Mental Model: the same payoffs, a different information structure

flowchart TB
    subgraph SIM["Simultaneous move — Nash"]
        S1["Leader picks σ₁<br/>Follower picks σ₂<br/><b>neither observes the other</b>"]
        S2["Stability: neither wants to<br/>deviate given the other's choice"]
        S1 --> S2
    end
    subgraph STK["Leader commits — Stackelberg"]
        T1["Leader commits to σ₁<br/><b>follower SEES σ₁</b>"]
        T2["Follower plays a best reply<br/>t ∈ BR(σ₁)"]
        T3["Leader picks σ₁ to maximise<br/>her payoff <i>anticipating</i> BR(σ₁)"]
        T1 --> T2 --> T3
    end
    SIM -->|"add observability<br/>+ binding commitment"| STK
    STK --> R["Leader payoff weakly RISES<br/>(mixed commitment, 2 players)<br/>Follower payoff may rise or fall"]

What it shows: the only difference between the two models is whether the follower observes the leader’s strategy before choosing. The insight: commitment is not a strategy, it is a change to the game’s information structure, and its value is the gap between the two solution concepts applied to the same payoff matrix.

Two definitions do the work:

• BR(σ) = argmax_t u_f(σ, t) — the follower’s best-response correspondence. u_f is the follower’s utility; σ is the leader’s (possibly mixed) strategy; t ranges over the follower’s pure actions. There is never any reason for the follower to randomise: having observed σ, she faces a single-agent decision problem.
• An optimal strategy to commit to maximises max_{t ∈ BR(σ)} u_l(σ, t) over σ (Conitzer & Sandholm 2006, §2.1).

That inner max is the tie-breaking assumption: when the follower is indifferent, she is assumed to break the tie in the leader’s favour. This is not cosmetic. Conitzer and Sandholm explain why it is forced: without it, “there would not exist an optimal strategy for the row player” — she would want probability 1/2 + ε for ever-smaller ε and the supremum would not be attained. With it, an optimum always exists and “corresponds to a subgame perfect equilibrium of the extensive-form representation of the leadership situation”. The resulting concept is called Strong Stackelberg Equilibrium (SSE); the pessimistic tie-breaking variant is the weak one, and it can fail to exist.

---

The classic result: quantity duopoly

Cournot’s 1838 model: two firms produce a homogeneous good, qᵢ is firm i’s quantity, total output Q = q₁ + q₂, inverse demand P = a − bQ, and each firm has constant unit cost c with a > c. Firm i’s profit is πᵢ = (P − c)qᵢ.

Cournot (simultaneous). Maximising π₁ = (a − c)q₁ − b q₁² − b q₁ q₂ over q₁ gives the first-order condition a − c − 2b q₁ − b q₂ = 0; the second derivative is −2b < 0 so the condition is sufficient. Solving the symmetric pair yields q₁* = q₂* = (a − c)/(3b) and price P = (a + 2c)/3 — the derivation as given in Bonanno’s Game Theory §2.7, which I read.

Stackelberg (firm 1 commits first). Rearranging the first-order condition gives firm 2’s best-reply function R₂(q₁) = (a − c − b q₁)/(2b). Firm 1 substitutes it into its own profit before optimising — this is the whole trick, and it is Backward Induction on a two-node tree:

π₁(q₁) = (a − b·(q₁ + R₂(q₁)) − c)·q₁
       = (a − c − b q₁ − b·(a − c − b q₁)/(2b))·q₁
       = ((a − c)/2 − (b/2)·q₁)·q₁

dπ₁/dq₁ = (a − c)/2 − b q₁ = 0   ⟹   q₁ = (a − c)/(2b)

Then q₂ = R₂(q₁) = (a − c)/(4b), and profits are π₁ = (a−c)²/(8b) for the leader and π₂ = (a−c)²/(16b) for the follower, versus (a−c)²/(9b) each under Cournot.

I verified all of this in exact rationals for three parameter sets, including one with fractional a, b, c, and separately by grid-searching the leader’s quantity over 4,001 rational points with the follower best-replying at each:

a=12  b=1  c=0
  Cournot     : q₁=4    q₂=4    Q=8    P=4  π₁=16   π₂=16   industry 32
  Stackelberg : q₁=6    q₂=3    Q=9    P=3  π₁=18   π₂=9    industry 27
  leader gain  π₁ˢ − π₁ᶜ = +2   ( = (a−c)²/(72b), confirmed for all three parameter sets )
  follower loss π₂ˢ − π₂ᶜ = −7
  industry profit −5,  price −1  (consumers gain)
  grid search over q₁ (4000 points): best π₁ = 18 at q₁ = 6 — matches the closed form exactly

Five things to take from that table, and only the first is the famous one:

1. The leader produces more and earns more. 6 > 4 and 18 > 16. The leader’s gain is exactly (a − c)²/(72b), which I confirmed symbolically-by-example across all three parameter sets.
2. The follower is hurt far more than the leader gains — −7 against +2. Commitment is not a Pareto improvement; it is largely a transfer, plus a deadweight loss.
3. Industry profit falls (32 → 27). The two firms jointly would rather move simultaneously. The leader cannot exploit that, because refusing to commit is not available once the game is the leadership game.
4. Consumers gain: output rises 8 → 9 and price falls 4 → 3. Sequential competition is more competitive than simultaneous competition.
5. q₁ = (a−c)/(2b) is the monopoly quantity — the leader produces what a monopolist facing residual demand would, and the follower fills in behind.

Uncertain — the 1934 source was not read

Verify: what exactly von Stackelberg wrote. Reason: Marktform und Gleichgewicht (Vienna: Julius Springer, 1934) is in German and, as far as I can establish from this machine, exists online only as a scan. I did not read it. The bibliographic entry above is copied from the reference list of Shoham & Leyton-Brown, which I did read, and the content attribution — that he showed a firm able to commit to a production quantity does better than in the Cournot solution — is taken from Conitzer & Sandholm 2006 §1 and von Stengel & Zamir 2004 §1. The algebra above is my own derivation, checked numerically. To resolve: read the 1934 monograph or a scholarly translation.

---

Commitment as self-mutilation: burning the bridges

The duopoly result is easy to misread as “moving first is good”. It is not; being seen to be unable to change your mind is good, and the sharpest form of that is destroying your own options.

The Nobel committee’s scientific background for the 2005 prize states Schelling’s point directly: he emphasised “that it may be advantageous to worsen one’s own options in order to elicit concessions from the opponent. It can be wise for a general to burn bridges behind his troops as a credible commitment towards the enemy not to retreat. Similarly, the owners of a firm may profitably appoint a manager with limited powers to negotiate, and a politician may gain from making public promises that would be embarrassing to break.” And crucially: “Such tactics work if the commitment is irreversible or can only be undone at great cost, while commitments that are cheap to reverse will not elicit large concessions” (Aumann and Schelling’s Contributions to Game Theory, §2.1).

This is measurable, so let us measure it. Model an entry-deterrence game where the incumbent is the player who cannot commit — the entrant moves first, the incumbent responds:

flowchart LR
    E(("Entrant")) -->|Out| O["(entrant 0, incumbent 2)"]
    E -->|In| I(("Incumbent"))
    I -->|Fight| FI["(entrant −1, incumbent 0)"]
    I -->|Accommodate| AC["(entrant 1, incumbent 1)"]
    style AC stroke-width:3px
    style O stroke-width:3px,stroke-dasharray: 4 4

What it shows: the extensive form of entry deterrence. Solid border = the backward-induction outcome of the game as drawn; dashed = the outcome once the incumbent’s Accommodate branch is deleted. The insight: the incumbent’s payoff rises from 1 to 2 by amputating the option it would actually have wanted to use.

Trace it. If the entrant enters, the incumbent compares Fight (0) against Accommodate (1) and accommodates. The entrant, forecasting that, compares Out (0) against In (1) and enters. Incumbent gets 1. The threat “we will fight” is exactly the kind of incredible threat that Subgame Perfect Equilibrium deletes.

Now burn the bridge — a long-term supply contract with punitive exit terms, a plant sized for a price war, a public promise expensive to break — so that Accommodate is simply not in the incumbent’s strategy set any more, and the entrant can see it:

=== Entry deterrence (entrant moves first, incumbent responds) ===
  full game: entrant plays In, incumbent Accommodates -> entrant 1, incumbent 1
  bridge burnt (Accommodate deleted): entrant plays Out -> entrant 0, incumbent 2
  incumbent gains +1 by DESTROYING one of its own options

Both players end up worse than the incumbent’s dream and the entrant’s dream respectively — and note the entrant is strictly worse off (1 → 0), which is the point of the manoeuvre.

How often does this work? I generated random two-stage games in which a “mover” chooses first and a “responder” chooses second with full observation, then asked: does there exist a subset of the responder’s own actions such that deleting the rest strictly raises the responder’s backward-induction payoff? Payoffs were distinct integers drawn from a common range so that the games are non-degenerate, 3,000 games per size:

2×2 : responder strictly better off after deleting some of its own actions
        in  418/3000 = 13.9% of games
3×3 : in  875/3000 = 29.2%
4×4 : in 1232/3000 = 41.1%

The more options you have, the more likely it is that some of them are hurting you. That inverts the usual intuition that optionality is valuable, and the mechanism is simple: an option is only harmful when it is tempting — when you would take it ex post and the other player knows it. The frequency grows with the action count because there are more chances for such a temptation to exist and more subsets available to remove it.

This is the same phenomenon as delegation to an agent with restricted authority, as a constitution that binds a future legislature, and — the example the Nobel background gives — as central-bank independence: “under certain circumstances, voters and politicians are better off delegating monetary policy to decision makers with other preferences than their own”, because firms and unions set prices anticipating the policy. It is also why the analyses of Spence (1977) and Dixit (1980) show a firm can profit “by changing its cost structure, even if its unit production cost increases as a result”.

Uncertain

Verify: the details of Schelling’s own formulations in The Strategy of Conflict (1960) and his 1956 American Economic Review article “An Essay on Bargaining”. Reason: I did not read either. Everything attributed to Schelling above comes from the Royal Swedish Academy’s 2005 scientific background document and press release, both fetched and read in full. To resolve: read the 1960 book, chapter 2 in particular.

---

Computing an optimal strategy to commit to

Pure commitment: trivial, and sometimes harmful

Enumerate the leader’s pure strategies; for each, find the follower’s best reply (ties to the leader); take the best. Conitzer and Sandholm’s Theorem 1 states this runs in O(#players · #outcomes) — linear in the input, because a normal-form game’s input is already Ω(#players · #outcomes).

But committing to a pure strategy can hurt. Committing to Rock in rock-paper-scissors and announcing it is the standard illustration (Conitzer, On Stackelberg Mixed Strategies). Measured over random general-sum games, the best pure commitment is worse than the best Nash payoff for the leader in 6.8% of 2×2 games and 12.0% of 3×3 games.

Mixed commitment: one LP per follower action

For each follower pure action t, solve for the leader distribution p that makes t a best reply and, subject to that, maximises the leader’s payoff. Take the best over t. This is Conitzer and Sandholm’s Theorem 2 — “In 2-player normal-form games, an optimal mixed strategy to commit to can be found in polynomial time using linear programming”:

maximise    Σ_{s∈S} p_s · u_l(s, t)
subject to  Σ_{s∈S} p_s · u_f(s, t) ≥ Σ_{s∈S} p_s · u_f(s, t')   for all t' ∈ T
            Σ_{s∈S} p_s = 1
            p_s ≥ 0

Symbol by symbol: S and T are the leader’s and follower’s pure strategy sets; p_s is the probability the leader commits to s; u_l, u_f are the two utility functions. The first family of constraints says “given p, action t is at least as good for the follower as any alternative t'” — it carves out the best-response region of the simplex on which t is optimal. The objective then maximises the leader’s payoff over that region. Each region is a polytope, the union of the regions is the whole simplex, so |T| LPs cover every case.

flowchart TB
    G["2-player normal-form game (A, B)"] --> L1["LP for follower action t₁:<br/>max leader payoff s.t. t₁ is a best reply"]
    G --> L2["LP for follower action t₂"]
    G --> Ln["... one LP per follower action"]
    L1 --> M["take the maximum"]
    L2 --> M
    Ln --> M
    M --> SSE["Strong Stackelberg Equilibrium<br/>leader mixed strategy p*, follower action t*"]

What it shows: the algorithm as a decomposition of the leader’s simplex into follower-best-response regions. The insight: the hard part of equilibrium computation — the fixed point — has disappeared. The follower is not a strategic agent inside the optimisation; she is a constraint.

My implementation uses the two-phase exact simplex over fractions.Fraction described in Coalitional Games (Bland’s rule, cross-validated against brute-force vertex enumeration on 300/300 random LPs). Nash equilibria, for comparison, are found by exact equal-support enumeration: for every pair of supports of equal size, solve the indifference systems by Gaussian elimination over Fraction, then verify the best-response conditions directly. That verification makes the enumerator sound always; it is complete only for non-degenerate games, which is why the random games below use distinct payoffs.

Reproducing the published examples exactly

--- Conitzer & Sandholm EC'06, §2.1 example ---
       L        R                Nash equilibria: p=(1,0) q=(1,0), leader 2
  U  (2,1)    (4,0)              best PURE commitment: row D → col R, leader 3
  D  (1,0)    (3,1)              STACKELBERG: p=(1/2, 1/2), follower plays R, leader 7/2
                                 value of commitment = 7/2 − 2 = 3/2

--- Korzhyk, Yin, Kiekintveld, Conitzer & Tambe, JAIR 2011, Table 1 ---
       c        d                Nash equilibria: p=(1,0) q=(1,0), leader 1
  a  (1,1)    (3,0)              best PURE commitment: leader 2
  b  (0,0)    (2,1)              STACKELBERG: p=(1/2, 1/2), follower plays d, leader 5/2
                                 value of commitment = 5/2 − 1 = 3/2

--- Matching Pennies (zero-sum) ---
  Nash: p=(1/2,1/2), q=(1/2,1/2), value 0
  best PURE commitment: −1        STACKELBERG (mixed): 0    value of commitment = 0

--- Prisoner's Dilemma ---
  Nash: (D, D), leader 1          STACKELBERG: p=(0,1), leader 1    value of commitment = 0

Every figure matches the source. The first game is the one to internalise. In the normal form, D is strictly dominated by U for the row player — and the optimal thing to commit to is a fifty-fifty mixture that puts half its weight on the dominated row. Commitment does not merely re-weight; it makes strictly dominated actions worth playing, because a dominated action can be the one that changes the follower’s incentives. Iterated elimination of dominated strategies is invalid in a leadership game.

The third and fourth games show the two ways commitment is worth exactly nothing. In matching pennies, mixed commitment buys nothing because the game is zero-sum — that is the minimax theorem, and Conitzer puts it exactly this way: “the Stackelberg mixed strategies for player 1 coincide with her maximin strategies in a two-player zero-sum game”. Verified: over 150 random zero-sum 3×3 games, the SSE leader value equalled every Nash value in 150/150. In the prisoner’s dilemma, commitment buys nothing because the follower’s dominant action does not depend on the leader’s mixture at all.

The headline measurement

2×2 random general-sum games (400 usable, distinct integer payoffs):
   SSE leader payoff ≥ best Nash leader payoff : 400/400
   strictly greater                            :  71/400 = 17.8%
   best PURE commitment WORSE than best Nash   :  27/400 =  6.8%
3×3 random general-sum games (200 usable):
   SSE leader payoff ≥ best Nash leader payoff : 200/200
   strictly greater                            :  78/200 = 39.0%
   best PURE commitment WORSE than best Nash   :  24/200 = 12.0%

600/600 games with no violation of the weak inequality, and the strict-gain rate roughly doubling from 2×2 to 3×3. This is the empirical face of von Stengel and Zamir’s theorem, whose precise statement is worth quoting because the informal version (“commitment never hurts”) is subtly wrong in non-generic games:

“All subgame perfect equilibrium payoffs to the leader (player I) in the leadership game belong to an interval [L, H]. The highest possible leader payoff H is at least as high as any Nash equilibrium payoff to player I in the simultaneous game. The lowest possible leader payoff L is at least as high as the lowest Nash equilibrium payoff. … If no pure strategy of the follower is weakly dominated by or payoff equivalent to a different (possibly mixed) strategy, then the leader’s payoff is unique (L = H). In particular, this is the case in a generic game.” — von Stengel & Zamir 2004, §1

So: in generic games the leader payoff is a single number, and it beats every Nash payoff. In degenerate games it is an interval, and only the two endpoints are separately comparable to the Nash endpoints. Conitzer adds that the comparison extends past Nash: “the Stackelberg leader’s expected utility is always at least the expected utility that she would receive in any Nash (or even correlated) equilibrium of the simultaneous-move game” (Letchford, Conitzer & Munagala, citing von Stengel & Zamir). Commitment dominates Correlated Equilibrium too.

Where it stops being easy

Setting	Pure commitment	Mixed commitment
Normal form, 2 players	O(#outcomes)	one LP per follower action
Normal form, ≥ 3 players	O(#players · #outcomes)	NP-hard
Bayesian, 1-type leader	O(#outcomes · #types)	NP-hard
Bayesian, 1-type follower	NP-hard	one LP per follower action
Bayesian, general	NP-hard	NP-hard

Reproduced from the two summary tables in Conitzer & Sandholm 2006, §4. Two things stand out. First, the table is not monotone in the obvious way: for pure strategies the problem is easy when the leader has one type and hard when the follower does; for mixed strategies it is exactly the reverse. Conitzer and Sandholm flag this contrast explicitly. Second, LP is not just a method but the method: their Theorem 3 shows any linear program with a probability constraint can be encoded as an optimal-mixed-commitment problem, so the LP formulation is tight — you cannot do better than linear programming in general.

---

Security games: the deployed form

The largest applied programme built on this model treats physical security as a Stackelberg game. A security game (Kiekintveld et al. 2009, as defined in §2 of the JAIR paper I read) has a defender who allocates K resources to cover targets T = {t₁, …, tₙ}, and an attacker who picks one target. Payoffs depend only on which target is attacked and whether it was covered: U_d^c(tᵢ) / U_d^u(tᵢ) for the defender, U_a^c(tᵢ) / U_a^u(tᵢ) for the attacker, with the structural assumptions ΔU_d(tᵢ) = U_d^c − U_d^u > 0 and ΔU_a(tᵢ) = U_a^u − U_a^c > 0 — covering a target helps the defender and hurts the attacker. Note the games are explicitly not zero-sum: the JAIR paper cites Bier (2007) on the point that an attacker’s utility depends on things like the cost of mounting an attack and a target’s propaganda value, which barely affect the defender.

The defender commits first because the attacker is assumed to conduct surveillance: the foundational assumption is “that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy”. Randomisation is the product, not the equilibrium: a deterministic patrol is a schedule an adversary can read off and route around.

Deployment, with the parts I could and could not verify

ARMOR at Los Angeles International Airport. This one I read in full. ARMOR (Assistant for Randomized Monitoring over Routes) “has been successfully deployed on a trial basis since August 2007” with the Los Angeles World Airports police “in randomized scheduling of checkpoints, and since November 2007 for generating randomized patrolling schedules for canine units” (Pita et al., AAMAS 2008 industrial track). It casts checkpoint placement and canine assignment as a Bayesian Stackelberg game — a distribution over adversary types — and solves it with an algorithm called DOBSS (Decomposed Optimal Bayesian Stackelberg Solver). Given the NP-hardness of Bayesian mixed commitment in the table above, DOBSS is a mixed-integer formulation, not a polynomial-time algorithm. The paper also stresses a mixed-initiative interface allowing officers to override the schedule — an important operational detail, and a hole in the model, since an override is a deviation from the committed strategy.

IRIS with the Federal Air Marshals Service. Attested by the JAIR paper: “the second is IRIS, a similar application deployed by the Federal Air Marshals Service (FAMS) (Tsai, Rathi, Kiekintveld, Ordonez, & Tambe, 2009)”. Marshals fly tours returning to a base, so the defender’s resources carry scheduling constraints — this is the domain that motivates the general schedules formulation.

Uncertain — deployment literature partially unreachable, and one correction

Verify: the details of IRIS, PROTECT, and GUARDS. Reason: I could not retrieve the primary papers. teamcore.usc.edu has migrated to a Harvard site whose publication listing no longer carries the 2008–2012 papers; the IFAAMAS proceedings URLs I tried for AAMAS 2009 and AAMAS 2012 returned 404 or failed to connect; jair.org’s direct download endpoint returned 404 (the JAIR paper itself was read from the author’s Duke page). Everything above about IRIS is second-hand from the JAIR 2011 paper, which I did read in full. Correction to a common description: the US Coast Guard system is not IRIS. As of the JAIR paper (published 06/11) the Coast Guard work was “an application under development … for suggesting patrolling strategies to protect ports”; the deployed Coast Guard system is PROTECT (Shieh et al., AAMAS 2012, Boston and New York), whose paper I could not fetch. Similarly, GUARDS was at that date being “tested and evaluated” by the TSA for potential deployment at over 400 airports — not deployed. Any claim that these were live should be dated and sourced. Note also the ARMOR paper is reachable at the IFAAMAS URL above and returns 50 KB of extractable text — contrary to a report that ARMOR primary papers 404.

A worked security game, computed exactly

Three targets, one defender resource, singleton schedules (the LAX structure — “the LAX domain is also a subclass of security games as defined here, with schedules of size 1 and homogeneous resources”). Defender covered payoff 0 everywhere; uncovered payoffs −10, −6, −4; attacker payoffs (−2, 8), (−1, 5), (−3, 3) for covered/uncovered:

Defender payoff matrix (rows = which target is covered, cols = which is attacked)
        attack t₁  t₂   t₃                Attacker payoffs
 cover t₁   0   −6  −4                     −2   5   3
 cover t₂ −10    0  −4                      8  −1   3
 cover t₃ −10   −6   0                      8   5  −3

SSE  : coverage (7/13, 31/78, 5/78);  attacker best-responds t₂;  defender = −47/13 ≈ −3.615
NASH : the SAME defender strategy (7/13, 31/78, 5/78);  attacker mixes (6/31, 10/31, 15/31)
       defender = −120/31 ≈ −3.871
  SSE − best Nash = +103/403 ≈ +0.256
  best PURE commitment = −6  (mixed commitment is worth 31/13 ≈ 2.38 more than the best pure one)

Look carefully at what that says. The defender plays the identical mixed strategy in both solutions. Under commitment she earns more anyway — because the SSE assumes the attacker breaks his indifference in her favour and attacks t₂, while the Nash equilibrium has him mixing across the whole attack set. All three targets yield the attacker the same expected payoff 34/13, so he is indifferent; the defender’s payoff, however, differs by target (−60/13, −47/13, −146/39), and commitment captures the best of them.

This is not luck; it is a theorem. Korzhyk, Yin, Kiekintveld, Conitzer and Tambe prove that under the SSAS property — Subsets of Schedules Are Schedules, i.e. if a resource can simultaneously defend a set of targets it can defend any subset — “any Stackelberg strategy is also a Nash equilibrium strategy”, and they additionally show Nash equilibria in security games are interchangeable, which “alleviat[es] the equilibrium selection problem”. Singleton schedules trivially satisfy SSAS.

I tested it: 120 random security games with 4 targets and 2 resources, singleton schedules, random payoffs.

SSE coverage vector equals some NE coverage vector : 120/120 = 100.0%
SSE defender payoff strictly above best NE payoff  : 120/120 = 100.0%

The first line is the theorem holding. The second is the nuance the theorem does not say: identical strategies, different payoffs. The entire value of commitment in these games is the tie-break. The practical consequence is the one the JAIR authors draw — a defender who is unsure whether the attacker actually conducts surveillance can commit to an SSE strategy anyway, because “the defender is always playing a best response by using an SSE regardless of whether the attacker observes the defender’s strategy or not”. That is a genuine engineering result: it removes the need to model the adversary’s reconnaissance capability.

The result is fragile in two named ways, both from the same paper: it fails when SSAS does not hold (resources forced to cover fixed pairs of targets), and it fails when the attacker can strike multiple targets at once — there, “the SSE strategy fails to be an NE strategy in a relatively large number of games”.

---

Failure Modes and Gotchas

1. Commitment that is not observable is not commitment. The follower must see the leader’s strategy; otherwise the game is simultaneous and you are back to Nash. von Stengel and Zamir cite Bagwell (1995) on the extreme case: when the leader’s pure strategy is only imperfectly observed, “the commitment effect vanishes since the leader would always renege on the commitment, given that the follower attributes the differently observed strategy to an erroneous observation.” Van Damme and Hurkens (1997) partially rescue it via mixed equilibria. A commitment device with a noisy channel is a device that does nothing.

2. Commitment that is not credible is not commitment. This is the whole content of Subgame Perfect Equilibrium and it is why the burning-bridges framing matters: the leader must be unable, not merely unwilling, to renege. “Commitments that are cheap to reverse will not elicit large concessions.”

3. A commitment to a distribution is not a distribution over commitments. Conitzer and Sandholm flag this explicitly. Committing to “50% Fight, 50% Accommodate” is a single object the follower observes and best-responds to. Flipping a coin and then committing is something else entirely and generally worth less. Mixed commitment is also, as von Stengel and Zamir note, “obviously harder to verify” than pure commitment — which is exactly why randomised-patrol systems must publish the randomisation policy rather than the day’s schedule.

4. Tie-breaking is load-bearing. Strong (leader-favourable) tie-breaking is assumed throughout because the weak version has no optimum. Real followers break ties however they like, so an SSE that relies on a knife-edge indifference is not robust. A standard fix is to shift the leader’s mixture by ε to make the desired follower reply strictly optimal, sacrificing O(ε) of payoff for strictness.

5. Iterated elimination of dominated strategies is invalid. The Conitzer–Sandholm example commits half its weight to a strictly dominated row. Any preprocessing pass that prunes dominated strategies before computing an SSE is a bug.

6. Degeneracy makes “the leader payoff” ill-defined. In non-generic games the set of subgame-perfect leader payoffs is an interval, not a point. If your game has ties — and security games in normal form are riddled with them, since many defender mixtures induce the same coverage vector — say which endpoint you computed. My Nash enumerator uses equal-size supports and is therefore complete only for non-degenerate games; the security-game comparisons above compare coverage vectors rather than raw mixed strategies for exactly this reason, and I cannot rule out that additional equilibria exist that it did not find.

7. You may not know the follower’s payoffs. Everything above assumes u_f is known. When it is not, the leader must learn it. Letchford, Conitzer and Munagala study exactly this and show the optimal strategy to commit to can be learned from a bounded number of best-response queries in some settings; their motivation is the same worked example used here. In deployment this is the largest modelling risk: DOBSS’s Bayesian types are a guess about an adversary.

8. Three players is a different problem. Two-player mixed commitment is an LP; three-player is NP-hard. Do not assume the LP formulation generalises. Nor does the leadership advantage: von Stengel and Zamir’s abstract states the payoff comparison “no longer holds for leadership games with three or more players.”

---

Alternatives and When to Choose Them

Concept	Who moves first	Existence / uniqueness	Complexity (2 players)	Choose it when
Strong Stackelberg equilibrium	Leader commits, follower observes	Exists with leader-favourable ties; payoff unique in generic games	one LP per follower action	Commitment is credible and observable
Weak Stackelberg	Same, adversarial tie-breaking	May not exist	—	You cannot rely on the follower’s goodwill; use the ε-shift instead
Nash Equilibrium	Simultaneous	Exists (mixed); not unique	PPAD-complete	Neither side observes the other
Subgame Perfect Equilibrium	Sequential, general tree	Exists in finite perfect-information games	Backward Induction, linear in tree size	The interaction is genuinely a tree and both sides are strategic at each node
Correlated Equilibrium	Simultaneous + mediator	Exists; superset of Nash	one LP	There is a trusted signalling device; note SSE still weakly dominates it for the leader
Maximin	Equivalent either way	Exists; value unique	one LP	The game is zero-sum — SSE and maximin coincide
Mechanism Design	Designer commits to rules	—	Varies	You control the rules, not just a strategy — leadership taken to its limit

The relationship with Mechanism Design deserves stating: Conitzer and Sandholm point out there is “an implicit leadership situation in the field of mechanism design, in which one player (the designer) gets to choose the rules of the game that the remaining players then play”, and they give the sharpest small example — a seller who values an item at 0 setting a positive reserve price. In hindsight it always looks suboptimal, yet it raises expected revenue because it changes bidders’ incentives. That is the same structure as the burning-bridges argument: an ex-post-irrational commitment that is ex-ante optimal. See Reserve Prices and Optimal Auctions.

There is also a real methodological dispute about whether SSE deserves to be a solution concept at all, since it is just subgame-perfect equilibrium of a transformed game. Conitzer’s answer in On Stackelberg Mixed Strategies is pragmatic: refusing to study it separately “obscures that they are a generalization of maximin strategies”, and makes results like the SSAS refinement “very cumbersome to state” — you would have to relate solutions of two different games rather than two concepts on one game.

---

Production Notes

What actually ships is the randomisation. ARMOR’s deliverable is a schedule for vehicle checkpoints on the roadways into LAX and an assignment of canine units to terminals. Its argument for game theory over a uniform coin flip is that “randomization must provide distinct weights to different actions based on their complex costs and benefits” — a naive uniform patrol over-protects cheap targets and under-protects expensive ones, and the LP is what turns a threat model into weights. That is the operational value proposition, and it is independent of whether the adversary is perfectly rational.

Model uncertainty is the binding constraint, not computation. For a game the size of LAX, solving the LP is not the problem. The problems are: are the payoffs right; is the adversary really best-responding; is he really observing. The JAIR paper’s entire motivation is the third question, and its answer — under SSAS, commit to the SSE regardless — is the most operationally useful theorem in the line of work, because it lets you stop trying to answer it.

Human overrides break the commitment. ARMOR’s mixed-initiative interface lets officers “occasionally adjust or override the automated schedule”. Every override is a deviation from the committed mixed strategy, and enough correlated overrides reintroduce exactly the pattern the randomisation existed to destroy. If you deploy one of these systems, the override log is a security artefact.

The vault’s adjacent systems. Security as an Adversarial Game is the general framing and its limits; Bayesian Games and Types is the machinery ARMOR actually uses (a distribution over adversary types), and is the setting where mixed commitment goes NP-hard; Trigger Strategies and Punishment is the repeated-game route to the same credibility problem, where the commitment device is a reputation rather than a burnt bridge; Rate Limiting as a Mechanism and Congestion Control as a Game are systems that commit to a published policy and let users best-respond — leadership games nobody has written down as such.

Beyond one-shot normal form. The line continues into stochastic games: Letchford et al. show that computing Stackelberg strategies in stochastic games requires care about what exactly the leader commits to, and survey the resulting complexity landscape (SIGecom Exchanges 11(2)). Commitment in a repeated or stateful setting is a genuinely harder object than commitment in a matrix.

---

See Also

• Subgame Perfect Equilibrium — the credibility half of this note; commitment is precisely the device that makes an otherwise-incredible threat binding
• Backward Induction — the algorithm behind the duopoly derivation and the entry-deterrence trace
• Nash Equilibrium — the simultaneous-move baseline every measurement here is taken against
• Mixed Strategies — why randomisation is a strategy at all; the object the leader commits to
• Zero-Sum Games and the Minimax Theorem — where Stackelberg mixed commitment and maximin coincide, so commitment is worth exactly zero
• Correlated Equilibrium — also one LP, also weakly dominated by leader commitment
• Bayesian Games and Types — the setting where ARMOR actually operates and where mixed commitment becomes NP-hard
• Security as an Adversarial Game — the systems framing of the deployed applications
• Trigger Strategies and Punishment — commitment via reputation in repeated play rather than via a device
• Mechanism Design and Reserve Prices and Optimal Auctions — leadership generalised from choosing a strategy to choosing the rules
• Coalitional Games — the sibling note: the other escape from simultaneous-move Nash, by grouping up rather than moving first
• Games and Strategic Systems in C MOC — parent map