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).
Game-theoretic analyses of cyber defence often compute equilibria of games whose payoffs exist only as the output of a simulator. Iterative equilibrium-finding methods grow a set of attacker and defender policies and need the payoff of every attacker--defender pair, so they are bottlenecked by payoff estimation: each payoff costs many simulator runs. We introduce Regret-Weighted Payoff Sampling (RWPS), which spends a fixed simulation budget on the payoffs the equilibrium actually depends on and predicts the rest with a model trained on every payoff measured so far. Standard error bounds for estimated games are driven by the worst-estimated payoff, so they cannot credit an estimator that is inaccurate only where accuracy does not matter. We prove a bound that weights payoff errors by the opponent's equilibrium strategy, a certificate that can be computed from simulated payoffs alone, and a condition under which errors in the predicted payoffs cannot change either player's regret. On three synthetic general-sum games, one of them a Colonel Blotto game of military resource allocation, the new bounds are four to six times tighter than the standard one, and RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget. On two cyber-defence simulators, CyGym and a new game whose hosts are LLM agents exposed to prompt injection, it gives the least exploitable equilibria at the smallest budgets.
Michael Lanier, David Farmer, Yevgeniy Vorobeychik
Computing equilibria in high-dimensional continuous games requires learning and representing rich, multi-modal strategy distributions, something conventional neural policies struggle to achieve. Diffusion models offer a natural solution, but standard diffusion training requires direct samples from a fixed target distribution, which are generally unavailable under iterative game-solving updates. We propose a diffusion-based framework for equilibrium computation that enables diffusion-based variants of Online Mirror Descent (OMD) and Fictitious Play (FP). Our approach derives a reweighted score-matching objective that trains diffusion policies without requiring direct samples from each updated policy. Our main method, DiffNash, combines the fast convergence of OMD with the sample efficiency of FP by reusing past actions through a replay buffer. To correct the resulting distribution shift from sample reuse, we derive an unbiased estimator of the difference between current and past policies' Evidence Lower Bounds, whose exponential provides a tractable proxy for the corresponding importance weight without evaluating diffusion likelihoods. We evaluate our approach on forest protection games and continuous Colonel Blotto games, reducing the Nash gap over the strongest baseline by 35.6% and 24.7%, respectively, with minimal hyperparameter tuning.
Haichuan Wang, Anagha Satish, Jiale Zheng +4
Harvard University · Massachusetts Institute of Technology · Georgia Institute of Technology
Nash equilibria provide a principled framework for modeling interactions in multi-agent decision-making and control. However, many equilibrium-seeking methods implicitly assume that each agent has access to the other agents' objectives and constraints, an assumption that is often unrealistic in practice. This letter studies a class of asymmetric-information two-player constrained games with decoupled feasible sets, in which Player 1 knows its own objective and constraints while Player 2 is available only through a best-response map. For this class of games, we propose an asymmetric projected gradient descent-best response iteration that does not require full mutual knowledge of both players' optimization problems. Under suitable regularity conditions, we establish the existence and uniqueness of the Nash equilibrium and prove global linear convergence of the proposed iteration when the best-response map is exact. Recognizing that best-response maps are often learned or estimated, we further analyze the inexact case and show that, when the approximation error is uniformly bounded by ε, the iterates enter an explicit O(ε) neighborhood of the true Nash equilibrium. Numerical results on a benchmark game corroborate the predicted convergence behavior and error scaling.
Mahdis Rabbani, Navid Mojahed, Shima Nazari
Department of Mechanical and Aerospace Engineering, University of California, Davis, One Shield Ave, Davis, CA 95616.