Stackelberg Games

Imagine two firms competing for the same market. They could announce their prices simultaneously and hope for the best — that is a Nash equilibrium, each responding to the other's expected move. But what if one firm moves first, publicly and irrevocably? Suddenly the second firm can only react, and the first firm — knowing this — can design its commitment to extract the best possible outcome.

This is the Stackelberg game, named after the German economist Heinrich von Stackelberg who described it in 1934. The model has two players: a leader who commits to a strategy first, and a follower who observes that commitment and then best-responds. Because the follower is fully rational, the leader can predict the response and choose the commitment that maximises its own payoff given that response.

The result is striking: the leader never does worse than in simultaneous play, and often does strictly better. Committing is a power, not a vulnerability — as long as the commitment is credible (the follower must believe the leader will actually carry it out).

Stackelberg games are solved — there is an efficient algorithm for finding the optimal mixed strategy for the leader in the general finite case (Conitzer & Sandholm, 2006). They sit at the intersection of classical game theory and modern algorithmic mechanism design, with real deployments in security, pricing and AI safety.

The demo below shows a 2×2 Stackelberg game between a Leader and a Follower. Both have two pure strategies. The payoff table is fixed: cells show (Leader payoff, Follower payoff).

Drag the Leader mix slider to set the probability the leader plays strategy A. The follower — who is fully rational — will always pick whichever response maximises their payoff given the leader's announced mix. Watch the follower's best response change as you cross the indifference threshold.

<p class="hint">{{hint}}</p>
<div class="payoff-table" id="payoffTable"></div>
<div class="control-row">
  <label for="leaderSlider">{{leader_label}}</label>
  <span id="pVal" class="p-val">0.50</span>
</div>
<input type="range" id="leaderSlider" min="0" max="100" value="50" step="1">
<div id="followerDisplay" class="follower-display"></div>
<div id="payoffDisplay" class="payoff-display"></div>
<div class="btns">
  <button id="optBtn" type="button">{{btn_optimal}}</button>
  <button id="resetBtn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="optResult" class="opt-result"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 4px; }
.hint { font-size: .85rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.payoff-table { display: grid; grid-template-columns: 80px 1fr 1fr; gap: 3px; margin-bottom: .8rem; font-size: .85rem; }
.cell { padding: 6px 8px; border-radius: 6px; text-align: center; }
.head { background: #dbe5ed; font-weight: 700; color: #1d3557; }
.pay  { background: #f0f4f8; border: 1px solid #cdd9e3; color: #1d3557; }
.pay.hl { background: #cfe8d4; border-color: #6dc08a; }
.control-row { display: flex; align-items: center; gap: .5rem; font-size: .9rem; margin-bottom: .3rem; }
.p-val { font-weight: 700; color: #1d3557; min-width: 2.5rem; }
input[type=range] { width: 100%; accent-color: #1d3557; margin-bottom: .7rem; }
.follower-display { font-size: .95rem; font-weight: 600; padding: .4rem .6rem; border-radius: 8px; background: #e8eef3; margin-bottom: .4rem; color: #1d3557; min-height: 1.6em; }
.payoff-display   { font-size: .9rem; color: #555; margin-bottom: .7rem; min-height: 1.3em; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .5rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.opt-result { font-size: .9rem; min-height: 1.2em; color: #0a7d33; font-weight: 600; }

// Code not found

The Optimal commitment button finds the exact leader probability that maximises the leader's expected payoff, taking into account how the follower will respond. Notice that the leader's best mix is often not a pure strategy.

How hard is it to compute the best commitment?

• Two players — polynomial. In 2006, Vincent Conitzer and Tuomas Sandholm showed that the optimal leader strategy in a two-player Stackelberg game can be found in polynomial time via a linear-program enumeration: for each pure strategy the follower might play, solve a small LP to find the best leader mix that induces it, then take the maximum. The whole procedure runs in O(m·LP(n)) time where n,m are the strategy counts.
• Multiple followers — NP-hard. With even one additional follower the problem explodes. Deciding whether the leader can guarantee a payoff above a threshold becomes NP-hard — you must reason over all possible equilibria among followers, which is the hard part.
• Bayesian uncertainty — harder still. Real security settings have an unknown attacker type drawn from a distribution. The Bayesian Stackelberg problem (Paruchuri et al., 2008) requires computing a leader strategy that is optimal in expectation over attacker types, which adds another layer of complexity.
• Commitment credibility. Even a polynomial algorithm for finding the optimal commitment is only useful if the commitment is credible. If the follower doubts the leader will carry through, the entire equilibrium unravels — a subtlety at the heart of repeated Stackelberg models.

The contrast with Nash equilibrium is instructive: Nash equilibria are hard to compute in general (PPAD-complete), but the Stackelberg equilibrium in the two-player case is strictly easier because one player moves first and the structure collapses to a single optimisation problem.

The leader-commits-first structure appears wherever one agent can make a binding public commitment before others react:

• Security scheduling (ARMOR/PROTECT). Since 2007, the Los Angeles International Airport and the US Coast Guard have deployed Stackelberg game solvers to randomise checkpoint placement and patrol routes. The security agency (leader) commits to a randomised schedule; an adversary (follower) best-responds by attacking the least-covered target. Randomisation removes the adversary's ability to exploit a predictable pattern.
• Electricity markets. A dominant generator sets output first; smaller competitors then best-respond. Regulators use Stackelberg models to design market rules that prevent the leader from abusing its first-mover advantage.
• Supply chain leadership. A powerful retailer sets contract terms; suppliers then decide quantities. Stackelberg equilibrium predicts how much surplus the retailer can extract and informs antitrust analysis.
• AI and mechanism design. When deploying an AI whose users will strategically react to its decisions, the deployment is a Stackelberg game — the designer is the leader. Optimal mechanism design under strategic agents reduces to finding the best commitment.
• Stackelberg in pricing. A market leader sets price first; competitors react. The leader deliberately leaves rivals room to coexist rather than triggering a ruinous price war — a practical illustration of the commitment advantage.

Whenever you need to make a binding decision knowing others will react rationally, you are playing a Stackelberg game — and the polynomial algorithm for the two-player case means the optimal commitment is computable in practice.

Stackelberg's insight from 1934 became a computational algorithm in 2006 and a deployed security system in 2007. The leader who commits publicly and credibly can shape the follower's best response to its own advantage — and in the two-player case, the optimal commitment is computable in polynomial time.

The edge cases are informative: with multiple followers the problem becomes NP-hard, and with uncertain follower types you enter the Bayesian Stackelberg regime. But the core idea — commit first, reason about the response, optimise the commitment — has proven extraordinarily productive, from airport security to AI mechanism design.

The next time you notice a patrol schedule that looks deliberately unpredictable, or a market leader that seems to leave just enough room for smaller rivals, you may be watching game theory at work — a rational leader playing the optimal Stackelberg commitment.