BRAID: Learning Equilibrium Maps in Interdependent Security Games via Weight-Tied Iterative Graph Neural Networks

Elnaz Nowrouzi; Zhiqun Zuo; Xueru Zhang; Mohammad Mahdi Khalili

Source-linked AI summary

BRAID: Learning Equilibrium Maps in Interdependent Security Games via Weight-Tied Iterative Graph Neural Networks

Elnaz Nowrouzi, Zhiqun Zuo, Xueru Zhang, Mohammad Mahdi Khalili

arXiv:2608.14856v1Aug 14, 2026cs.GTcs.LG

TL;DR

Computing equilibria and their parameter sensitivities in interdependent security games can require costly iterative best-response solves. BRAID learns an amortized equilibrium map with a weight-tied iterative graph neural network, achieving fast predictions and meaningful sensitivity recovery across utility specifications and network sizes.

Problem
Interdependent security games require costly equilibrium computation and responses to parameter perturbations for operational analysis.
Method
BRAID learns an amortized equilibrium map using weighted SUM message passing and a shared GRU update derived from damped best-response dynamics.
Results
BRAID predicts equilibria with relative error below 0.5% for log-linear and quadratic-cost models, below 2% for log-CES, and recovers cost and edge-weight sensitivities without labels.
Takeaways & Limitations
BRAID provides a fast equilibrium solver that also recovers local responses to cost and edge-weight perturbations across the evaluated IDS utility specifications.
Takeaways & Limitations
Edge-weight sensitivities remain the hardest case, especially for log-CES with ρ = 0.7.

Abstract

from arXiv · show

Computing Nash equilibria in interdependent security (IDS) games on networks is computationally expensive: best-response dynamics may need hundreds of iterations per instance, and downstream tasks such as auditing, stress-testing, and incentive design often require repeatedly re-solving the game under parameter perturbations. We propose BRAID, a Best-Response Amortized Iterative Dynamics model that uses a weight-tied iterative graph neural network to learn a direct map from game parameters to Nash equilibrium effort profiles, replacing iterative best response computation with a single forward pass that is up to 43X faster per instance. BRAID is derived from the best-response fixed-point structure of IDS games: its SUM aggregation reflects additive neighbor coupling, and a weight-tied gated recurrent unit (GRU) mirrors a damped best-response update. The same architecture applies across IDS specifications that vary investment-cost curvature and neighborhood aggregation, including log-linear, quadratic-cost, and log constant-elasticity-of-substitution (CES) utilities. Beyond equilibrium prediction, BRAID also recovers how equilibrium efforts change under perturbations to game parameters, including costs and network edge weights. We make this sensitivity recovery an explicit evaluation target and introduce two training strategies, interior-equilibrium training and input-noise regularization, that improve the local behavior of the learned equilibrium map without using sensitivity labels. Experiments show that BRAID effectively predicts Nash equilibria and recovers equilibrium sensitivities across utility specifications and network sizes.

1 Introduction

BRAID amortizes Nash-equilibrium computation in interdependent security games with a weight-tied iterative graph neural network derived from damped best-response dynamics. It also explicitly evaluates and improves recovery of equilibrium sensitivities to costs and edge weights without sensitivity labels.

Sensitivity-aware learning and evaluation: BRAID evaluates sensitivity recovery as an explicit target for how equilibrium efforts respond to perturbations in costs and edge weights.The motivation is that low pointwise equilibrium error does not ensure accurate local responses for what-if analysis, key-player identification, or mechanism design.
Method: BRAID learns an equilibrium map with a weight-tied iterative GNN, replacing per-instance best-response dynamics with a single-forward-pass amortized solver.Its SUM aggregation captures weighted neighbor effects, while a shared GRU emulates repeated best-response updates.
Method: 43× faster inference per instance is achieved by BRAID than iterative BRD.The comparison is reported for the amortized NE solver in Table 4.
Robustness across utility specifications: BRAID applies the same architecture and training recipe to log-linear, quadratic-cost, and log-CES IDS utilities.These specifications vary investment-cost curvature and neighborhood aggregation; log-linear is the ρ →1 limit of log-CES.
Robustness across utility specifications: Relative equilibrium error is below 0.5% for log-linear and quadratic-cost models, below 2% for log-CES, with R2 > 0.999 across all settings.The log-CES model is identified as the more challenging specification.
Sensitivity-aware learning and evaluation: 2–7% relative error is achieved for cost sensitivities and 11–17% for edge-weight sensitivities on most settings, without ground-truth sensitivity supervision.Errors rise to 19–31% for the most curved log-CES utility, ρ=0.7; interior-equilibrium training with input-noise regularization improves local smoothness.

2 Related Work

Prior work spans exact but computationally hard equilibrium computation, inverse game-learning methods, and graph-based analyses of network games. BRAID is positioned as a graph-aware, continuous-action, single-pass equilibrium predictor that addresses a gap left by existing learned solvers.

Computing Nash Equilibria: Exact equilibrium algorithms include Lemke–Howson and support enumeration, but Nash equilibrium computation has exponential worst-case complexity and is PPAD-complete even for two-player games.RENES uses a GNN over an α-rank response graph and still requires an inner solver run.
Computing Nash Equilibria: Inverse-learning methods recover games or network structure from observed behavior rather than predicting equilibria from known games.MINE recovers strategies and latent rewards from observed networks, while Rossi et al. learn network structure from observed equilibrium actions.
Network Games and GNNs for Optimization: Network-game theory shows that equilibrium behavior depends on topology, including structural position, strategic interaction, information, and the network’s lowest eigenvalue.The cited studies identify key players, characterize linear-bestreply equilibria through the lowest eigenvalue, and analyze how position and information shape behavior.
Comparison with Prior Learned Solvers: Table 1 compares learned solvers by game type, graph awareness, action space, solution concept, and single-pass inference; only NES is single-pass, while MINE solves the inverse problem.BRAID is designed to fill the gap in combining these properties for direct equilibrium prediction.

3 Problem Formulation

Section 3 formulates network security games in which agents choose nonnegative efforts under directed security spillovers and heterogeneous effort costs. It defines Nash equilibrium and the amortized-learning objective, while considering utility specifications that vary cost curvature and neighbor aggregation.

Network Security Game: Each of n agents chooses effort e_i ≥ 0 in a directed network encoded by X, where X_ii = 1 captures self-benefit and X_ij ≥ 0 captures neighbor influence.Each agent also has a positive cost parameter c_i controlling the cost of security effort.
Network Security Game: A Nash equilibrium is an effort profile in which every agent’s effort is a best response to the others’ efforts.The best-response map maximizes each agent’s security utility net of effort cost over nonnegative effort levels.
Three Utility Instances: The study examines three IDS utility specifications that retain own-investment benefits and positive neighbor spillovers while varying investment-cost curvature and neighboring-effort aggregation.U1 is an additive linear-cost baseline, U2 adds quadratic cost, and U3 uses CES aggregation to vary neighbor substitutability.
Three Utility Instances: For the CES specification, ρ ∈ {0.3, 0.5, 0.7} controls neighbor substitutability, with ρ approaching 1 recovering the log-linear case.Lower ρ makes one neighbor’s protection less able to substitute for others’ protection.
Research goal: The research goal is to learn an amortized solver that maps an IDS instance’s parameters directly to its Nash equilibrium, predicting e* by f_θ(X, c).The equilibrium is denoted e*(X, c), while the model prediction is ˆe = fθ(X, c).

4 BRAID: Weight-Tied Iterative GNN

BRAID is a weight-tied iterative GNN that aligns graph message passing and gated updates with the fixed-point structure of IDS best-response dynamics. By unrolling a fixed number of shared rounds, it replaces instance-dependent convergence with a bounded single forward pass for equilibrium prediction.

Why message passing fits IDS games: BRAID’s inductive bias is motivated by IDS topology: equilibrium effort depends on private costs and structural network position, with edge weights expressing strategic dependencies.A flat predictor does not directly encode these graph-mediated dependencies.
Architecture rationale: BRAID uses edge-weighted SUM aggregation to represent the additive neighbor coupling in IDS best responses.SUM preserves additive multiplicity information that mean or max aggregation can discard.
Architecture rationale: GRU gating provides a learned analogue of the damped best-response update, while shared parameters across K rounds mirror repeated application of the same operator.The learned update cell replaces the analytic best-response map while retaining the iterative update structure.
Forward computation: BRAID’s K weight-tied rounds are isomorphic to K damped best-response steps, replacing the inner convergence loop with a fixed, bounded-depth forward pass.The output head decodes the final node states into positive effort predictions using Softplus.
Properties and complexity: The architecture is permutation equivariant, has agent-independent parameter count for fixed d and K, and costs O(K(|E| d + n d^2)) per forward pass.For fixed hidden dimension and unroll depth, each round costs O(|E| d + n d^2).

5 Training

Training uses varied graph-game instances and damped best-response dynamics for ground truth, while emphasizing interior equilibria and input-noise regularization to improve local equilibrium-map behavior. The model is trained with expected prediction loss and evaluated independently for fixed-point quality.

Dataset Generation: Training instances use symmetrized Erdős–Rényi graphs, varied coupling targets, and weak/strong edge-weight mixtures so expected neighbor coupling matches the target.Coupling targets are sampled from U(0.3, 1.2), with 60% weak and 40% strong edge weights.
Ground-Truth Dynamics: Ground-truth equilibria are generated with damped best-response dynamics, initialized from small random efforts and stopped when the infinity-norm change falls below tolerance.The procedure applies damping α after each best-response update and returns either a converged or non-converged result.
Interior-Equilibrium Training: Interior-equilibrium training avoids boundary-heavy datasets because they can produce low prediction error but poor local behavior and ill-defined sensitivity recovery.The training and evaluation regime is chosen so equilibria remain interior.
Input Noise Regularization: Input-noise regularization adds Gaussian noise with standard deviation 0.01 to node and edge features during training, encouraging smooth predictions without sensitivity labels.Perturbed edge weights are clamped to remain non-negative, creating a data-space smoothness prior.
Objective: The objective minimizes expected per-agent mean-squared prediction error, while best-response gap is monitored independently rather than added as a training penalty.This separates prediction fitting from fixed-point satisfaction measurement.
Optimization: Optimization uses AdamW with base learning rate 10^-3, weight decay 10^-5, gradient clipping at 1.0, plateau-based learning-rate reduction, and early stopping.Training runs for up to 300 epochs, with adjusted settings for larger games.

6 Sensitivity Analysis

BRAID’s sensitivity analysis tests whether its learned equilibrium map captures local responses to perturbations in costs and network edge weights, not merely pointwise equilibrium accuracy. It uses symmetric finite differences with verified, warm-started best-response solutions and evaluates training strategies intended to improve local smoothness.

Motivation: Sensitivity recovery evaluates BRAID’s local equilibrium responses to perturbations in costs and directed edge weights, because low pointwise prediction error alone may not ensure accurate sensitivities.These sensitivities support auditing, stress testing, and intervention design.
Finite-difference method: Symmetric finite differences compare the true map e∗(γ) with BRAID’s learned map fθ(γ) at γ0 ± εu_j for each scalar game parameter γ_j.The method requires accuracy that remains small and smooth throughout the perturbation neighborhood, not only at γ0.
Training strategies: Interior-equilibrium training keeps targets away from non-smooth boundary responses, while input-noise regularization discourages spurious local oscillations without using sensitivity labels.Both strategies aim to improve the learned equilibrium map’s local behavior.
Evaluation protocol: 10^-2 is the finite-difference step ε; ground-truth sensitivities require two additional BRD solves per parameter, whereas model sensitivities require two additional forward passes.Sensitivity metrics use sampled test games because ground-truth computation is expensive, while equilibrium and perturbation errors use the full held-out set.
Verification: Warm-started, re-verified BRD solves keep perturbed equilibria in the same basin and discard failed equilibrium checks, so finite differences measure local sensitivities rather than jumps between equilibria.The learned map is evaluated with one forward pass at each perturbed parameter value.

7 Experiments

BRAID achieves accurate, stable equilibrium predictions across utility specifications and agent counts, while recovering local sensitivities and substantially reducing computation relative to damped best-response dynamics. Its evaluations use verified BRD equilibria, perturbation tests, sensitivity errors, and runtime comparisons.

Evaluation Protocol: Evaluation averages equilibrium and perturbation errors over 1,500 held-out games per agent count, using converged, re-verified damped best-response dynamics as ground truth.Best-response gap is also monitored as an independent fixed-point check.
Equilibrium Prediction: Relative equilibrium error stays below 0.5% for log-linear and quadratic utilities and below 2% for CES utility across agent counts.The same architecture, training loop, and sensitivity pipeline are used across utilities; only the best-response module differs.
Equilibrium Prediction: Perturbation errors remain nearly identical to nominal equilibrium errors for log-linear and quadratic utilities and stay in the same order for CES utilities.Perturbations use γ0 ± ∆uj with ∆= 10^-2, supporting accuracy in the local neighborhoods used for sensitivity recovery.
Training dynamics and Per-agent accuracy: Training error falls from roughly 58% at initialization, crosses 5% within about 40 epochs, and converges to ∼0.5% without divergence or overfitting.At n = 50, NodeACC reaches 98.0%, 99.7%, and 100% at tolerances τ = 5, 10, and 20%, respectively.
Sensitivity Recovery: Cost sensitivities are recovered with 2–7% relative error, whereas edge-weight sensitivities range from 11–17% for most utilities and 19–31% for CES with ρ = 0.7.Edge sensitivities are consistently harder than cost sensitivities, with the most curved CES case hardest throughout.
Computational Performance: 2.6–4.6 ms GPU latency yields a 25–43× per-instance reduction versus BRD, while CPU speedups reach 5.5–34×.The comparison uses log-CES with ρ = 0.7, BRD’s hardest utility; BRAID reaches ∼105 games/s at n = 3 under batching.

8 Conclusion

BRAID uses a weight-tied iterative graph neural network to predict Nash equilibria in interdependent security games across multiple utility specifications. Its main limitations are difficult edge-weight sensitivities and open extensions to richer utilities and game settings.

Contributions: BRAID combines weighted SUM aggregation with a shared GRU update to mirror damped best-response dynamics.The architecture is derived from the best-response fixed-point structure.
Contributions: The same architecture and training recipe apply to log-linear, quadratic-cost, and log-CES utilities.BRAID achieves low equilibrium error across agent counts.
Limitations and future work: Edge-weight sensitivities remain the hardest case, particularly for log-CES with ρ = 0.7.The authors motivate richer edge representations and edge-focused regularization to address this limitation.
Limitations and future work: Future extensions include behavioral probability-weighting utilities and Stackelberg or repeated-game settings.The conclusion also frames BRAID as complementing iterative methods with fast amortized equilibrium predictions and informative local sensitivities.