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.
Figures & tables
Method
Game type
Graph-
Action
Solution
Single-
aware
space
pass
NES [ 28 ]
Normal-form
×
Discrete
NE/CE/CCE
✓
N-FPN [ 12 ]
Contextual/convex
×
Cont.
NE
×
Exp3-IX rl [ 37 ]
Stochastic
×
Discrete
CCE
×
MINE [ 32 ]
Network (inverse)
✓
—
—
—
BRAID
Network (forward)
✓
Cont.
NE
✓
Table 1: Comparison of learned equilibrium prediction methods along the five axes defined in the text. “Graph-aware” marks an explicit dependence on interaction topology; “Single-pass” marks a prediction produced without an inference-time iterative solve. Entries for prior methods are drawn from their published descriptions.
Figure 1: Architecture of BRAID, our weight-tied iterative GNN. A game instance (X,c) enters as a graph with node features xi=[ci,Xii] and edge weights Xij . A node encoder produces initial states h(0) ; the shared message-and-SUM block and GRU update are then applied for K weight-tied rounds (the recurrence shown by the feedback arrow), so the forward pass mirrors K steps of damped best-response dynamics. A Softplus output head maps the final states to the predicted equilibrium effort profile e^ .
n
p
d
K
lr
bs
wd
3
0.80
64
12
1×10−3
32
1×10−5
30
0.15
128
15
8×10−4
32
1×10−5
50
0.15
256
20
5×10−4
32
1×10−5
100
0.15
256
20
3×10−4
16
5×10−6
200
0.15
256
20
3×10−4
16
5×10−6
Table 2: Graph and model configurations by network size. Graphs are Erdős–Rényi with edge probability p ; (d,K) denote the hidden width and number of weight-tied rounds; lr is the base learning rate; bs the batch size; and wd the weight decay.
Utility
n
Eq. err.
Pert. cost
Pert. edge
∂/∂ci
∂/∂Xij
(%)
(%)
(%)
(%)
(%)
Log-linear
3
0.33
0.32
0.34
4.0
11.6
30
0.35
0.35
0.36
3.5
11.0
50
0.38
0.38
0.39
3.3
11.4
100
0.29
0.35
0.36
3.2
13.2
200
0.27
0.33
0.34
3.0
13.6
Table 3: Equilibrium prediction, perturbation stability, and sensitivity recovery across utilities and agent counts ( Δ=10−2 ). Equilibrium and perturbation errors are averaged over 1,500 test games per n ; sensitivities over a sample of test games per setting. The framework is identical across rows; only the best-response dynamics differ.
Figure 2: Left: test relative error versus training epoch for a representative n=100 model; it drops below the 5% reference (green dashed) within about 40 epochs and converges to ∼0.5% (orange dashed marks 10% ), with no overfitting. Right: per-agent NodeACC curve at n=50 , the fraction of agents predicted within relative-error tolerance τ (a node-level Regression Error Characteristic curve [ 5 ] ); at τ=5,10,20% it reaches 98.0% , 99.7% , and 100% , confirming that accuracy is broadly uniform across agents rather than concentrated in an easy majority.
n
BRD iters
conv.
BRD cpu
BRAID cpu
BRAID gpu
speedup
med (max)
(%)
(ms)
(ms)
(ms)
(CPU / GPU)
3
58 (97)
100
112.1
3.34
2.59
34× / 43×
30
64 (83)
95
128.7
6.41
3.48
20× / 37×
50
59 (73)
90
119.7
13.36
4.40
9× / 27×
100
55 (65)
78
115.1
20.95
4.63
5.5× / 25×
Table 4: Runtime comparison on a single NVIDIA RTX A6000 (CUDA 12.1, PyTorch 2.5.1, PyG 2.6.1) for the log-CES utility ( ρ=0.7 ), the hardest utility for BRD. BRD and BRAID use PyTorch implementations, with BRD vectorized across agents. “BRD iters” reports the median (maximum) number of damped best-response iterations to convergence among converged instances; “conv.” is the fraction reaching the 10−7 tolerance within a 5,000 -iteration budget. Latencies are medians at batch size 1. Speedups are BRD cpu /BRAID cpu (same device) and BRD cpu /BRAID gpu (GPU deployment).