CS Paper Radar

Networked Multi-Resource Defense Capabilities in a General Lotto Game

Faezeh Shojaeighadikolaei, Keith Paarporn

cs.GT cs.CReess.SY ·submitted 2026-08-28 17:37 UTC · v2
publishedbenchmark

Abstract

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.

Comment
9 pages, 3 figures, Accepted for presentation at the 65th IEEE Conference on Decision and Control (CDC 2026)

Closest papers

Nearest neighbours by meaning across the whole index.

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.69
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

Efficient Nash Equilibrium Computation for Cybersecurity Games

cs.GT cs.AI ·2026-09-16 ·Michael Lanier, David Farmer, Yevgeniy Vorobeychik
theory similarity 0.66
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.

0.26

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.65
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

Defensive Sufficiency in a Stackelberg Model of AI Security

cs.CR cs.AI ·2026-10-07 ·Subhabrata Majumdar, Rajlakshmi Chavan
similarity 0.61
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

Deception in Reach-Avoid Game with Unknown Heterogeneous Attackers Speed Information

cs.GT cs.RO ·2026-09-07 ·Xiangkai Wu, Shaolin Tan, Wei Wang, Zhen Han
similarity 0.60
Abstract

This letter investigates a reach-avoid game involving two Attackers and one Defender, where the Attackers aim to maximize the number reaching the target region while the Defender seeks to minimize it. In contrast to conventional complete information formulations, we consider an information asymmetry scenario where the Attackers' heterogeneous maximum speeds are privately known but publicly disclosed to lie within continuous ranges. Existing studies on uncertain speeds, however, have primarily focused on homogeneous settings, whereas heterogeneity extends the uncertainty from a common capability level to the relative capability configuration of the Attackers. To address the resulting capture-order ambiguity over infinitely many possible speed combinations, we establish a critical speed pair framework that characterizes when different capability configurations induce different optimal capture orders, and enables the analysis of the Defender's guessing behavior and the design of information-limiting strategies for the Attackers. We demonstrate that under certain initial conditions, the Attackers can mislead the Defender into making suboptimal decisions through a slow-speed deception strategy, achieving superior payoffs compared to the complete information game. Numerical visualizations reveal the widespread occurrence of such dilemma conditions.

0.20

Forming Alliances in the Fog of War: A General Lotto Perspective

cs.GT ·2026-09-30 ·Edik Hakobyan, Vade Shah, Jason R. Marden
similarity 0.60
Abstract

Agents competing against a common opponent can often gain an edge by forming alliances, but deciding whether to do so is difficult when they lack precise knowledge about their opponent or ally. We study how uncertainty affects opportunities for alliance formation in the coalitional General Lotto game, in which two players compete aganist a shared adversary by allocating their resource budgets over separate sets of valued contests. When all agents know one another's budgets, it is known that a budget transfer from one player to the other can benefit both players. We ask whether such alliances survive when the players know the relevant budgets only up to a multiplicative factor. Under two models, one in which the players are uncertain about the adversary's budget and one in which they are uncertain about each other's budgets, we characterize exactly which games admit a transfer that benefits both players in every game consistent with what they conjecture to be possible. In both models, we show that such robust transfers exist in a set of games of positive measure for every level of uncertainty. These results suggest that alliances can remain worthwhile even when allies are largely in the dark.

0.13

Dynamical low-rank equilibrium computation for stochastic games between advanced persistent threats and moving target defense

cs.GT cs.AIcs.CReess.SY ·2026-09-20 ·Tian Zijian, Zhang He, Chen Xinjie, Wang Wenhai, Liu Xinggao
theorycode/data similarity 0.60
Abstract · Regular Paper, under review at Automatica (submission 26-2265). v2: corrected the utility-loss figure in Experiment 5 (2.3%). This preprint …

Moving target defense (MTD) against advanced persistent threats (APTs) in industrial control systems (ICS) has well-established game-theoretic formulations, but their practical value hinges on equilibrium computation, which faces two gaps: full-rank value iteration is prohibitively expensive at industrial scale, and the resulting defense strategies admit no certified robustness against adversarial perturbations. We first reveal that the attack and defense influence matrices of ICS dynamics are intrinsically low-rank: APTs infiltrate through a handful of entry points and MTD reconfigures only a few components per cycle. Our theory makes four contributions. First, an augmented gradient matrix certifies that the low-rank structure propagates through the non-smooth Bellman operator of the zero-sum stochastic game, so that every Bellman target lies near a low-dimensional subspace and low-rank truncation incurs an explicit error bound (Lemma 1, Theorem 1). Second, we propose the Dynamical Low-Rank Nash Equilibrium algorithm, named DLR-NE, which augments the rank-r search space each iteration, regularizes the core matrix spectrum, and retracts via truncated SVD, and prove that it converges geometrically to a neighborhood whose error decomposes into five physically interpretable sources (Theorem 2). Third, its per-step cost is O(nr^2), a Theta(n/r^2) speedup over full-rank value iteration (Theorem 3). Fourth, a single weight trades accuracy against a certified sensitivity bound of the induced defense strategy under core-matrix perturbations (Corollary 1). Six experiments on a nonlinear power-system testbed confirm each prediction, with 94% parameter compression at 2.3% utility loss. All experimental data and code are publicly available.

0.29

Hardening Agentic Web Populations Through Multi-Criterion Competitive Co-Evolution: Lessons from Wargame Strategy Optimization

cs.AI ·2026-11-14 ·Shashank Raj, Kalyanmoy Deb
published similarity 0.60
Abstract · Accepted at the 1st NeurIPS 2026 Workshop on Agentic Web: Decentralized, Continually-Adapting Agent Ecosystems (https://neurips.cc/virtual/2…

Agents on the open web will face adversaries that keep adapting, so a defense that is only tested once will eventually be found and broken. We propose treating jailbreak attacks and safety guardrails as two populations that evolve against each other, rather than as a fixed attacker probing a fixed defense. This idea comes directly from wargame strategy optimization, where two-population competitive co-evolution with alternating evolution cycles and cross-play evaluation has already been shown to produce strategies that are robust to a moving opponent, and where a companion line of work has shown that the same machinery can measure how much competitive pressure a population must absorb. However, real-world applications can never rely on a single criterion as a key performance indicator, rather must use multiple conflicting criteria, such as, cost and efficiency. We describe how this mechanism transfers to language model safety, argue why the resulting multi-criteria, competitive and coevolutionary arms race is a genuinely networked, population-level problem rather than a two-agent toy setting, and lay out the open problems that stand between the wargame version of this idea and an agentic web version of it.

0.29