Subgame-Perfect Grid Defense at Scale: Dependent Rounding with Real Costs

When a power grid operator hardens transmission lines, a strategic attacker observes the hardened network and then chooses where to strike, and the operator responds with repairs. This design–attack–recover interaction is a sequential game: each side's best move depends on what the other has already committed to, so the right solution concept is a subgame-perfect equilibrium (SPE), meaning every plan must remain optimal even at decision points that, in hindsight, should never have been reached. Theory for exactly this setting exists — Chen, Touati, and Zhu solve a three-stage protection-and-recovery game in closed form — but only on ten-node toy networks, with unitless cost constants, and with no empirical evaluation on any real infrastructure. Meanwhile, the tools that do scale, such as continuous relaxations with rounding, have only been proven safe in static, simultaneous-move games. The result is a field with elegant equilibria nobody can compute at realistic scale, and scalable algorithms whose guarantees do not hold in the sequential setting.

This proposal builds a single pipeline that closes all four gaps at once: a three-stage infrastructure defense game whose payoffs carry genuine economic content (capital cost of hardening, operational cost, value of lost load, recovery cost, payback period), solved by backward induction where each stage's combinatorial decision is relaxed to a continuous program and mapped back to an integral plan by dependent rounding, and evaluated on real transmission topologies from the PowerGraph benchmark (IEEE24, IEEE39, IEEE118, and the UK Transmission System) with cascading-failure physics. The scientific risk is concentrated in one place: rounding a fractional plan at an early stage can destroy the equilibrium logic of later stages, a failure mode flagged as open in the relaxation literature. Our core contribution is a subgame-safe rounding procedure that provably bounds this damage, plus the first empirical accounting of whether equilibrium defense plans are even economically viable on real grids.

Core Claim

The claim has three parts. First, methodological: in a three-stage extensive-form defense game where the defender's stage-one hardening choice is a "pick $k$ of $n$ links" decision, one can relax $x \in \{0,1\}^n$ to the unit hypercube, solve each stage by backward induction on the relaxed game, and round the fractional plan with swap rounding — the pairwise mass-transfer scheme that keeps $\sum_i x_i$ exactly at the budget — while provably preserving the follower's incentive to remain in the solved subgame. Second, economic: replacing unitless link costs with calibrated capital and operational costs changes the equilibrium qualitatively, and the deliverable is a regime map of when subgame-perfect hardening has positive net present value versus when "do nothing and insure" dominates. Third, empirical: on real grid topologies the rounding loss in defender utility is small in practice — we expect single-digit percent, mirroring how Wilder's EQUATOR achieves utility "within 4-8% of the global optimum" despite a worst-case guarantee of only $(1-1/e)^2 \approx 0.39$ — even though the worst-case bound must be looser in the sequential setting.

The safety mechanism adapts the Best-Response-Value bounds of Ling and Brown's safe subgame search. If $V^{\mathrm{LP}}$ is the defender's value from the relaxed backward induction and $\hat{x}$ the rounded plan, we target a guarantee of the form

$$V(\hat{x}) \;\geq\; V^{\mathrm{LP}} - \Delta_{\mathrm{round}} - \Delta_{\mathrm{slack}},$$

where $\Delta_{\mathrm{round}}$ is the per-stage rounding loss (zero in expectation for the multilinear stage objectives, as swap rounding preserves marginals) and $\Delta_{\mathrm{slack}}$ is the follower-payoff slack needed so that rounding does not push the attacker's best response outside the subgame we solved. The theory task is proving $\Delta_{\mathrm{slack}}$ can be set without re-solving the whole tree, by propagating follower value bounds downward as in safe search.

Research Program

Three components. The first is the game formulation. We adopt the Chen–Touati–Zhu three-stage structure (design $\to$ attack $\to$ recover) but make the payoffs techno-economically honest in the sense demanded by the economic-viability literature: hardening carries a per-link capital cost and recurring operational cost; attack damage is computed by the AC cascading-failure simulation shipped with PowerGraph, valued at the demand-not-served quantity it reports; recovery carries a time-dependent cost. This directly addresses the gap that Chen et al. treat link cost as a single static constant, and it imports the multi-dimensional cost accounting that Khorramfar et al. demonstrate at bulk-system scale but in a completely non-adversarial planning model. We also take seriously the adoption question raised by applied work like Ma et al.'s Rankine-cycle retrofit, where technical savings stalled without a payback analysis: every equilibrium plan we output comes with a payback period and net present value, and the "do nothing, buy insurance" alternative is modeled as an explicit outside option in the spirit of the deterrence-backup-insurance trade-off analyzed by Yin, Sarabi, and Liu.

The second component is the solver. Backward induction proceeds stage by stage; at each stage the combinatorial decision is relaxed to a continuous program over $[0,1]^n$ with a hard budget constraint, solved by standard convex tooling, and mapped back by swap rounding under the follower-value safety constraints described above. This is where we depart from all existing work. Marchesi et al.'s QPSE branch-and-bound uses LP relaxations but forces integrality by branching, which is exactly why it stalls at thousands of tree nodes; Ling and Brown use MILP bounding but no rounding theory; Wilder's EQUATOR uses swap rounding but only in simultaneous zero-sum games where the non-submodularity of sequential minimax objectives never arises. No published result found on Lacuna applies dependent rounding inside an extensive-form sequential equilibrium computation; that absence is the technical heart of the proposal. We will also test whether tremble-based perturbations in the $\xi$-perturbation style of Marchesi et al. are needed to make the rounded solutions stable, or whether safety slack alone suffices.

The third component is the empirical platform. We instantiate the game on the four PowerGraph topologies, using its cascade simulator for attack outcomes and its demand data for lost-load valuation, and we reuse its synthetic UAV-style small instances (the $n = 10$, $C_D = 1/20$, $C_A = 1/8$, $\tau = 0.3$, $T_R = 0.2$ regime from Chen et al.) as a correctness ground truth where exact backward induction is still feasible.

Proposed Experiments

Experiment 1 is the correctness check: on synthetic instances up to roughly 15 nodes, compare our rounded-backward-induction value against exact SPE from exhaustive backward induction. Success is a measured optimality gap below 5% with 100% budget feasibility, and a count of how often rounding triggers subgame unsafety (detectable when the attacker's realized best response leaves the solved subgame) below a few percent, with the safety slack catching the rest.

Experiment 2 is the scalability check: on IEEE39, IEEE118, and the UK Transmission System, run our solver against the baselines below under equal compute and tuning budgets, measuring wall-clock time and defender net payoff against a best-responding attacker. There is no published exact-SPE runtime at this scale — no reported result found on Lacuna for sequential equilibrium computation on any PowerGraph topology — so the comparison is against relaxation-based and heuristic baselines.

Experiment 3 is the economic regime map: sweep capital cost per hardened link and recovery agility, and chart where the subgame-perfect hardening plan has positive net present value versus where the insurance/do-nothing option dominates. The Chen et al. stylized analysis predicts minimal-tree topologies when recovery is agile (their optimal recovery duration was approximately 0.25 in their units); we test whether calibrated, asymmetric, physically grounded costs move that boundary. This is the experiment that speaks directly to the economic-viability gap: it answers, per grid and per cost regime, whether the game-theoretically optimal defense is one an operator could actually afford.

Baselines

The do-nothing reference point is a grid with no hardening, where the attacker best-responds to the bare topology and the defender absorbs cascading losses (with an insured variant in which losses are transferred at a premium, following the defender-insurer structure of Yin et al.). Any defense plan must beat this on net present value to be worth discussing. The strongest exact competitor is exhaustive backward induction in the style of Chen, Touati, and Zhu, which yields the true SPE on instances small enough to enumerate; beating it means matching its defender value within the proven rounding bound while running where it cannot. The strongest scalable competitor is EQUATOR (Wilder), a multilinear-relaxation-plus-swap-rounding method that solved "1,000-node graphs in seconds where baselines timed out" and stayed within 4-8% of optimum in practice; we run it by collapsing our sequential game into a static zero-sum matrix over hardening plans and attack sets, with identical topologies, cascade simulator, and compute budget. Beating it means materially higher defender net payoff under a sequentially-reacting attacker at comparable runtime, since EQUATOR's guarantees do not cover commitment dynamics or general-sum payoffs. A commercial-MILP baseline (full-game integer program solved offline in Gurobi) is included with a matched wall-clock cap, given that Ling and Brown report full-game solvers failing to converge within "1,000 seconds" on two-stage games where safe search succeeded in "100 seconds". Finally, the key ablation replaces swap rounding with independent coin flips at the defender's marginals; the prediction, grounded in the standard failure analysis of independent rounding, is random budget violations and occasional catastrophic subgame departures, isolating dependent rounding as the ingredient that matters.

Why not just…?

Why not just model it as a static zero-sum game and use EQUATOR? This is the most serious alternative, and EQUATOR is genuinely fast and near-optimal in its own setting. Two pieces of evidence say the sequential structure is not free to discard: Paarporn et al. prove that pre-committed resources in a multi-stage lotto game are worth exactly half of real-time ones, so collapsing stages systematically misprices hardening; and Wilder's own analysis shows the minimax objective stops being submodular-friendly outside static zero-sum settings, which is why his guarantees do not transfer. The decisive test is in our Experiment 2: if EQUATOR-on-the-collapsed-game matches our defender payoff on real topologies, the sequential machinery is unjustified and we will say so.

Why not just compile the whole game into a big MILP and let Gurobi solve it? On paper this is simplest, and for small formulations it will work — which is why we use it as a baseline rather than dismissing it. The evidence against it at scale is Ling and Brown: on 8-card Leduc Hold'em, offline MILP solvers "failed to even construct a model within three hours." Grid defense games with per-link hardening variables over a 118-bus or UK-scale network will have comparable or worse model sizes. We still run it with a fair time budget, because if a tight formulation makes MILP viable at IEEE118 scale, that is a finding worth reporting.

Why not just use greedy hardening (best value-per-pound link first)? Greedy is the practitioner's default and must be beaten on merit. In adversarial settings Wilder shows greedy is fragile under worst-case scenario selection, and in a different domain Gravin et al. report greedy needing "27 hours" where a continuous relaxation finished in "45 seconds." Neither result settles greedy's fate on grids directly, so greedy runs head-to-head in every experiment with the same cascade simulator; the specific failure we predict is that greedy concentrates hardening where marginal cascade reduction is highest, leaving cut-sets exposed to a sequentially-optimizing attacker.

Why not just do non-adversarial techno-economic planning, as Khorramfar et al. already do? Their JPoNG co-optimization is exactly the kind of rigorous cost modeling we import, but it assumes a passive environment. Chen et al. show that efficiency-optimized networks are structurally exposed to adversaries who target critical cut-sets, while over-building redundancy is economically prohibitive. The honest caveat: if attack costs are high enough that no rational attacker strikes, the non-adversarial plan and our equilibrium plan coincide, and our regime map (Experiment 3) is precisely the instrument that locates that boundary rather than assuming it away.

Decisive Checks

The proposal stands or falls on three numbers. The rounding-versus-exact gap on small instances must be small (target: under 5% defender-value loss, zero budget violations) — if the sequential setting makes rounding loss catastrophic where the static setting's is 4-8%, the core claim is wrong. The subgame-safety violation rate must be near zero with slack active, because a plan the attacker can trivially push off-path is not an equilibrium at all. And the economic regime map must be non-degenerate: if positive-NPV hardening and the do-nothing option are separated by realistic cost ranges on at least the UK grid, the exercise delivers an answer operators could act on; if the viable region is empty or covers everything, that is itself the finding — but the methodological contribution, subgame-safe dependent rounding for extensive-form games, remains the first of its kind either way.