Bilevel Optimization

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 $x$ to optimize an objective $F(x, y)$. The catch is that $y$ is not the leader's to choose — it is the follower's optimal response to $x$, determined by a separate inner optimization:

$$y^*(x) = \arg\min_{y} \; f(x, y)$$

So the leader's true problem is:

$$\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 $x$, you must first solve the follower's problem — and you must do this for every candidate $x$ the leader might consider.

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

<!-- {{c_intro}} -->
<div class="intro-hint">{{hint_para}}</div>
<div class="game-area">
  <div class="slider-row">
    <label for="leaderSlider"><strong>{{label_leader}}</strong> x = <span id="xVal">5.0</span></label>
    <input type="range" id="leaderSlider" min="0" max="100" value="50" step="1"
           title="{{slider_title}}" aria-label="{{label_leader}}">
  </div>
  <div class="info-grid">
    <div class="info-box leader-box">
      <div class="role-label">{{label_leader}}</div>
      <div class="formula">{{formula_leader}}</div>
      <div class="value-row">{{label_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">{{label_follower}}</div>
      <div class="formula">{{formula_follower}}</div>
      <div class="value-row">y* = <span id="yVal" class="big-val">—</span></div>
      <div class="value-row">{{label_payoff}}: <span id="followerPayoff" class="big-val">—</span></div>
    </div>
  </div>
  <div class="chart-wrap">
    <div class="chart-label">{{label_curve}}</div>
    <canvas id="payoffChart" width="420" height="130" aria-label="{{label_curve}}"></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">{{btn_find_opt}}</button>
    <button id="btnReset" type="button" class="ghost">{{btn_reset}}</button>
  </div>
</div>

/* {{c_styles}} */
* { 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; }

// Code not found

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 $x$ — find the peak to solve the bilevel problem.

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

• Evaluating the objective is itself an optimization. To compute $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))$ 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.
• $\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 $\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.

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).

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.