CS Paper Radar

Efficient Nash Equilibrium Computation for Cybersecurity Games

Michael Lanier, David Farmer, Yevgeniy Vorobeychik

cs.GT cs.AI ·submitted 2026-09-16 20:29 UTC · v2
theory

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Efficient Equilibrium Computation in Colonel Blotto Games

cs.GT cs.DSecon.TH ·2026-11-03 ·Martin Bichler, Abheek Ghosh
similarity 0.67
Abstract · 75 pages

Colonel Blotto is a fundamental resource-allocation game in which two players divide their budgets across battlefields, and the higher allocation on each battlefield wins its value. The problem of computing an equilibrium efficiently has remained unresolved for its classical continuous version with arbitrary budgets and with values that may vary across battlefields but are the same for both players. We give a fully polynomial-time approximation scheme that computes an $\varepsilon$-Nash equilibrium in time polynomial in the input length and $1/\varepsilon$, and nearly linear in the input length for fixed $\varepsilon$. For sufficiently balanced budgets and battlefield values, we also compute exact equilibria in linear time.

0.13

Networked Multi-Resource Defense Capabilities in a General Lotto Game

cs.GT cs.CReess.SY ·2026-08-28 ·Faezeh Shojaeighadikolaei, Keith Paarporn
publishedbenchmark similarity 0.66
Abstract · 9 pages, 3 figures, Accepted for presentation at the 65th IEEE Conference on Decision and Control (CDC 2026)

Ensuring the security of complex systems involves the strategic allocation of defensive resources to prevent various types of attacks from succeeding. A defender often has multiple types of defensive assets at its disposal, where it must decide how to optimally deploy their heterogeneous capabilities across different attack types. In this paper, we formulate a multi-resource allocation problem in the form of a General Lotto game where a defender possesses various types of resources. A feature that we introduce is that their individual effectiveness against different types of attacks is characterized by a network weight matrix. In our analysis, we derive upper and lower bounds on the performance of the defender, and provide numerical evidence suggesting that they are tight. For the case of two attack types, we analytically prove that the bounds coincide, establishing an exact equilibrium characterization. We then numerically compare our proposed networked multi-resource architecture to an independent-defense benchmark from the existing literature. These results highlight fundamental and tractable structures underlying multi-attack-type defense problems.

0.21

Epsilon-Nash Equilibria in History-Dependent SA-MDPs

cs.GT cs.CR ·2026-09-16 ·Brandon Gary Kaplowitz, Dominik Bohnet Zurcher, Akash Agrawal, Tala Jafari, Christian Schroeder de Witt +1 more
theory similarity 0.66
Abstract

We study state-adversarial Markov decision processes (SA-MDPs) as games of observation-space attacks: at each step, an agent selects an action from a received observation while an adversary$\unicode{x2014}$who knows the true state the agent is in$\unicode{x2014}$chooses a perturbed observation within a state-dependent proximity set. While existing work focuses on Markovian policies, we develop a solution concept and computational approach for SA-MDPs under history dependence. History dependence can materially change equilibrium outcomes and can force both the agent and the adversary to adapt their strategies. First, we prove the non-existence of universal (agnostic of the initial state distribution) history-dependent equilibrium policies. Our main result presents the first algorithmic route to computing $ε$-approximations of initial-state dependent equilibria. We do so by reducing SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game. We test our algorithm on small analytically verifiable games and show that it scales to larger, more realistic benchmarks, including Atari Freeway rollouts with a 12-period ahead horizon.

0.21

Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

cs.LG cs.GT ·2026-09-28 ·Yuheng Zhang
similarity 0.66
Abstract

We study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. We develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent $\mathcal{O}(\log^2 T)$ Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee under bandit feedback from $2\times2$ games to arbitrary finite dimensions. To handle nonunique equilibria, we construct a reference strategy that leaves room for local adjustments. We order independent payoff differences by estimation accuracy and scale these adjustments by uncertainty, allowing the learner to exploit the opponent's imbalance to offset estimation costs. Our result thus shows that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.

0.13

Security Games on Series-Parallel Attack Graphs with Adaptive Attackers

cs.GT ·2026-08-21 ·Russell Kai Min Tan, Hui Han Chin, Chun Kai Ling
similarity 0.65
Abstract · 68 pages, 10 figures. Added examples and updated acknowledgements

We study security games on attack graphs, where an adaptive attacker seeks to reach a target by sequentially attempting stochastic controls along the current attack frontier, while a defender allocates limited resources across controls to delay compromise. The attacker may choose among exponentially many attack routes and freely pivot between them as successes and failures are observed, yielding an exponentially large space of contingent attack policies. For any fixed defender allocation, we show that an optimal attacker policy on a two-terminal series-parallel attack graph is an index policy: at each step, the attacker selects an available control with the largest value of an extension of the classical Gittins index. The indices and the resulting attacker best response can be computed in polynomial time, without explicitly enumerating attack paths or contingent policies. To the best of our knowledge, this is the first optimal index characterization for adaptive attackers in security games on general series-parallel attack graphs. We further develop efficient algorithms for computing the attacker's exact utility and an exact defender subgradient, enabling deterministic first-order optimization of defensive resource allocations without sampling attack trajectories. Our framework strictly generalizes prior approaches restricted to parallel chains and out-trees, while exploiting the compositional structure of series-parallel graphs to support interpretable attacker policies and parallel computation across independent subgraphs. Experiments demonstrate that the resulting methods scale substantially better than naive explicit-state approaches while producing effective defensive allocations.

0.47

Defensive Sufficiency in a Stackelberg Model of AI Security

cs.CR cs.AI ·2026-10-07 ·Subhabrata Majumdar, Rajlakshmi Chavan
similarity 0.64
Abstract · 27 pages, 3 figures, 1 table

Feedback from automated testing, human red teaming, and incident response can strengthen an AI system's defenses when discovered failures lead to effective repairs. We study when this feedback process provides sufficient protection and when investing in it is economically worthwhile. We begin by showing that an attack surface composed of finite number of inputs is defended with probability 1 if every unresolved attack has a persistent chance of discovery, repairs are effective, and subsequent updates preserve earlier protection. We derive completion-time bounds and extend the analysis to growing attack surfaces, repairs that generalize across related attacks, and multiple discovery mechanisms. These results distinguish eventual protection against each fixed attack from complete protection at a single time. We then formulate a defender-led Stackelberg game in which the defender invests in proactive discovery and reactive repair, anticipating the attacker's choice of search effort. We characterize the least-cost allocation that deters attack and the equilibrium regimes in which the defender funds neither capability, one capability, or both. Numerical experiments illustrate these regimes and show how faster repair can reduce compromise duration without reducing compromise probability.

0.35

When Are We Near Nash? Certifying Solutions in General-Sum Games

cs.GT cs.AIcs.MA ·2026-10-21 ·Boning Li, Longbo Huang
benchmarkcode/data similarity 0.64
Abstract · 35 pages, 5 figures

Heuristic solvers for general-sum extensive-form games produce a stream of iterates, and practice reports the NashGap of the returned profile. We ask what a solver can know about its own iterates from the regret accumulators and the terminal-distribution accumulators its updates already maintain. In two-player games the NashGap of a weighted average strategy equals, at the maximizing player, the weighted external regret plus a signed value correction. Bounding the regret by the running counterfactual-regret accumulator gives an online certificate whose cost per checkpoint is linear in the number of terminal histories. The certificate stays sound under alternating updates and in games with three or more players. The mismatch between what alternation evaluates and what the averages record enters as one signed comparator term, maximized in a single backward pass per player whose comparator weight is nonzero. The bound is read off the regret state, with no best response against the average. Run a portfolio of training-free regret-matching solvers, output the iterate with the smallest certificate, and verify that iterate once. On the benchmark's biased Leduc family a pool of sixteen training-free solvers, seven original and nine recent variants, solves $89\%$ of the $64$ instances at threshold $10^{-5}$ this way, matching the trajectory-minimum union of the solvers. The same protocol solves $92\%$ of the $64$ pre-registered held-out instances and $89\%$ again on a third set of $64$ instances that no earlier stage used. The zero-best-response certificate certifies all $57$ in-sample solves and all $57$ fresh ones, and $58$ of the $59$ held-out ones. Its exact-comparator refinement certifies every solve in the three sets. The certificate states both and attributes its bound. Code is available at https://github.com/lbn187/CertNE.

0.24

Games Over Observation Spaces in Multi-Agent Capture the Flag

cs.GT ·2026-09-05 ·Mae Frost, Michael Amir, Shaunak D. Bopardikar
published similarity 0.63
Abstract · 21 pages, 5 figures, To be published as a conference paper in the 17th International Conference on Game Theory and AI for Security (GameSec …

We consider a multi-agent Capture the Flag (CtF) scenario in a graph-based environment, where a team of attackers seeks to reach designated flag vertices while a defending team attempts to intercept them. In our setting, both teams operate using decentralized heuristic policies. While the attacking team may choose its heuristic from a diverse library of policies, the defense is restricted to playing a single fixed policy. To overcome this limitation, a centralized defense oracle strategically restricts the portion of the graph visible to each of its agents in order to elicit a wider range of emergent behaviors from its fixed policy. We formalize this interaction as a two-player zero-sum game, where the attacker reasons over its library of heuristics and the defense reasons over the combinatorial space of visibility profiles. To solve this intractably large game, we propose a Double Oracle algorithm to find approximate empirical equilibria, and we empirically validate that observation manipulation can improve the defense's performance.

0.34