CS Paper Radar

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

Xiangkai Wu, Shaolin Tan, Wei Wang, Zhen Han

cs.GT cs.RO ·submitted 2026-09-07 02:47 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Strategic disclosure and epistemic manipulation in extensive games

cs.LO ·2026-11-12 ·Sergei Artemov, Benjamin Prud'homme
theory similarity 0.64
Abstract

In many strategic settings, agents can influence opponents by selectively disclosing truthful information about their own future actions. We introduce a game-theoretic framework to model this phenomenon. As a case study, we consider a two-player, alternating-move epistemic game in which Player A evaluates actions under a conservative maximin rule, while Player B-the manipulator-leverages this behavior by strategically revealing commitments. We prove that the manipulator can implement every inducible outcome using at most n disclosures in a binary game of depth 2n with n decisions per player. This establishes a sharp contrast between the game tree's exponential size and the linear amount of information required to control the outcome, highlighting a general mechanism by which limited information can exert disproportionate strategic influence.

0.46

Efficient Nash Equilibrium Computation for Cybersecurity Games

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

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

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

Hierarchical Defense in Leader-Defender-Attacker Games: Nested Equilibria and Receding-Horizon Control

eess.SY ·2026-10-07 ·Honglei Guo, Hanfang Zhang, Guochuan Zhang, Yuhan Zhao
similarity 0.59
Abstract

We formulate a discrete-time leader-defender-attacker game that combines hierarchical interaction within a protective group with competition against an external attacker. The leader seeks to reach a prescribed demand point while avoiding capture, whereas the defender seeks to intercept the attacker while remaining near the leader. To capture their distinct objectives and asymmetric interactions, we introduce a nested equilibrium concept combining a leader-defender Stackelberg relationship with a Nash-type best-response condition for the attacker. For linear dynamics and quadratic objectives, we derive affine response laws and a backward recursion, together with sufficient conditions for unique stagewise solutions. We further express arrival, capture, and interception conditions as quadratic inequalities in the initial joint state, characterizing winning regions under the resulting policy. A receding-horizon algorithm implements the computed control laws using updated state information. Numerical experiments over randomized initial configurations examine the influence of the prediction horizon and compare the proposed method with an independent-control baseline, illustrating differences in game outcomes and the agents' realized costs.

0.18

Why Alternation Speeds Up Counterfactual Regret Minimization?

cs.GT ·2026-10-15 ·Boning Li, Longbo Huang
theory similarity 0.57
Abstract · 34 pages, 8 figures

Solving imperfect-information games at scale rests on counterfactual regret minimization with the regret matching$^{+}$ (RM$^{+}$) update, and a seemingly minor implementation choice accounts for much of its practical speed: alternating the two players' updates, so that the second player responds to the strategy the first player just produced. A widely repeated intuition explains why: seeing the opponent's fresh strategy should act like optimism. We treat this intuition as a testable hypothesis about deterministic two-player zero-sum self-play dynamics and find that its canonical additive form fails an information-matched test. On an analytic witness family we compare alternating RM$^{+}$ against a one-sided predictive RM$^{+}$ that receives the same information channel each round and differs only in where the fresh signal enters, a persistent regret state versus a transient prediction term. Our main result is a dichotomy theorem that reduces trajectory separation to the recurrence of exact-vertex play by the predictive dynamics: under an interior-band assumption on the alternating iterate, either vertex times recur and the profile distance is at least, infinitely often, an explicit constant that our measurements nearly attain, or they terminate. Across the tested self-play regimes, any correct explanation of the alternation speedup must reproduce a staleness cost present at the smallest tested stale fraction, an advantage that persists across seven orders of payoff conditioning, regime crossings of the optimism family, and a measured per-perturbation cost of weakening the injection path that is far steeper for staleness than for partial persistence.

0.40

Safe Subgame Resolving in Multiplayer Games

cs.GT cs.AI ·2026-11-19 ·Boning Li, Longbo Huang
theorycode/data similarity 0.57
Abstract · 44 pages

Poker and other games with hidden information are too large to solve in one pass. Strong systems compute a complete blueprint strategy offline and refine it in real time inside the reached subgame. In 2p0s games, a safety theorem guarantees that subgame resolving never increases how much an adversary can gain by exploiting the resolved strategy relative to the blueprint strategy. With three or more players acting independently, no such guarantee exists yet, and heuristic resolving can increase the profile's best-response gap. We prove the first conditional safety theorem for uncorrelated multiplayer subgame resolving, a post-hoc certificate for any delivered update. The best-response gap of the resolved profile exceeds that of the blueprint by at most four terms. Two concern the resolver: the subgame value the blueprint promised without realizing ($A_i^{S}$) and the resolver's subgame solve error ($\varepsilon_i$). The other two are the opponents' best-response gains inside the subgame over their promised values ($\sum_q M_{q}$) and a structural tax ($Θ$), which measures how much the players' total utility can change. The tax is zero in constant-sum games, including every rake-free poker variant. Constructions attain each term with equality. On three-player Leduc poker and on Kuhn poker with up to six players, resolving without a certificate raises the gap beyond a small tolerance in 12% to 100% of the updates. The certificate flags every such update and accepts 41% (Kuhn) and 86% (Leduc) of the standard resolving updates. A resolver that keeps the blueprint whenever the certificate exceeds the tolerance delivers no harmful update. The certificate needs only one best-response pass per opponent inside the subgame, so real-time multiplayer solvers that refine a blueprint can attach it as a safety check. Code is available at https://github.com/lbn187/MultiPlayerSolver

0.67

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