Introduction

Imagine a government setting a tax rate. Citizens respond by adjusting their behavior to minimize their own cost. The government, knowing this, must pick a rate that achieves its goals after citizens have reacted. This is bilevel optimization: a problem nested inside another problem.

The outer problem belongs to the leader: choose some variable xx to optimize an objective F(x,y)F(x, y). The catch is that yy is not the leader's to choose — it is the follower's optimal response to xx, determined by a separate inner optimization:

y∗(x)=arg⁡min⁡y  f(x,y)y^*(x) = \arg\min_{y} \; f(x, y)

So the leader's true problem is:

min⁡x  F(x, y∗(x))\min_{x} \; F(x,\, y^*(x))

This structure was formalized as the Stackelberg game in 1934 by economist Heinrich von Stackelberg, who modeled a dominant firm anticipating a competitor's reaction. The math is elegant, but the computation is brutal: to evaluate the leader's objective at a single point xx, you must first solve the follower's problem — and you must do this for every candidate xx the leader might consider.

Try It: Stackelberg Game

The demo below models a simple Stackelberg game. The leader picks a production quantity x∈[0,10]x \in [0, 10]. The follower then chooses yy to maximize their own profit, knowing xx. The leader wants to maximize their profit after the follower has reacted.

<!-- Bilevel optimization (Stackelberg game) demo — leader picks x, follower best-responds with y* -->
<div class="intro-hint">A <b>leader</b> picks production quantity x. A <b>follower</b> then picks y to maximize their own profit. The leader's goal: maximize <em>their</em> profit knowing the follower will react optimally.</div>
<div class="game-area">
  <div class="slider-row">
    <label for="leaderSlider"><strong>Leader</strong> x = <span id="xVal">5.0</span></label>
    <input type="range" id="leaderSlider" min="0" max="100" value="50" step="1"
           title="Set the leader's production quantity" aria-label="Leader">
  </div>
  <div class="info-grid">
    <div class="info-box leader-box">
      <div class="role-label">Leader</div>
      <div class="formula">max F(x,y*) = x·(10−x−y*)</div>
      <div class="value-row">Payoff: <span id="leaderPayoff" class="big-val">—</span></div>
    </div>
    <div class="arrow-col">&#x21E8;</div>
    <div class="info-box follower-box">
      <div class="role-label">Follower</div>
      <div class="formula">max f(x,y) = y·(10−x−y) given x</div>
      <div class="value-row">y* = <span id="yVal" class="big-val">—</span></div>
      <div class="value-row">Payoff: <span id="followerPayoff" class="big-val">—</span></div>
    </div>
  </div>
  <div class="chart-wrap">
    <div class="chart-label">Leader's payoff curve as a function of x (red dot = current x)</div>
    <canvas id="payoffChart" width="420" height="130" aria-label="Leader's payoff curve as a function of x (red dot = current x)"></canvas>
    <div class="chart-axes">
      <span>x=0</span><span>x=10</span>
    </div>
  </div>
  <div id="status" class="status"></div>
  <div class="btns">
    <button id="btnOptimize" type="button">Find leader's optimum</button>
    <button id="btnReset" type="button" class="ghost">Reset</button>
  </div>
</div>

/* layout and color styles for the Stackelberg demo */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px 2px; }
.intro-hint { font-size: .88rem; color: #444; margin-bottom: .8rem; line-height: 1.5; }
.game-area { max-width: 440px; }
.slider-row { display: flex; flex-direction: column; gap: .3rem; margin-bottom: .8rem; font-size: .95rem; }
#leaderSlider { width: 100%; accent-color: #1d3557; cursor: pointer; }
.info-grid { display: flex; align-items: center; gap: .5rem; margin-bottom: .8rem; }
.info-box { flex: 1; border-radius: 10px; padding: .6rem .8rem; }
.leader-box { background: #dde8f5; border: 1px solid #9bb3d4; }
.follower-box { background: #fde8d8; border: 1px solid #e0a87a; }
.arrow-col { font-size: 1.6rem; color: #888; flex: 0 0 auto; }
.role-label { font-weight: 700; font-size: .85rem; margin-bottom: .3rem; color: #333; }
.formula { font-size: .78rem; color: #555; font-style: italic; margin-bottom: .4rem; }
.value-row { font-size: .9rem; }
.big-val { font-weight: 700; font-size: 1.05rem; }
.chart-wrap { background: #f4f7fb; border: 1px solid #cdd9e3; border-radius: 8px; padding: .5rem; margin-bottom: .6rem; }
.chart-label { font-size: .8rem; color: #555; margin-bottom: .3rem; text-align: center; }
canvas { display: block; width: 100%; height: auto; }
.chart-axes { display: flex; justify-content: space-between; font-size: .75rem; color: #888; margin-top: .2rem; }
.status { font-size: .95rem; font-weight: 600; min-height: 1.3em; margin-bottom: .5rem; }
.status.ok { color: #0a7d33; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Stackelberg duopoly (linear demand). Market price p = 10 - x - y.
// Leader's profit: F(x,y) = x*(10 - x - y).
// Follower maximizes f(x,y) = y*(10 - x - y) taking x as given.
// Analytic solution: y*(x)=(10-x)/2; leader optimum x*=5, y*=2.5, F*=12.5.

const STEPS = 200; // resolution for brute-force curve scan

// Follower best-response: solve df/dy=0 => 10 - x - 2y = 0 => y* = (10-x)/2.
function followerBestResponse(x) {
  // First-order condition of follower: d/dy [y*(10-x-y)] = 10-x-2y = 0
  // => y* = (10 - x) / 2, clipped to [0, 10]
  const yOpt = (10 - x) / 2;
  return Math.max(0, Math.min(10, yOpt));
}

// Leader payoff given x and follower response y.
function leaderPayoff(x, y) {
  return x * (10 - x - y);
}

// Follower payoff given x and y.
function followerPayoff(x, y) {
  return y * (10 - x - y);
}

// Scan x in [0,10] and pick the x that maximizes F(x, y*(x)).
function findLeaderOptimum() {
  let bestX = 0, bestF = -Infinity;
  for (let i = 0; i <= STEPS; i++) {
    const x = (i / STEPS) * 10;
    const y = followerBestResponse(x);
    const f = leaderPayoff(x, y);
    if (f > bestF) { bestF = f; bestX = x; }
  }
  return { x: bestX, f: bestF };
}

// Draw the leader's payoff curve F(x, y*(x)) over x in [0,10].
function drawChart(currentX) {
  const canvas = document.getElementById('payoffChart');
  const ctx = canvas.getContext('2d');
  const W = canvas.width, H = canvas.height;
  ctx.clearRect(0, 0, W, H);

  // draw axes
  ctx.strokeStyle = '#ccc'; ctx.lineWidth = 1;
  ctx.beginPath(); ctx.moveTo(30, 5); ctx.lineTo(30, H - 20);
  ctx.lineTo(W - 5, H - 20); ctx.stroke();

  const xs = [], fs = [];
  let fMin = Infinity, fMax = -Infinity;
  for (let i = 0; i <= STEPS; i++) {
    const x = (i / STEPS) * 10;
    const y = followerBestResponse(x);
    const f = leaderPayoff(x, y);
    xs.push(x); fs.push(f);
    if (f < fMin) fMin = f;
    if (f > fMax) fMax = f;
  }
  const range = fMax - fMin || 1;

  // draw payoff curve
  ctx.strokeStyle = '#1d3557'; ctx.lineWidth = 2;
  ctx.beginPath();
  for (let i = 0; i <= STEPS; i++) {
    const px = 30 + (xs[i] / 10) * (W - 35);
    const py = (H - 20) - ((fs[i] - fMin) / range) * (H - 30);
    i === 0 ? ctx.moveTo(px, py) : ctx.lineTo(px, py);
  }
  ctx.stroke();

  // draw marker for current x
  const cy = followerBestResponse(currentX);
  const cf = leaderPayoff(currentX, cy);
  const mx = 30 + (currentX / 10) * (W - 35);
  const my = (H - 20) - ((cf - fMin) / range) * (H - 30);
  ctx.fillStyle = '#e63946';
  ctx.beginPath(); ctx.arc(mx, my, 5, 0, 2 * Math.PI); ctx.fill();

  // y-axis min/max labels
  ctx.fillStyle = '#888'; ctx.font = '10px system-ui';
  ctx.fillText(fMax.toFixed(1), 2, 12);
  ctx.fillText(fMin.toFixed(1), 2, H - 22);
}

function fmt(v) { return v.toFixed(2); }

function update() {
  const slider = document.getElementById('leaderSlider');
  const x = (parseInt(slider.value, 10) / 100) * 10;
  const y = followerBestResponse(x);
  const lf = leaderPayoff(x, y);
  const ff = followerPayoff(x, y);

  document.getElementById('xVal').textContent = fmt(x);
  document.getElementById('yVal').textContent = fmt(y);
  document.getElementById('leaderPayoff').textContent = fmt(lf);
  document.getElementById('followerPayoff').textContent = fmt(ff);
  drawChart(x);
  document.getElementById('status').textContent = '';
  document.getElementById('status').className = 'status';
}

document.getElementById('leaderSlider').addEventListener('input', update);

document.getElementById('btnOptimize').addEventListener('click', () => {
  const { x, f } = findLeaderOptimum();
  const sliderVal = Math.round((x / 10) * 100);
  document.getElementById('leaderSlider').value = sliderVal;
  update();
  const s = document.getElementById('status');
  s.textContent = i18nFmt('Optimum: x* = %fmt% → leader payoff = %fmt2%', { fmt: fmt(x), fmt2: fmt(f) });
  s.className = 'status ok';
  console.log('Leader optimum x =', fmt(x), 'payoff =', fmt(f));
});

document.getElementById('btnReset').addEventListener('click', () => {
  document.getElementById('leaderSlider').value = 50;
  update();
});

update();
Result
Console

Drag the slider to change the leader's choice. The follower's best response updates instantly. The leader's payoff curve shows how the overall objective depends on xx — find the peak to solve the bilevel problem.

The Real Complexity

The nesting makes bilevel problems qualitatively harder than single-level ones.

  • Evaluating the objective is itself an optimization. To compute F(x,y∗(x))F(x, y^*(x)) you first solve the follower's problem from scratch. Every function evaluation hides a complete inner solve.
  • The feasible region is implicit. The set of points (x,y∗(x))(x, y^*(x)) that the leader can actually reach is defined by the follower's optimality conditions, not by explicit constraints. This set can be non-convex and even disconnected.
  • NP-hard in the simplest cases. Even when both levels are linear programs, the bilevel problem is NP-hard. The proof encodes integer programming inside the follower's constraints.
  • Σ2P\Sigma_2^P-complete in the polynomial hierarchy. For discrete bilevel problems, the complexity lives in the second level of the polynomial hierarchy — strictly harder than NP, assuming the hierarchy does not collapse. Deciding whether the leader can achieve a target value is Σ2P\Sigma_2^P-complete.
  • Optimistic vs. pessimistic formulations. When the follower's optimal response is not unique, should we assume the best or the worst for the leader? These two conventions give different (and both hard) problems.

Classic algorithms — KKT conditions, penalty methods, branch-and-bound — all implicitly solve or approximate the inner problem repeatedly. For large instances, even getting a good approximation is a major research challenge.

Where It Matters

Wherever one agent anticipates and influences another's decision, bilevel structure arises:

  • Pricing and taxation: a firm sets prices knowing consumers will buy optimally; a government sets taxes knowing firms will reorganize. Both are classic Stackelberg settings.
  • Network tolls: a planner sets road tolls to manage traffic; drivers then minimize their own travel time. The planner's best tolls depend on the equilibrium the drivers reach — a bilevel routing problem.
  • Adversarial machine learning: training a classifier robust to adversarial examples is a bilevel problem. The inner level finds the worst-case perturbation; the outer level trains the model to survive it.
  • Hyperparameter optimization: choosing hyperparameters to minimize validation loss, where training the model is the inner optimization, is a bilevel problem at the heart of modern deep learning.
  • Robust optimization: designing a system that performs well under the worst-case scenario is a min-max structure — a special case of bilevel.

The framework connects directly to Nash equilibrium (where both players optimize simultaneously) and to linear programming duality (which handles the single-level limit).

Conclusion

Bilevel optimization is what happens when optimization meets strategy. A single nesting — the leader anticipating the follower's rational response — is enough to push the problem outside NP and into qualitatively harder territory.

The structure is everywhere: in markets, networks, adversarial AI, and robust design. And the core lesson is always the same: when your objective depends on someone else's optimization, you cannot separate planning from prediction. You must solve both at once — and that, it turns out, is one of the hardest things computation can ask.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/bilevel-optimization/Content licensed under CC BY-NC 4.0.