Resource-Aware Intrusion Detection in Infrastructure Networks: A Game-Theoretic Approach

Resource-Aware Intrusion Detection in Infrastructure Networks: A Game-Theoretic Approach Technical Report Xuanli Lin∗ , Zhaofeng Zhang† , Zunzheng Zhang∗ , Kevin S. Chan‡ , Guoliang Xue∗ ∗

arXiv:2608.06655v1 [cs.GT] 7 Aug 2026

Arizona State University, Tempe, AZ, {xlin54, zzhan621, xue}@asu.edu † Delaware State University, Dover, DE, zzhang@desu.edu ‡ DEVCOM Army Research Laboratory, Adelphi, MD, kevin.s.chan.civ@army.mil

August 2026

Abstract Infrastructure networks increasingly rely on distributed sensing to detect intrusions before attackers reach valuable assets. Yet sensing devices, communication resources, and edge server capacity are limited, while intelligent attackers can adapt their routes to the deployed defense. Motivated by integrated sensing and communication (ISAC), we study how sensing and processing resources should be allocated under strategic interaction between a defender and an attacker. We formulate their interaction as a graph security game in which the defender deploys sensing actions under resource and false alarm constraints, while the attacker selects routes to valuable targets. We consider simultaneous play and settings in which the attacker observes either a pure defender configuration or a mixed defender strategy. Our analysis characterizes the existence, structure, and computational complexity of the Nash and Stackelberg equilibria, showing how the attacker’s observation of the defense affects equilibrium behavior and when optimal strategies become difficult to compute. We develop algorithms that construct effective pure configurations and refine restricted games for mixed Nash and mixed Stackelberg play. On enumerable instances, their solutions have small mean normalized differences from fully enumerated references; the methods also apply when exhaustive strategy enumeration is impractical. We also identify conditions under which Nash and mixed Stackelberg payoffs are ordered or coincide.

Keywords: Integrated sensing and communication (ISAC), intrusion detection, graph security games, Nash equilibrium, Stackelberg equilibrium, resource allocation, edge computing.

Contents 1 Introduction

3

2 System Model and Player Strategies 2.1 Network Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Defender Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Attacker Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Utility Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4 4 5 6 6

1

3 Simultaneous Nash Game 3.1 Pure Nash Equilibrium Need Not Exist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Mixed Nash Equilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Support Characterization for Enumerated Games . . . . . . . . . . . . . . . . . . . . . . . . .

8 8 9 9

4 Pure Stackelberg Game 10 4.1 Attacker Best Response to an Observed Configuration . . . . . . . . . . . . . . . . . . . . . . 11 4.2 Existence and Defender Optimization Hardness . . . . . . . . . . . . . . . . . . . . . . . . . . 12 4.3 RADAR: Resource-Aware Downgrading with Adaptive Refinement . . . . . . . . . . . . . . . . 13 5 Mixed Stackelberg Game 15 5.1 Why One Exact Shortest Path Weight No Longer Suffices . . . . . . . . . . . . . . . . . . . . 16 5.2 Existence and Pessimistic Nonattainment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.3 Explicit Linear Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 5.4 Computational Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5.5 RGR: RADAR-Guided Restricted Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 6 Relations Between Nash and Stackelberg Equilibria 21 6.1 When a Pure Stackelberg Outcome Is a Pure Nash Equilibrium . . . . . . . . . . . . . . . . . 21 6.2 General Defender Advantage under Strong Tie-Breaking . . . . . . . . . . . . . . . . . . . . . 22 6.3 Minimax Value under Single Route Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 6.4 Multiple Routes and a Common Payoff Ratio . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 6.5 Weighted Zero-Sum Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 7 Evaluation 25 7.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.2 Metrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 7.3 Attacker Response: Pure Configuration versus Mixed Strategy . . . . . . . . . . . . . . . . . 27 7.4 Optimization over Pure Defender Configurations . . . . . . . . . . . . . . . . . . . . . . . . . 28 7.5 Restricted Mixed Games versus Fully Enumerated Games . . . . . . . . . . . . . . . . . . . . 29 7.6 Larger Instances without Exhaustive References . . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.7 Numerical Checks of Nash–Stackelberg Relations . . . . . . . . . . . . . . . . . . . . . . . . . 30 7.8 Evaluation Summary and Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 8 Conclusion

31

A Proof of Theorem 4.3

32

B Proof of Theorem 5.1

34

C Proof of Theorem 5.2

35

D Proof of Lemma 6.1

38

E Detailed Evaluation Tables

40

2

1

Introduction

Infrastructure networks increasingly use distributed sensing to detect intrusions before an adversary reaches a valuable asset. Integrated sensing and communication (ISAC) makes such protection possible on shared wireless infrastructure, but the available sensors, communication resources, and edge server capacity remain limited [1, 2]. A defender must therefore decide where to sense, which capability to activate, and whether observations should be processed locally or at an edge server. These coupled choices determine detection coverage, false alarms, deployment cost, server load, and the sensing–communication tradeoff [3, 4]. Their effectiveness also depends on a strategic attacker whose target and route choices respond to the information available about the defense [5]. The central question is consequently not only which sensing configuration performs well, but which pure configuration or mixed defender strategy remains effective under the information available to the attacker. We use one graph model and one pair of pure action spaces to study three game settings. In the simultaneous Nash game, neither player observes the other player’s realized action before choosing its own. In the pure Stackelberg setting, the attacker observes the defender’s pure sensing configuration before routing. In the mixed Stackelberg setting, the attacker observes the distribution over complete configurations but not the configuration drawn for the current interaction. This progression isolates how the attacker’s observation of the defense changes equilibrium behavior, computational structure, and the value of hiding the realized configuration. Security games allocate limited defensive resources across targets or constrained schedules [6–8]. Graph security games and network interdiction model route selection and exponentially large action spaces [9–16], whereas adversarial network design modifies or protects the topology itself [17–19]. Intrusion detection games consider adaptive intruders and false alarm constraints [5, 20], while integrated sensing, communication, and computing work optimizes sensing, offloading, and edge computation [21–26]. We connect these directions in a graph model with fixed topology that jointly selects monitored edges, sensing types, and processing modes under deployment cost, edge server capacity, and an aggregate false alarm constraint. The model supports general-sum payoffs that vary by target, multiplicative route detection, and attacks against multiple targets. The formulation exposes a sharp computational divide. For a pure defender configuration, a logarithmic transformation turns the multiplicative probability of reaching a target undetected into an additive shortest path objective. For a hidden realization drawn from a mixed defender strategy, expected non-detection probability is instead a weighted sum of path products. Correlation induced by the common hidden configuration prevents that expectation from being represented by one set of exact additive edge weights in general, as occurs in reliable path models with correlated failures [27]. This divide motivates a restricted game method related to branch-and-price and double-oracle approaches [10,28], although the exact best response subproblems in the mixed games are themselves NP-hard. The main contributions of this report are the following. 1. We formulate the common graph game and make explicit how sensing type, processing mode, resource limits, false alarms, route detection, and payoffs assigned to each target determine the two players’ expected utilities under pure and mixed strategies. We show that a pure Nash equilibrium need not exist, while a mixed Nash equilibrium always exists, and we give exact support conditions for an enumerated game in normal form. 2. For an observed pure defender configuration, we derive an exact shortest path attacker response and prove its runtime. We show that an optimal pure Stackelberg defense exists under both strong and pessimistic tie-breaking, but optimizing that defense is NP-hard even with one 3

perfect sensing type and only a cardinality budget. We then develop RADAR (Resource-Aware Downgrading with Adaptive Refinement), including its repair score, neighborhood construction, termination property, and runtime bound. 3. For a mixed defender strategy whose realization remains hidden, we prove the existence of a mixed strong Stackelberg equilibrium and give a complete example in which the pessimistic problem has a supremum but no maximizing strategy. We establish NP-hardness of the exact attacker oracle, the pure defender oracle, and mixed Stackelberg optimization through explicit reductions. These results motivate RGR, a restricted game method guided by RADAR for mixed Nash and mixed Stackelberg computation. We derive the Stackelberg column score from the restricted linear program and state precisely what its generated action diagnostics do and do not certify. 4. We characterize the relationship between the three games. We give the exact condition under which a pure Stackelberg outcome is also a pure Nash equilibrium, prove a minimax characterization for attacks on a single route, extend it to coordinated attacks on multiple routes under a common payoff ratio, bound the Nash–Stackelberg payoff differences, and identify the weighted zero-sum case in which mixed Nash and mixed Stackelberg payoffs coincide. 5. We expand the numerical evaluation beyond the conference presentation. On enumerable instances, RADAR has a 3.64% mean normalized gap from exact optimization over pure configurations, while RGR’s mean absolute normalized defender payoff differences from selected fully enumerated solutions are 0.466% for Nash and 0.433% for mixed Stackelberg play. The expanded results separate candidate modes and candidate counts, report quality by topology and counts of objective evaluations, include larger instances for which exhaustive comparison is unavailable, and check the predicted payoff identities and inequalities numerically. The remainder of the report is organized as follows. Section 2 defines the common model. Sections 3–5 analyze the simultaneous, pure Stackelberg, and mixed Stackelberg games. Section 6 compares their outcomes, and Section 7 presents the expanded evaluation. The appendices contain the longer reductions, complete supporting proofs, and detailed evaluation tables.

2

System Model and Player Strategies

This section defines the network, the defender’s sensing configurations, the attacker’s route actions, and the payoffs assigned to each target. These elements are shared by all three games; only the order of play and the attacker’s observations change.

2.1

Network Environment

Let G = (V, E) be an undirected graph representing a monitored physical environment. Vertices may represent entrances, junctions, checkpoints, or target areas, while edges may represent corridors or links along which an intrusion can progress. The sets S ⊆ V and T ⊆ V contain possible attack sources and valuable targets, respectively, with S ∩ T = ∅. We assume that every target is reachable from at least one source. The topology is fixed: the defender selects sensing and processing actions on the existing edges but does not add, remove, or reroute network links.

4

2.2

Defender Strategies

The defender can deploy sensing capabilities along edges e ∈ E. Let K = {1, . . . , K} denote the available sensing types, each representing a distinct sensing capability. Let M = {0, 1} denote the processing modes, where m = 0 means local processing and m = 1 means offloading to an edge server. A sensing action h = (k, e, m) deploys sensing type k on edge e using processing mode m. The set H ⊆ K × E × M contains all operationally supported actions; unsupported combinations of sensing type, edge, and processing mode are simply absent from H. For h = (k, e, m), let ρkem ∈ [0, 1] be its effective detection probability, pfa kem ∈ [0, 1] its false alarm probability, cke ≥ 0 its deployment cost, and uke ≥ 0 its server load when offloaded. The detection and false alarm parameters may depend on processing mode because local and offloaded processing can use different algorithms or data resolutions. For each edge, define He = {(k, e, m) ∈ H}. A defender configuration is a set z ⊆ H with at most one sensing action per edge. Writing ze = z ∩He , the set of all configurations is Z = {z ⊆ H : |ze | ≤ 1, ∀e ∈ E}. The probability that an intrusion is detected while traversing edge e under z is X pe (z) = ρkem .

(1)

(k,e,m)∈ze

The sum contains at most one nonzero term because |ze | ≤ 1. Assuming that false alarm events are independent across deployed sensing actions [29, 30], the probability that at least one deployed action produces a false alarm is   Y X 1 −  Pfa (z) = 1 − pfa (2) kem . e∈E

(k,e,m)∈ze

Let BD > 0 be the deployment budget, Csrv > 0 the edge server capacity, and P̄fa ∈ (0, 1] the aggregate false alarm limit. Define the deployment cost and server load of z by X X b(z) = cke , ℓ(z) = muke . (3) (k,e,m)∈z

(k,e,m)∈z

The feasible defender action space is X = {z ∈ Z :Pfa (z) ≤ P̄fa ,

b(z) ≤ BD ,

ℓ(z) ≤ Csrv }.

(4)

Each z ∈ X is a feasible pure defender strategy. The empty configuration has zero cost, zero server load, and zero false alarm probability, so ∅ ∈ X and X is always nonempty under the stated parameter ranges.

5

2.3

Attacker Strategies

An attack route r is a simple path from a source s ∈ S to a target t ∈ T . Let E(r) be its edge set, t(r) its target, and R the finite set of all such routes. For a target t, write Rt = {r ∈ R : t(r) = t}. For z ∈ Z, assume that detection events on different edges are independent conditional on the realized configuration z [27]. The route non-detection probability, meaning the probability that the attacker reaches the target undetected via r, is Y
qr (z) = 1 − pe (z) . (5) e∈E(r)

Conditional independence is imposed only after z is fixed. When the defender later randomizes over complete configurations, the common hidden realization can correlate the unconditional sensing outcomes on different edges. Restricting routes to simple paths loses no attacker optimum. Consider any source–target walk containing a cycle. Removing the cycle preserves its source and target while removing factors from the product in (5). Every removed factor lies in [0, 1], so the resulting route has non-detection probability at least as large. Because the attacker utility defined below is strictly increasing in this probability, a cyclic walk cannot be strictly better than the corresponding simple path. The attacker may launch attacks against several targets simultaneously [7]. A pure attacker strategy is a set of routes containing at most one route to each target. Formally, A = {a ⊆ R : |a ∩ Rt | ≤ 1, ∀t ∈ T } .

(6)

The empty action ∅ ∈ A gives both players zero utility and represents the attacker abstaining from attack. The model places no exogenous upper bound on the number of simultaneously attacked targets; instead, the sign of the route utility determines whether attacking each target is worthwhile. Figure 1 illustrates one pure strategy pair. edge server

s1 v1

t1

v2 t2

v3

v4

s2

t3

Figure 1: Example pure strategy pair. The defender deploys two locally processed sensing actions and one offloaded action; the attacker selects two routes to distinct targets.

2.4

Utility Functions

u (t) < 0 and U d (t) > 0 be the defender utilities when an attack is undetected and For target t, let UD D detected, respectively. Define UAu (t) > 0 and UAd (t) < 0 analogously for the attacker. These sign

6

assumptions make an undetected intrusion harmful to the defender and beneficial to the attacker, while detection reverses those effects. The magnitudes may vary by target, allowing the players to value the same target differently. For a pure defender configuration z and route r, the defender’s expected route utility is
d u UD (z, r) = qr (z)UD (t(r)) + 1 − qr (z) UD (t(r)) (7) d = UD (t(r)) − ∆D (t(r))qr (z), where d u ∆D (t) = UD (t) − UD (t) > 0.

The attacker’s expected route utility is
UA (z, r) = qr (z)UAu (t(r)) + 1 − qr (z) UAd (t(r)) = UAd (t(r)) + ∆A (t(r))qr (z),

(8)

where ∆A (t) = UAu (t) − UAd (t) > 0. Thus, for a fixed target, the defender route utility decreases with the non-detection probability, whereas the attacker route utility increases with it. Utilities are additive across the routes in an attacker action: X X UD (z, a) = UD (z, r), UA (z, a) = UA (z, r). (9) r∈a

r∈a

A target omitted from a contributes zero to both players. Additivity and the restriction of at most one route per target imply that, once the best route to each target is known, the attacker can decide independently whether to include that target. This separability is used by the shortest path response in Section 4 and the candidate generator in Section 5. Table 1: Frequently used notation. Symbol

Meaning

G = (V, E) S, T H, He Z, X pe (z), Pfa (z) b(z), ℓ(z) R, Rt A qr (z) Uiu (t), Uid (t)

Monitored undirected graph Attack sources and valuable targets Supported sensing actions and actions supported on edge e All defender configurations and feasible configurations Edge detection probability and aggregate false alarm probability Deployment cost and edge server load All attack routes and routes terminating at target t Pure attacker actions, with at most one route per target Route non-detection probability Player i ∈ {D, A} payoff at target t under an undetected or detected attack Payoff differences between detected and undetected outcomes

∆D (t), ∆A (t)

The pure action spaces X and A are common to all formulations below. Decisions are simultaneous in the Nash game. In the Stackelberg games, the defender acts first and the attacker responds after observing either the realized pure configuration or the mixed defender strategy but not its realization. 7

3

Simultaneous Nash Game

We begin with the simultaneous Nash game. The defender chooses z ∈ X and the attacker chooses a ∈ A without observing the other player’s realized action. A Nash equilibrium makes these choices mutually stable: each player’s strategy is a best response to the other player’s strategy.

3.1

Pure Nash Equilibrium Need Not Exist

A pure Nash equilibrium (NE) is a pair (z NE , aNE ) satisfying UD (z NE , aNE ) ≥ UD (z, aNE ), UA (z

NE

NE

,a

) ≥ UA (z

NE

, a),

∀z ∈ X ,

(10)

∀a ∈ A.

(11)

Route adaptation can prevent such stability even in a minimal instance. Theorem 3.1. A pure Nash equilibrium need not exist. Proof. Consider two edge-disjoint routes r1 and r2 leading to two different targets. The defender can deploy at most one perfect sensor and can therefore cover at most one route. Let z0 denote the empty configuration, and let zj place a perfect sensor on rj for j ∈ {1, 2}. Thus, X = {z0 , z1 , z2 }. For both targets, set UAu = 3,

UAd = −1,

u UD = −1,

d UD = 1.

An uncovered route remains undetected with probability one and gives payoff (−1, 3), ordered as (UD , UA ). A perfectly covered route remains undetected with probability zero and gives (1, −1). By additivity across targets, the nonempty part of the payoff matrix is {r1 } {r2 } {r1 , r2 } z0 (−1, 3) (−1, 3) (−2, 6) z1 (1, −1) (−1, 3) (0, 2) z2 (−1, 3) (1, −1) (0, 2). The empty attacker action gives (0, 0) against every defender action and is never an attacker best response in this instance. We now examine every possible defender action. Against z0 , both routes have positive attacker utility, so the unique attacker best response is {r1 , r2 }. Holding that action fixed, the defender improves from −2 to 0 by changing to either z1 or z2 . Consequently, no pair with defender action z0 satisfies (10)–(11). Against z1 , route r1 gives attacker utility −1 and route r2 gives utility 3. The unique attacker best response is therefore {r2 }. Holding {r2 } fixed, the defender improves from −1 under z1 to 1 under z2 . Hence no pair with defender action z1 is a pure NE. By symmetry, the unique attacker best response to z2 is {r1 }, and the defender improves by changing to z1 . These three cases exhaust X , so no pure Nash equilibrium exists. The failure is not caused by imperfect sensing, processing constraints, or complicated routes. The attacker’s best response changes with sensor placement, while each Nash deviation holds the other player’s current action fixed. The resulting best response cycle prevents a stable pure pair. 8

3.2

Mixed Nash Equilibrium

The players may instead randomize over complete pure actions. Let ∆(X ) and ∆(A) be the corresponding probability simplices, and let σ ∈ ∆(X ) and µ ∈ ∆(A) denote defender and attacker mixed strategies. A draw from σ realizes one complete feasible configuration; it does not fractionally deploy individual sensing actions. The expected utilities are XX ŪD (σ, µ) = σ(z)µ(a)UD (z, a), (12) z∈X a∈A

ŪA (σ, µ) =

XX

σ(z)µ(a)UA (z, a).

(13)

z∈X a∈A

We use the samePnotation when one argument is pure. For example, ŪD (σ, a) = and ŪD (z, µ) = a µ(a)UD (z, a). A mixed NE (σ NE , µNE ) satisfies ŪD (σ NE , µNE ) ≥ ŪD (z, µNE ), ŪA (σ

NE

NE

,µ

) ≥ ŪA (σ

NE

, a),

P

z σ(z)UD (z, a)

∀z ∈ X ,

(14)

∀a ∈ A.

(15)

It is sufficient to check pure deviations. Indeed, the payoff from any mixed deviation is a convex combination of the payoffs from its pure actions and therefore cannot exceed the largest payoff from a pure deviation. Theorem 3.2. The simultaneous graph game has at least one mixed Nash equilibrium. Proof. The defender action set X is finite because it is a subset of the power set of the finite set H of sensing actions. The route set R is finite because a finite graph has finitely many simple paths, and A is finite because it is a subset of the power set of R. The game is therefore a finite two-player game in normal form. Nash’s existence theorem for finite games guarantees a mixed equilibrium [31]. For the instance used in the proof of Theorem 3.1, one mixed NE is obtained by assigning probability 1/2 to each of z1 and z2 and letting the attacker choose {r1 , r2 }. Each route then gives the attacker expected utility 1, so attacking both gives utility 2 and is optimal. Against the two-route action, both z1 and z2 give the defender utility zero, whereas z0 gives −2. Thus both players are best responding even though no pure action pair is stable.

3.3

Support Characterization for Enumerated Games

When all pure actions are explicitly enumerated, candidate supports provide an exact way to compute and verify mixed equilibria. Let nonempty sets SD ⊆ X and SA ⊆ A be candidate supports. Set all probabilities outside these sets to zero, and introduce payoff variables vD and vA . Consider X µ(a)UD (z, a) = vD , z ∈ SD , (16) a∈SA

X

µ(a)UD (z, a) ≤ vD ,

z ∈ X \ SD ,

(17)

σ(z)UA (z, a) = vA ,

a ∈ SA ,

(18)

a∈SA

X z∈SD

9

X

σ(z)UA (z, a) ≤ vA ,

a ∈ A \ SA ,

(19)

z∈SD

together with σ(z) ≥ 0,

µ(a) ≥ 0,

X

X

σ(z) = 1,

z∈SD

µ(a) = 1.

(20)

a∈SA

Proposition 3.1. Every feasible solution of (16)–(20) defines a mixed NE whose actual supports are contained in (SD , SA ). Conversely, every mixed NE satisfies this system when SD and SA are its exact supports. Proof. Suppose the system is feasible. Every defender action assigned positive probability lies in SD and gives expected payoff vD against µ by (16). Hence the defender’s expected payoff under σ is also vD . Every action outside SD gives payoff at most vD by (17); actions inside SD give exactly vD . Therefore no pure defender deviation is profitable, and, by linearity, no mixed defender deviation is profitable. The same argument using (18)–(19) shows that the attacker’s expected payoff is vA and that no attacker deviation is profitable. Thus (σ, µ) is a mixed NE. Conversely, let (σ, µ) be a mixed NE and let SD = supp(σ) and SA = supp(µ). Every action in the support of a best response must itself be a best response. If, for example, some z ∈ SD gave strictly less than the maximum defender payoff against µ, then the weighted average under σ would be strictly less than that maximum, contradicting (14). Therefore every z ∈ SD gives the common equilibrium payoff vD , and every action outside SD gives at most vD . The attacker conditions follow identically. The support probabilities are nonnegative and sum to one, so the equilibrium satisfies the complete system. Exhaustive enumeration of candidate support pairs is exact for an explicitly listed game, but it scales poorly: the graph may encode exponentially many pure configurations and routes, and the number of candidate support pairs is itself exponential in the size of the game in normal form. The next two sections exploit the graph structure where possible and use restricted action sets where exact enumeration is impractical.

4

Pure Stackelberg Game

We next consider a sequential setting in which reconnaissance reveals the defender’s pure sensing configuration. The defender acts first and selects z ∈ X . The attacker observes that complete configuration before choosing a ∈ A. The defender is therefore the leader and the attacker is the follower. For any z ∈ Z, define the attacker best response set BRA (z) = arg max UA (z, a).

(21)

a∈A

Although the defender ultimately selects from X , we define the response on all of Z because RADAR evaluates infeasible intermediate configurations. The set BRA (z) is nonempty because A is finite and nonempty. When the attacker has multiple best responses, strong tie-breaking selects one that is most favorable to the defender, while pessimistic tie-breaking selects one that is least favorable. Define VD+ (z) =

max a∈BRA (z)

VD− (z) =

UD (z, a), 10

min a∈BRA (z)

UD (z, a).

(22)

A pure strong Stackelberg equilibrium (SSE) is a pair (z SE , aSE z ) such that z SE ∈ arg max VD+ (z), z∈X

SE aSE z ∈ arg max UD (z , a).

(23)

a∈BRA (z SE )

The pessimistic pure Stackelberg problem maximizes VD− (z) over z ∈ X .

4.1

Attacker Best Response to an Observed Configuration

Fix z ∈ Z. Because ∆A (t) > 0, the attacker utility (8) is strictly increasing in qr (z) among routes to the same target. The attacker therefore prefers a route with maximum non-detection probability. Define the nonnegative edge weight
we (z) = − log 1 − pe (z) , (24) with we (z) = +∞ when pe (z) = 1. For any route with positive non-detection probability, Y X − log qr (z) = − log (1 − pe (z)) = we (z). e∈E(r)

(25)

e∈E(r)

Because x 7→ − log x is strictly decreasing on (0, 1], maximizing the route non-detection probability is equivalent to minimizing the sum in (25). To find the best route from any source, add an auxiliary source s0 with a zero-weight edge to each s ∈ S. Assign weight we (z) to every original edge and remove edges with pe (z) = 1, which have infinite weight. One Dijkstra run from s0 returns the minimum distance dz (v) to every vertex. For target t, the maximum route non-detection probability is qtmax (z) = e−dz (t) ,

(26)

where e−∞ = 0. Any predecessor path returned for t maximizes the non-detection probability when dz (t) < ∞. The best route to target t gives attacker and defender utility contributions θt (z) = UAd (t) + ∆A (t)e−dz (t) ,

(27)

d ϕt (z) = UD (t) − ∆D (t)e−dz (t) .

(28)

If θt (z) > 0, every attacker best response includes a route with maximum non-detection probability to t, because adding it strictly improves attacker utility. If θt (z) < 0, every best response omits t. When θt (z) = 0, inclusion and omission give the attacker the same utility. Strong tie-breaking includes the route exactly when doing so improves the defender’s payoff, while pessimistic tie-breaking includes it exactly when doing so lowers the defender’s payoff. Equivalently, X X VD+ (z) = ϕt (z) + max{ϕt (z), 0}, (29) t: θt (z)>0

VD− (z) =

X

t: θt (z)=0

ϕt (z) +

t: θt (z)>0

X

min{ϕt (z), 0}.

(30)

t: θt (z)=0

The particular route chosen among routes of equal transformed weight to the same target does not affect either player’s payoff, because those routes have the same target and the same non-detection probability. 11

Theorem 4.1. For any z ∈ Z, the procedure above returns an attacker best response and computes both VD+ (z) and VD− (z) in O((|E| + |V|) log |V|) time. Proof. Fix a target t. By (8), two routes r, r′ ∈ Rt satisfy UA (z, r) ≥ UA (z, r′ ) if and only if qr (z) ≥ qr′ (z), because both routes have the same UAd (t) and positive coefficient ∆A (t). Equation (25) shows that a route with maximum non-detection probability is exactly a minimum weight route under w(z). All finite edge weights are nonnegative, so Dijkstra’s algorithm from the auxiliary source finds such a route simultaneously for every target. If all routes to a target contain a perfectly sensed edge, the target distance is infinite and the maximum non-detection probability is zero, which is represented by e−∞ = 0. It remains to form a best action that may attack multiple targets. By (9), the attacker utility of an action is the sum of its target contributions, and the constraint in (6) couples neither the route choices nor the inclusion decisions for different targets. For each target, choosing a route with maximum non-detection probability maximizes its possible contribution. A positive contribution must be included, a negative contribution must be omitted, and a zero contribution may be either included or omitted. These independent choices produce an action in BRA (z). At a zero attacker contribution, choosing between the included route payoff ϕt (z) and the omitted payoff zero gives the strong and pessimistic terms in (29)–(30). Therefore the procedure returns a best response and both defender values. The auxiliary graph has |V|+1 vertices and at most |E|+|S| edges. With a binary heap, Dijkstra’s algorithm takes O((|E| + |V|) log |V|) time. Reconstructing at most one route per target and scanning the targets takes O(|E| + |V|) total time when predecessor paths are represented implicitly, so it does not change the stated bound.

4.2

Existence and Defender Optimization Hardness

The finite action spaces immediately give existence under either tie-breaking rule. Theorem 4.2. A pure SSE exists, and the pessimistic pure Stackelberg problem has an optimal defender configuration. Proof. The feasible set X is nonempty because it contains the empty configuration, and it is finite because H is finite. For every z ∈ X , the finite best response set BRA (z) is nonempty, so the maxima and minima in (22) are well defined. A real-valued function on a finite nonempty set attains both its maximum and minimum. Hence some z + ∈ arg maxz∈X VD+ (z) exists, and selecting a response most favorable to the defender from BRA (z + ) gives a pure SSE. Likewise, some z − ∈ arg maxz∈X VD− (z) exists and solves the pessimistic pure problem. The attacker response can be computed in polynomial time, but defender optimization remains intractable. Consider the restricted setting with one source, one perfect sensing type of unit cost, no false alarm or server constraint, and only the cardinality constraint |z| ≤ BD . Every target has payoffs u d UAu = 1, UAd = −1, UD = −1, UD = 1. Theorem 4.3. Even in the restricted setting above, computing an optimal pure defender configuration is NP-hard under either strong or pessimistic tie-breaking.

12

Proof. Appendix A gives a complete reduction from Clique that is computable in polynomial time. The construction has no attacker ties that affect payoffs, so the same reduction applies to both tie-breaking rules. Theorems 4.1 and 4.3 separate evaluation from optimization: the value of any proposed pure configuration can be computed efficiently, but finding the best feasible configuration is NP-hard. This motivates a search procedure that repeatedly evaluates selected configurations without enumerating X.

4.3

RADAR: Resource-Aware Downgrading with Adaptive Refinement

RADAR searches Z using two stages. Resource-aware downgrading (RAD) repairs a dense, possibly infeasible configuration by moving sensing actions down prescribed hierarchies. Adaptive refinement then tests repaired upgrades and exchanges to recover valuable sensing choices removed during repair. Let F : Z → R be the objective used by the search. For pure Stackelberg optimization, set F = VD+ under strong tie-breaking and F = VD− under pessimistic tie-breaking. These values are defined on all Z because resource feasibility restricts which configurations may be selected, not how route payoffs are evaluated. Section 5.5 later uses the same search with different objectives. 4.3.1

Downgrade hierarchies and repair score

For every edge e that supports sensing, each action h ∈ He has a prescribed immediate downgrade de (h) ∈ He ∪ {∅e }, where ∅e denotes no sensing on e. A downgrade does not increase detection probability, deployment cost, server load, or false alarm probability. Repeated downgrades must reach ∅e , so the directed downgrade relation is acyclic. Reversing the relation defines the immediate upgrades. The initial configuration z max selects a designated maximal action on every edge that supports sensing and may violate one or more resource limits. If z selects h on edge e, let de (z) be the configuration obtained by replacing h with de (h), or by removing h when de (h) = ∅e . Define normalized resource usage, normalized excess, and the resource reduction from z to x by   b(z) ℓ(z) Pfa (z) g(z) = , , , (31) BD Csrv P̄fa ν(z) = [g(z) − 1]+ , (32) ξ(z, x) = g(z) − g(x).

(33)

The positive part operator is applied componentwise. Because a downgrade does not increase any resource, ξ(z, x) ≥ 0. The amount by which the downgrade addresses currently violated constraints is R(z, x) = ν(z)⊤ ξ(z, x) ≥ 0. (34) Let the nonnegative loss in search objective be ∆F (z, x) = [F (z) − F (x)]+ .

13

(35)

RAD ranks a candidate downgrade by   R(z, x) > 0 and ∆F (z, x) = 0, +∞, SF (z, x) = R(z, x)/∆F (z, x), R(z, x) > 0 and ∆F (z, x) > 0,   0, R(z, x) = 0.

(36)

The score favors a large reduction in the constraints that are currently violated and a small loss in F . Ties are broken first by larger R(z, x) and then by larger F (x). These secondary rules prefer a downgrade that makes more direct feasibility progress and, subject to equal progress, retains more objective value. 4.3.2

Refinement neighborhood

For a feasible configuration z, let U(z) be its immediate upgrades. An upgrade may violate a resource limit, so each upgraded configuration is passed through RAD before it enters the neighborhood. Let Q(z) ⊆ X contain feasible exchanges between two edges. An exchange swaps the sensing type and processing mode choices assigned to the two edges whenever the resulting actions for those edges belong to H. Treating ∅e as an available choice allows an exchange to move a deployment from a monitored edge to an unmonitored edge. The refinement neighborhood is NF (z) = {RAD(y, F ) : y ∈ U(z)} ∪ Q(z). Duplicate configurations may be removed before evaluation. Algorithm 1 Resource-aware downgrading and adaptive refinement 1: procedure RAD(z, F ) 2: while z ∈ / X do 3: D ← {de (z) : e ∈ E, ze ̸= ∅} 4: z ← arg maxx∈D SF (z, x) using the stated tie rules 5: end while 6: return z 7: end procedure 8: procedure RADAR(z max , F ) 9: z ← RAD(z max , F ) 10: loop 11: N ← NF (z) 12: if N = ∅ then 13: break 14: end if 15: x ← arg maxy∈N F (y) 16: if F (x) ≤ F (z) then 17: break 18: end if 19: z←x 20: end loop 21: return z 22: end procedure

14

(37)

Proposition 4.1. RAD terminates and returns a feasible configuration. RADAR terminates at a feasible configuration z for which no candidate in NF (z) has a strictly larger objective value F . Proof. Assign each action in an edge’s downgrade hierarchy a nonnegative rank equal to the number of remaining downgrade steps before ∅e . The sum of the ranks selected by a configuration is a nonnegative integer. Every RAD iteration replaces one action by its immediate downgrade and therefore decreases this rank sum by one. RAD cannot cycle and must terminate after finitely many iterations. If feasibility has not been reached earlier, all actions are eventually removed. The resulting empty configuration belongs to X , so RAD necessarily terminates at a feasible configuration. The initial RAD call in RADAR therefore returns a feasible configuration. Every repaired upgrade in (37) is feasible because it is the output of RAD, and every exchange in Q(z) is feasible by definition. Hence every accepted iterate remains in X . RADAR accepts a new iterate only when its objective value is strictly larger. Since X is finite, a strictly improving sequence cannot continue indefinitely and cannot revisit a previous configuration. At termination, either the neighborhood is empty or its largest value is no larger than F (z), which is exactly the stated local optimality condition. Proposition 4.2. Let M be the number of edges that support sensing, let I be the number of refinement rounds, and let TF be the time required to evaluate F for one configuration. Assuming resource usage is maintained incrementally, one RAD call takes O(|H|M TF ) time, and RADAR takes

O |H|M + I(|H|2 M + M 2 ) TF = O(I|H|3 TF ) (38) time when I ≥ 1 and M ≤ |H|. Proof. Across all edges, the total number of possible downgrade steps is at most |H|: each step leaves one supported action and moves to another supported action or to no sensing. At any RAD iteration, at most one downgrade is available for each of the M edges that support sensing, so at most M candidates are scored. Caching F (z) means each candidate requires at most one new objective evaluation. Thus a repair uses at most O(|H|M ) objective evaluations and takes O(|H|M TF ) time. The reverse downgrade relation contains at most |H| immediate upgrade arcs in total, so a refinement round considers at most |H| immediate upgrades. Repairing each one costs O(|H|M TF ), for O(|H|2 M TF ) time. There are at most O(M 2 ) unordered edge pairs to test for exchanges, each requiring at most a constant number of objective evaluations once support and feasibility are checked. This contributes O(M 2 TF ) per round. Adding the initial repair and multiplying the refinement cost by I gives the first expression in (38). Since M ≤ |H|, the expression is O(I|H|3 TF ) for I ≥ 1. For pure Stackelberg optimization, Theorem 4.1 gives TF = O((|E| + |V|) log |V|). Every local candidate is therefore evaluated after the attacker reroutes optimally. In the next section, the same repair and refinement operations generate candidate defender columns for restricted mixed Nash and mixed Stackelberg games; only the objective F changes.

5

Mixed Stackelberg Game

The preceding Stackelberg setting assumes that the attacker observes the realized pure defender configuration. The defender may instead use a mixed strategy σ ∈ ∆(X ) and draw one complete 15

feasible configuration before each interaction. The attacker observes σ but not the realized configuration before selecting its routes. Randomization therefore hides which edges are actively monitored in the current interaction while preserving the resource feasibility of every realized configuration. For route r, define its expected non-detection probability under σ by X q̄r (σ) = σ(z)qr (z). (39) z∈X

The expected route utilities are ŪA (σ, r) = UAd (t(r)) + ∆A (t(r))q̄r (σ),

(40)

d (t(r)) − ∆D (t(r))q̄r (σ). ŪD (σ, r) = UD

(41)

They extend additively to attacker actions. The follower best response set is BRA (σ) = arg max ŪA (σ, a).

(42)

a∈A

Define the mixed defender values under strong and pessimistic tie-breaking by VD+ (σ) =

max a∈BRA (σ)

VD− (σ) =

ŪD (σ, a),

min a∈BRA (σ)

ŪD (σ, a).

(43)

A mixed SSE is a pair (σ SE , aSE σ ) satisfying σ SE ∈ arg max VD+ (σ),

SE aSE σ ∈ arg max ŪD (σ , a).

(44)

a∈BRA (σ SE )

σ∈∆(X )

The timing is essential. If the realized configuration were revealed before the attacker selected its action, the defender’s expected value from σ would be a convex combination of the Stackelberg values of pure configurations and could not exceed the best value attained by a pure configuration under the same tie-breaking rule. Randomization can improve the defender’s outcome only because the attacker responds to the distribution rather than to its current draw.

5.1

Why One Exact Shortest Path Weight No Longer Suffices

For a fixed configuration, the logarithm in (25) converts a path product into a sum. Under a mixed strategy, X Y q̄r (σ) = σ(z) (1 − pe (z)). (45) z∈X

e∈E(r)

The logarithm cannot pass through the outer weighted sum. More fundamentally, the common hidden configuration can correlate the edge states in a way that no fixed set of exact edge weights represents. Example 5.1 (Correlated hidden configurations). Consider two serial binary choice stages, so every source–target route chooses branch 0 or 1 in the first stage and independently chooses branch 0 or 1 in the second. Denote the four routes by r00 , r01 , r10 , r11 . Let z 00 leave both branch 0 choices unsensed and perfectly sense both branch 1 choices. Let z 11 do the reverse, and assign probability 1/2 to each configuration. Then 1 q̄r00 (σ) = q̄r11 (σ) = , 2

q̄r01 (σ) = q̄r10 (σ) = 0. 16

Suppose exact nonnegative additive weights existed. Writing the corresponding multiplicative edge b factors as αib = e−wi ∈ [0, 1] for stage i and branch b, exactness would require 1 α10 α20 = , 2

1 α11 α21 = . 2

Both equalities force all four factors to be positive. The products for the crossed routes α10 α21 and α11 α20 would then also be positive, contradicting the zero expected non-detection probability of r01 and r10 . Thus no single exact additive edge weight represents all four expected route non-detection probabilities. This obstacle is the nonadditive expectation induced by the hidden configuration, not a failure of Dijkstra’s algorithm. It is closely related to reliable path problems with correlated edge failures [27].

5.2

Existence and Pessimistic Nonattainment

Theorem 5.1. A mixed SSE exists. By contrast, the pessimistic mixed Stackelberg problem need not attain its supremum. Proof. Appendix B gives a complete proof. It first partitions the defender simplex into the closed polytopes on which each attacker action is a best response, and then maximizes the defender’s linear payoff over those polytopes. The appendix also gives an explicit instance with two configurations in which the pessimistic value approaches a strictly larger limit from one side and drops at the tie point. Every pure configuration is a degenerate mixed strategy. Therefore, max VD− (z) ≤ sup VD− (σ) z∈X

σ∈∆(X )

≤ max VD+ (σ).

(46)

σ∈∆(X )

The three quantities are the best pessimistic pure value, the pessimistic mixed supremum, and the mixed SSE value. Nonattainment is not caused by noncompactness: the simplex ∆(X ) is compact. It is caused by pessimistic tie-breaking, which can make VD− (σ) drop discontinuously when a second attacker action becomes tied. Strong tie-breaking instead selects the tied action most favorable to the defender and attains a maximum.

5.3

Explicit Linear Formulation

Suppose all pure actions are explicitly listed. Fix a candidate attacker response a ∈ A and solve max ŪD (σ, a) σ

s.t. ŪA (σ, a) ≥ ŪA (σ, a′ ), ∀a′ ∈ A, X σ(z) = 1,

(47)

z∈X

σ(z) ≥ 0,

∀z ∈ X .

The incentive constraints make a an attacker best response. The objective then evaluates the defender payoff when strong tie-breaking selects that response. 17

Proposition 5.1. Solving (47) for every a ∈ A and retaining a feasible solution with the largest objective value returns a mixed SSE. Proof. For a fixed a, the feasible set of (47) consists exactly of the defender mixtures for which a ∈ BRA (σ). Hence every feasible pair (σ, a) is a valid leader strategy together with one follower best response, and its LP objective is the corresponding defender payoff. Conversely, for any defender mixture σ and any best response a ∈ BRA (σ), the same σ is feasible for the LP indexed by a. Therefore the union of the feasible pairs over all indexed LPs is exactly {(σ, a) : σ ∈ ∆(X ), a ∈ BRA (σ)}. Maximizing the defender payoff over this union is precisely the strong Stackelberg optimization in (44). Taking the best objective among the finitely many LPs therefore returns a mixed SSE. This procedure is polynomial in the size of an explicitly listed game in normal form: it solves |A| linear programs, each with |X | variables and |A| + 1 principal constraints. A compact graph description may nevertheless encode exponentially many defender configurations and attacker route actions, so the explicit formulation is not polynomial in the graph input size.

5.4

Computational Complexity

The loss of the shortest path structure is not merely a limitation of the proposed candidate generator. Theorem 5.2. In the graph model: (i) computing an exact attacker best response to a mixed defender strategy with explicit finite support is NP-hard, even when the attacker selects only one route; (ii) computing a pure defender best response to a mixed attacker strategy with explicit finite support is NP-hard; and (iii) computing an optimal mixed SSE is NP-hard. Proof. Appendix C gives complete reductions from Max-Cut, Maximum Coverage, and 0–1 Knapsack, respectively. The constructions use only polynomially many vertices, edges, and explicitly supported pure strategies, and they use detection probabilities in {0, 1/2, 1}. The third construction has a unique attacker response for every defender mixture, so its hardness is unrelated to tie-breaking. Allowing the defender to randomize therefore makes both exact response generation and defender optimization combinatorial. Finite formulations remain useful over selected action sets, but those sets must be expanded without relying on exact oracles that run in polynomial time.

5.5

RGR: RADAR-Guided Restricted Game

RGR maintains nonempty restricted action sets X ′ ⊆ X and A′ ⊆ A. Including the empty configuration and empty attacker action provides a simple feasible initialization, although the algorithm accepts any nonempty initial sets. For mixed Nash play, it solves the restricted bimatrix game using the support conditions of Section 3.3. For mixed Stackelberg play, it solves the restricted versions of (47), one for each designated response in A′ , and retains the best restricted LP value. The resulting solution guides searches for new defender configurations and attacker actions. 18

5.5.1

Defender generation for Nash play

Let (σ ′ , µ′ ) be a restricted Nash equilibrium. A defender deviation in the full game would maximize ŪD (z, µ′ ) over z ∈ X . RGR therefore calls RADAR with FN (z) = ŪD (z, µ′ ).

(48)

The returned configuration is a heuristic pure best response to the restricted attacker mixture. 5.5.2

Defender column score for Stackelberg play

Consider the selected restricted SSE LP with designated attacker action a⋆ . For a′ ∈ A′ , define da′ (z) = UA (z, a⋆ ) − UA (z, a′ ). Over X ′ , the LP is X

max σ

σ(z)UD (z, a⋆ )

z∈X ′

X

s.t.

∀a′ ∈ A′ ,

σ(z)da′ (z) ≥ 0,

(49)

z∈X ′

X

σ(z) ≥ 0.

σ(z) = 1,

z∈X ′

Let ηa′ ≥ 0 be the dual multiplier associated with the incentive constraint against a′ , and let β be the free dual variable associated with the probability equality. The dual is min β β,η

s.t. β ≥ UD (z, a⋆ ) +

X

ηa′ da′ (z), ∀z ∈ X ′ ,

(50)

a′ ∈A′

∀a′ ∈ A′ .

ηa′ ≥ 0, This gives the defender column score FS (z) = UD (z, a⋆ ) +

X

  ηa′ UA (z, a⋆ ) − UA (z, a′ ) .

(51)

a′ ∈A′

For every existing column z ∈ X ′ , dual feasibility requires FS (z) ≤ β. A missing configuration with FS (z) > β violates the current dual constraint and has positive reduced value for the maximization problem. RGR therefore calls RADAR with FS to search for such a column. Pure Stackelberg design, Nash deviation search, and mixed Stackelberg column generation use the same configuration search; only F changes. 5.5.3

Attacker route generation

The attacker generator combines two candidate sources. First, the support generator applies the exact shortest path response of Theorem 4.1 to every pure configuration z ∈ supp(σ ′ ) and collects the routes that appear in those responses. This source is inexpensive and often useful, but a route that is optimal in expectation need not be optimal under any individual support configuration. 19

Second, the surrogate generator assigns edge weight X w ee (σ ′ ) = σ ′ (z)we (z)

(52)

z∈supp(σ ′ )

and generates the Kcand shortest simple paths to each target. For any route r, X X σ ′ (z) log qr (z) w ee (σ ′ ) = − e∈E(r)

z∈supp(σ ′ )

Y

= − log

′

qr (z)σ (z) .

z∈supp(σ ′ )

The surrogate therefore maximizes the weighted geometric mean of the route non-detection probability, not the expectation in (39). It is used only to propose paths. The combined generator takes the union of the support and surrogate candidates. Every proposed route is reevaluated using the exact expectation (39). For each target, the generator retains a candidate with maximum exact attacker utility. A target with positive utility is included in the generated action, and a target with negative utility is omitted. For Nash deviation measurement, a target with zero utility may be omitted because inclusion does not change attacker utility. For strong Stackelberg play, zero utility and ties between routes are resolved using the exact utility most favorable to the defender among the generated candidates. Algorithm 2 RGR: RADAR-guided restricted game Require: Game g ∈ {NE, SSE}; nonempty X ′ , A′ ; candidate count Kcand ; iteration cap 1: loop 2: Solve the restricted game 3: if g = NE then 4: obtain (σ ′ , µ′ ) and set F ← FN 5: else 6: obtain (σ ′ , a⋆ , η, β) and set F ← FS 7: end if 8: z + ← RADAR(z max , F ) 9: generate support and surrogate routes and form action a+ using exact utilities 10: add any new generated defender or attacker action that improves or invalidates the restricted solution 11: if no action is added or the iteration cap is reached then 12: break 13: end if 14: end loop 15: return the restricted solution and generated action diagnostics For a restricted Nash solution, the generated actions give the measured unilateral deviation gains   ϵD = ŪD (z + , µ′ ) − ŪD (σ ′ , µ′ ) + , (53)   ϵA = ŪA (σ ′ , a+ ) − ŪA (σ ′ , µ′ ) + . (54) For the selected restricted SSE LP, the corresponding generated quantities are   ϵcol = FS (z + ) − β + , 20

(55)

  ϵroute = ŪA (σ ′ , a+ ) − ŪA (σ ′ , a⋆ ) + .

(56)

The evaluator’s generated action gaps summarize improvements found among generated actions; they are not global equilibrium gaps. Proposition 5.2. If exact best response oracles for the full game are used for both players and a restricted Nash solution has ϵD = ϵA = 0, then it is a Nash equilibrium of the full game. A full mixed SSE certificate additionally requires considering every possible designated attacker response and pricing every corresponding LP over all defender configurations. The heuristic RGR procedure does not provide these global certificates in general. Proof. For Nash play, zero exact defender and attacker gains mean that neither player has a profitable pure deviation in its full action set. Linearity then rules out profitable mixed deviations, so the restricted solution satisfies the full Nash conditions (14)–(15). For mixed SSE, a zero exact pricing violation certifies only the currently selected LP and its designated response. The global strong Stackelberg problem is the maximum over one LP indexed by each a ∈ A, as shown in Proposition 5.1. A missing designated response may define a different LP with a larger defender value, and a missing attacker action may invalidate the incentive constraints of an existing LP. Therefore a global certificate requires complete response enumeration and complete pricing for every indexed LP. Theorem 5.2 shows why RGR uses heuristic generation instead. Because the action sets are finite and only new actions are added, RGR terminates at the iteration cap or when its generators add no action. Under heuristic generation, this stopping condition does not certify global optimality.

6

Relations Between Nash and Stackelberg Equilibria

The preceding games have the same action spaces and payoffs but differ in move order and in what the attacker observes. Existing equivalence results for target security games [32] do not directly cover multiplicative route detection and coordinated attacks against multiple targets. We first characterize when a pure Stackelberg outcome is also a pure Nash equilibrium. We then show that a mixed SSE weakly improves the defender’s mixed Nash payoff, characterize the attacker’s minimax value when each action contains at most one route, extend that characterization under a common payoff ratio, and identify the weighted zero-sum case in which mixed Nash and mixed Stackelberg payoffs coincide.

6.1

When a Pure Stackelberg Outcome Is a Pure Nash Equilibrium

A pure Stackelberg outcome (z SE , aSE z ) already satisfies the attacker’s Nash condition because SE SE az ∈ BRA (z ). Only the defender condition remains. Proposition 6.1. A pure Stackelberg outcome (z SE , aSE z ) is a pure Nash equilibrium if and only if z SE ∈ arg max UD (z, aSE z ).

(57)

z∈X

SE Proof. Because aSE z is an attacker best response to z , the attacker inequality (11) is satisfied. The pair is therefore a pure NE exactly when it also satisfies the defender inequality (10). That inequality is equivalent to (57).

21

Condition (57) need not hold. In the instance used to prove Theorem 3.1, a pure Stackelberg optimum is z1 followed by {r2 }, or symmetrically z2 followed by {r1 }. The defender obtains −1 at either outcome. Holding the attacker’s action fixed, however, the defender can switch to the other sensor placement and obtain 1. Thus a pure Stackelberg outcome can fail to be a pure NE even though the attacker is best responding.

6.2

General Defender Advantage under Strong Tie-Breaking

Under strong tie-breaking, a mixed SSE gives the defender at least the payoff of any mixed Nash equilibrium, without requiring a zero-sum or common ratio assumption. NE , µNE ) be any mixed NE. Then Theorem 6.1. Let (σ SE , aSE σ ) be a mixed SSE and let (σ NE NE ŪD (σ SE , aSE , µ ). σ ) ≥ ŪD (σ

(58)

Proof. Every action in supp(µNE ) is an attacker best response to σ NE . Strong tie-breaking at that same defender mixture gives VD+ (σ NE ) =

max ŪD (σ NE , a) NE a∈BRA (σ ) X ≥ µNE (a)ŪD (σ NE , a) a∈supp(µNE )

= ŪD (σ NE , µNE ). The mixed SSE maximizes VD+ (σ) over all defender mixtures, so its payoff is at least VD+ (σ NE ) and hence at least the mixed Nash payoff. The theorem orders defender payoffs but does not order attacker payoffs. Additional payoff structure is needed for that comparison.

6.3

Minimax Value under Single Route Attacks

Suppose every nonempty attacker action contains exactly one route, so the attacker chooses at most one target. Target variation in defender and attacker payoffs can then be absorbed by reweighting the attacker’s route mixture. Lemma 6.1. Assume every attacker action contains at most one route. For any mixed NE (σ NE , µNE ), any σ ∈ ∆(X ), and any a ∈ BRA (σ), ŪA (σ NE , µNE ) =

min max ŪA (σ ′ , a′ )

σ ′ ∈∆(X ) a′ ∈A

(59)

≤ ŪA (σ, a). Thus the attacker’s mixed Nash payoff is its minimax value and does not exceed its payoff from a best response to any pure or mixed defender strategy. Proof. Appendix D gives the complete reweighting and saddle point argument, including the separate case in which the empty action belongs to the Nash support.

22

The lemma compares values rather than arbitrary defender strategies: an optimal Stackelberg defense need not itself minimize the attacker’s payoff. With explicitly listed actions, a minimax defender mixture is obtained from min v σ,v X s.t. σ(z)UA (z, a) ≤ v, ∀a ∈ A, z∈X

X

(60) σ(z) = 1,

z∈X

σ(z) ≥ 0,

∀z ∈ X .

Recovering a Nash attacker mixture for the original general-sum game additionally requires a saddle point mixture for the zero-sum game defined by the attacker payoff and the inverse reweighting in Appendix D. RGR instead solves the restricted original game and remains applicable when one attacker action contains several routes.

6.4

Multiple Routes and a Common Payoff Ratio

When actions contain several routes, reweighting probabilities separately by target need not produce one valid attacker mixture. A payoff ratio that is constant across targets restores a single identity that makes the game strategically zero sum. Theorem 6.2. Suppose a constant λ > 0 satisfies ∆D (t) = λ, ∆A (t)

∀t ∈ T .

(61)

When an attacker action may contain any number of routes, every mixed NE gives the attacker the minimax value in (59). Consequently, the attacker’s payoff from a best response to any pure or mixed defender strategy is at least its mixed Nash payoff. Proof. For each target, define u ct = UD (t) + λUAu (t).

(62)

Condition (61) implies
d u UD (t) + λUAd (t) = UD (t) + ∆D (t) + λ UAu (t) − ∆A (t) u = UD (t) + λUAu (t) + ∆D (t) − λ∆A (t)

= ct . Using either the detected/undetected expectation or the affine forms (7)–(8), every route to target t therefore satisfies UD (z, r) + λUA (z, r) = ct . For an attacker action a, let C(a) =

X

ct(r) .

(63)

r∈a

Additivity gives the outcome identity UD (z, a) + λUA (z, a) = C(a), 23

∀z ∈ X , a ∈ A.

(64)

The right-hand side depends on the attacker action but not on the defender action. Let (σ NE , µNE ) be a mixed NE. For a fixed attacker mixture µNE , taking expectations in (64) yields ŪD (σ, µNE ) = Ea∼µNE [C(a)] − λŪA (σ, µNE ). The first term is independent of σ. Because σ NE maximizes defender utility against µNE , it minimizes attacker utility against that same mixture. The attacker Nash condition says that µNE maximizes attacker utility against σ NE . Hence (σ NE , µNE ) is a saddle point of the zero-sum game in which the defender minimizes and the attacker maximizes ŪA . Its attacker payoff is therefore min max ŪA (σ ′ , a′ ).

σ ′ ∈∆(X ) a′ ∈A

For any σ and any a ∈ BRA (σ), ŪA (σ, a) = maxa′ ŪA (σ, a′ ), which is at least the minimax value. This proves both statements. Theorems 6.1 and 6.2 give nonnegative defender and attacker payoff differences between mixed SSE and mixed NE. The range of C(a) bounds those differences. Theorem 6.3. Let Cmin = min C(a),

Cmax = max C(a).

a∈A

a∈A

NE , µNE ) satisfy Under (61), a mixed SSE (σ SE , aSE σ ) and any mixed NE (σ NE NE 0 ≤ ŪD (σ SE , aSE , µ ) ≤ Cmax − Cmin , σ ) − ŪD (σ Cmax − Cmin NE NE 0 ≤ ŪA (σ SE , aSE ,µ ) ≤ . σ ) − ŪA (σ λ

(65) (66)

pay Proof. Let ∆pay D and ∆A denote the defender and attacker payoff differences on the left sides of pay (65) and (66). Theorem 6.1 gives ∆pay D ≥ 0, and Theorem 6.2 gives ∆A ≥ 0. Apply (64) to the SSE outcome and take its expectation at the NE: SE SE SE ŪD (σ SE , aSE σ ) + λŪA (σ , aσ ) = C(aσ ),

ŪD (σ NE , µNE ) + λŪA (σ NE , µNE ) = Ea∼µNE [C(a)]. Subtracting gives pay SE ∆pay D + λ∆A = C(aσ ) − Ea∼µNE [C(a)].

(67)

Both quantities on the right lie in [Cmin , Cmax ], so their difference is at most Cmax − Cmin . Since the two terms on the left are nonnegative, each is individually bounded by that range, with the attacker term divided by λ. This yields (65)–(66).

6.5

Weighted Zero-Sum Case

The gap bounds become zero when C(a) is the same for every attacker action. Because the empty action belongs to A and C(∅) = 0, the common value must be zero. Since singleton route actions are available, this requires ct = 0 for every target. Together with (61), this is equivalent to u UD (t) = −λUAu (t),

d UD (t) = −λUAd (t),

24

∀t ∈ T .

(68)

SE SE Theorem 6.4. Assume (68). Let (z SE , aSE z ) be an optimal pure Stackelberg outcome, (σ , aσ ) a mixed SSE, and (σ NE , µNE ) any mixed NE. Then strong and pessimistic tie-breaking give the same defender value, and SE SE NE NE UD (z SE , aSE , µ ), z ) ≤ ŪD (σ , aσ ) = ŪD (σ

UA (z

SE

SE SE NE NE , aSE , µ ). z ) ≥ ŪA (σ , aσ ) = ŪA (σ

(69) (70)

Moreover, the defender payoff gain from randomization satisfies SE SE ŪD (σ SE , aSE σ ) − UD (z , az )   SE SE = λ UA (z SE , aSE z ) − ŪA (σ , aσ ) .

(71)

UD (z, a) = −λUA (z, a)

(72)

Proof. Equation (68) gives for every pure outcome, and hence the same identity for all mixed outcomes. If two attacker actions are tied in attacker utility against a defender strategy, they are also tied in defender utility by (72). Strong and pessimistic tie-breaking therefore coincide. Let vA = min max ŪA (σ, a) σ∈∆(X ) a∈A

be the attacker value of the zero-sum game. Every mixed NE has attacker payoff vA and defender payoff −λvA . For a defender mixture σ, every attacker best response has utility maxa ŪA (σ, a), so the defender’s mixed Stackelberg value at σ is −λ max ŪA (σ, a). a∈A

Maximizing this expression over σ is equivalent to minimizing the inner maximum. Thus the mixed SSE has attacker payoff vA and defender payoff −λvA , proving the equalities in (69)– (70). A pure defender configuration is a degenerate mixed strategy, so restricting the defender to pure strategies cannot improve its maximum payoff. This proves the defender inequality in (69). Multiplying that inequality by −1/λ and using (72) gives the attacker inequality in (70). Finally, subtracting UD = −λUA at the pure and mixed Stackelberg outcomes yields (71) exactly. Without the common ratio condition, a mixed SSE still weakly improves the defender’s mixed Nash payoff by Theorem 6.1, but the attacker payoff has no universal ordering. The evaluation uses the general model in which payoffs vary by target and then checks the specialized identities separately on small constructed profiles.

7

Evaluation

We evaluate four questions. First, how does the exact shortest path response to an observed pure configuration compare with route generation against a mixed defender strategy? Second, how closely does RADAR approximate exact optimization over pure configurations, and how much does adaptive refinement improve over RAD repair alone? Third, how closely do RGR’s restricted Nash and mixed Stackelberg solutions match fully enumerated references, and what diagnostics remain when exhaustive enumeration is unavailable? Fourth, do small constructed instances satisfy the payoff relationships in Section 6? 25

The evaluation contains 51,929 recorded rows. We distinguish exact comparisons from diagnostics over generated actions: a zero generated action gap is not a global certificate unless the corresponding exact oracle was used.

7.1

Experimental Setup

Graph families and instance counts. The enumerable experiments use diamond graphs (DGs) with |V| ∈ {4, 7} and random geometric graphs (RGGs) with |V| ∈ {6, 7, 8}. Diamond graphs provide controlled alternative routes, while RGGs provide irregular topology. Each topology and size contains 100 independently parameterized instances. The restricted game records also include Diamond-10, RGG-9, and RGG-10. Full enumeration is unavailable for these larger settings, so we report completion rates and generated action diagnostics but not exact route or defender payoff comparisons. For optimization over pure configurations, the baseline resource vector (BD , Csrv , P̄fa ) and separate 0.75× and 1.25× changes to each component produce seven resource cases per instance. This gives 700 cases per enumerable topology and 3,500 cases overall. We pool the seven cases for each topology. Sensing parameters. Each edge supports three sensing actions. Their base detection probabilities, false alarm probabilities, deployment costs, and server loads are, respectively, {0.30, 0.58, 0.76},

{0.0015, 0.0035, 0.0055},

{0.75, 1.20, 1.35},

{0, 0, 0.85}.

An edge perturbation δe is added to each base detection probability, with δe ∼ Unif[−0.035, 0.035] for DGs and δe ∼ Unif[−0.045, 0.045] for RGGs. Across both graph families, the three resulting detection ranges are [0.255, 0.345], [0.535, 0.625], and [0.715, 0.805]. Implementation. The implementation is written in C++ and uses Gurobi for the finite optimization problems. Experiments run on an AMD Ryzen 9 9950X3D workstation with 96 GB of memory. The greedy baseline starts with no sensing and repeatedly selects the feasible single upgrade with the largest increase in defender utility, stopping when none improves the objective. Reported runtimes are arithmetic means per case. The reporter treats differences within 10−8 as numerically exact and displays every value with magnitude below 10−12 as 0 throughout this section and Appendix E. The path enumerator also records whether it reaches its candidate cap; no reported row does. Reproducibility boundary of the supplied records. The supplied records do not specify the RGG connection radius, source and target selection rule, payoff generation rule, baseline resource vector, initial restricted action sets, or RGR iteration cap. We do not infer these settings; they should be added from the experiment configuration before public release. All numerical statements below use only the available records.

7.2

Metrics

For a mixed defender strategy with an exhaustively enumerable attacker action set, let a+ be the generated action and define the route response gap route gA = max ŪA (σ, a) − ŪA (σ, a+ ) ≥ 0. a∈A

26

(73)

The evaluator stores the absolute numerical value of this gap. Checks for an observed pure configuration compare both non-detection probability and utility with exhaustive enumeration, but do not store a numerical gap once the check passes. For optimization over pure configurations, let VD⋆ be the exact optimum under the selected tie-breaking rule and let VD be the method’s value. Let RD be the defender payoff range over the enumerated reference actions. The normalized defender gap is gD =

VD⋆ − VD . RD

(74)

An exact match means that this difference is within the reporter tolerance. For restricted mixed games, define the signed normalized payoff difference δD =

VDfull − VDRGR . RD

(75)

For Nash play, VDfull and VDRGR are payoffs from equilibria selected by the solver. Their difference is not an optimality gap when either game has multiple equilibria. For mixed Stackelberg play, the values compare selected SSEs of the fully enumerated and restricted games, but omitted attacker actions can make the restricted value optimistic or pessimistic. We therefore report both signed and absolute differences where available.

7.3

Attacker Response: Pure Configuration versus Mixed Strategy

The test for an observed pure configuration covers 500 baseline instances: 100 each for Diamond-4, Diamond-7, RGG-6, RGG-7, and RGG-8. The Dijkstra response passes exhaustive checks of nondetection probability and utility in all 500 cases, confirming the construction in Theorem 4.1 on the tested instances. For mixed defender strategies, the support generator applies Dijkstra to each configuration in supp(σ), the surrogate generator produces the Kcand shortest paths under (52), and the combined generator uses their union. Every candidate is reevaluated under the exact expectation. Table 2 aggregates the enumerable Nash and mixed SSE records. Table 2: Route generation against mixed defender strategies over enumerable cases. “Exact” is the fraction within 10−8 of exhaustive attacker utility. Support records are pooled across the three candidate counts because that generator ignores Kcand . Candidate source Support Surrogate, Kcand = 1 Surrogate, Kcand = 4 Surrogate, Kcand = 8 Combined, Kcand = 1 Combined, Kcand = 4 Combined, Kcand = 8

Exact comparisons

Exact (%)

Mean route gap

Max route gap

3000 1000 1000 1000 1000 1000 1000

53.8 92.9 96.4 98.6 95.0 97.5 99.2

1.5131 × 10−2 1.3840 × 10−3 5.6274 × 10−4 2.6848 × 10−4 6.7948 × 10−4 2.4170 × 10−4 6.0360 × 10−5

2.543 × 10−1 2.162 × 10−1 7.554 × 10−2 7.554 × 10−2 7.968 × 10−2 4.319 × 10−2 1.761 × 10−2

The support generator shows why best responses to individual pure configurations are insufficient for a hidden mixed defense: only 53.8% of the pooled records contain an exact expected utility best 27

response among those routes. The surrogate recovers routes that are not optimal for any support configuration. Increasing Kcand from 1 to 8 raises its exact rate from 92.9% to 98.6% and reduces its mean route gap by about a factor of five. The combined generator performs best at every tested candidate count; at Kcand = 8, it matches 992 of 1000 exhaustive responses and has mean gap 6.04 × 10−5 . The remaining misses are concentrated in RGG-8. With combined Kcand = 8, all Diamond-4, Diamond-7, RGG-6, and RGG-7 attacker responses are exact for both Nash and mixed SSE strategies. RGG-8 is exact in 96 of 100 Nash cases and 96 of 100 mixed SSE cases, with mean gaps 2.627 × 10−4 and 3.409 × 10−4 , respectively. These results support the use of the combined generator but do not constitute an approximation bound; Theorem 5.2 rules out a general exact oracle that runs in polynomial time unless P = NP.

7.4

Optimization over Pure Defender Configurations

All four methods return feasible configurations in every one of the 3,500 cases under both strong and pessimistic tie-breaking. The exact match rates and normalized gaps are identical under the two tie-breaking rules in the supplied records; mean runtimes differ only slightly. Table 3 uses the pessimistic runtimes and pools the five topology settings, each of which contributes 700 cases. Table 3: Optimization over pure configurations in 3,500 cases. Gaps are percentages of the enumerated defender payoff range RD . Method Exact enumeration RADAR RAD Greedy

Exact match (%)

Mean gap (%)

Max gap (%)

Time (ms)

Objective evals

100.0 47.3 23.1 14.4

0 3.640 8.714 42.852

0 48.36 75.47 77.99

19.020 0.329 0.189 0.0265

15912.5 242.2 164.8 19.1

Adaptive refinement reduces RAD’s mean gap from 8.71% to 3.64% and raises its exact match rate from 23.1% to 47.3%. The additional objective evaluations therefore recover substantial payoff that feasibility repair alone discards. Greedy is faster but has a 42.85% mean gap, showing that locally adding sensing from the empty configuration is much less effective than repairing a dense configuration and then reconsidering removed or misplaced sensing actions. Table 4 separates the topology settings. The exact enumerator is slightly faster than RADAR on Diamond-4 because the complete action space is tiny: it evaluates about 34 configurations, compared with about 42 RADAR evaluations. From Diamond-7 onward, exact enumeration is 8.7–116.5 times slower and uses 9.8–137.9 times as many objective evaluations. The largest contrast occurs on RGG-8, where exact enumeration averages 56,810 evaluations and 68.6 ms, while RADAR averages 412 evaluations and 0.589 ms. The gaps are not monotone in graph size. RGG-6 has the largest RADAR mean gap even though RGG-7 and RGG-8 are larger, while RGG-8 has the largest gap in a single case. This is consistent with a local search whose quality depends on the placement of routes that affect payoffs and on resource bottlenecks, not only on vertex count. The maximum gaps also emphasize that RADAR is a heuristic with no general approximation guarantee.

28

Table 4: Pure configuration results by topology under pessimistic tie-breaking. Strong tie-breaking gives the same quality metrics. Topology Diamond-4 Diamond-7 RGG-6 RGG-7 RGG-8

7.5

Exact (%)

Mean gap (%)

RADAR Max gap (%)

Evals

Time (ms)

Evals

Exact Time (ms)

82.1 22.7 55.1 43.4 33.1

0.221 2.023 7.112 5.066 3.777

3.338 9.673 40.69 45.53 48.36

41.8 182.3 226.1 348.7 412.1

0.0510 0.2398 0.2845 0.4789 0.5889

33.6 3657 2212 16,850 56,810

0.0409 4.277 2.484 19.70 68.60

Mean gap (%) RAD Greedy 0.498 4.911 12.48 14.08 11.60

35.81 74.04 42.91 39.22 22.28

Restricted Mixed Games versus Fully Enumerated Games

Table 5 compares restricted solutions from the combined generator with Kcand = 8 against fully enumerated games. It reports 100|δD |. All 1,000 runs (500 Nash and 500 mixed SSE) in the five enumerable settings produce a restricted solution and an exact defender payoff comparison. Table 5: RGR versus selected solutions of fully enumerated games using the combined generator with Kcand = 8. Entries are 100|δD | (%). Topology

Nash Mean Max

Mixed SSE Mean Max

Diamond-4 Diamond-7 RGG-6 RGG-7 RGG-8

2.058 0 0.040 0.231 0

4.340 0 0.819 15.69 0

2.058 0 0.041 0.064 0

4.340 0 0.819 0.646 0

All

0.466

15.69

0.433

4.340

For Nash play, the mean absolute normalized difference is 0.466%. Because the two games may select different equilibria, this is a payoff difference rather than an optimality gap. The 15.69% maximum on RGG-7 is one outlier; the other 99 RGG-7 runs average 0.075%. In the outlying run, the route gap and measured gains from generated deviations are zero. Thus, no generated action improves the selected restricted equilibrium, but an ungenerated defender configuration or a different equilibrium of the fully enumerated game may still do so. For mixed Stackelberg play, the mean absolute normalized difference is 0.433% and the maximum is 4.34%. Diamond-4 has essentially exact route and generated action diagnostics but a 2.058% mean defender payoff difference across every candidate mode and count. Thus, route response quality alone does not determine the value of a restricted game: an omitted defender column, an omitted designated attacker response, or selection under strong tie-breaking can still affect payoffs. Conversely, RGG-8 has zero defender payoff difference even though the mean route gaps are 2.627 × 10−4 for Nash and 3.409 × 10−4 for mixed Stackelberg play. The omitted routes in those cases do not change the selected equilibrium payoff. Increasing Kcand improves route response accuracy more consistently than defender payoff agreement. A route gap evaluates one follower response at one defender mixture, whereas the restricted game payoff also depends on defender columns, alternative designated responses, tiebreaking, and equilibrium selection. A numerically accurate current response is therefore not a certificate for the fully enumerated game. 29

7.6

Larger Instances without Exhaustive References

The expanded records include larger settings for which complete action enumeration and exact payoff comparison are unavailable. Table 6 reports the combined Kcand = 8 completion rate and mean generated action gap. These gaps cover only generated actions. Table 6: RGR on larger settings with the combined generator and Kcand = 8. No comparison with a fully enumerated game is available. Topology

Game

Diamond-10 Diamond-10 RGG-9 RGG-9 RGG-10 RGG-10

Nash Mixed SSE Nash Mixed SSE Nash Mixed SSE

Completed (%)

Mean generated action gap

100 100 100 100 87 100

0 0 1.059 × 10−3 8.968 × 10−4 2.472 × 10−1 9.791 × 10−5

Diamond-10 completes every run with zero generated action gaps. RGG-9 also completes every run, although its remaining gaps are about 10−3 . On RGG-10, the mixed SSE procedure completes all 100 runs with a small mean gap, whereas the Nash procedure completes 87 and has a much larger mean gap. These records show that the restricted method can remain operational when exact enumeration is unavailable, but they do not establish proximity to a fully enumerated solution. Here, “completed” means that the procedure returned under its implemented stopping conditions, not that it certified the global game.

7.7

Numerical Checks of Nash–Stackelberg Relations

The evaluator includes one profile on three vertices for each of three payoff families: heterogeneous single route payoffs, common ratio payoffs, and weighted zero-sum payoffs. These are deterministic consistency checks, not a statistical experiment. Table 7 summarizes the results. Table 7: Checks of the payoff relationships in Section 6. Profile

Checked statement

All three

Mixed SSE defender payoff is at least the mixed NE defender payoff Mixed NE attacker payoff equals the minimax value Pure and mixed SSE attacker payoffs are at least the mixed NE payoff UD + λUA = C(a) and the two gap bounds hold UD + λUA = 0, mixed SSE and mixed NE payoffs coincide, and pure/mixed ordering holds Randomization gain identity (71) A pure SSE automatically has no profitable unilateral defender deviation

Heterogeneous, single route Heterogeneous, single route Common ratio Weighted zero sum Weighted zero sum All three

Result Pass; zero residual Pass; residual 0 Pass; zero residual Pass; zero residual Pass; zero residual Pass; zero residual Fail, with residuals 8, 5, and 8

The failed final row is expected and useful. Proposition 6.1 states a condition for a pure Stackelberg outcome to be a pure NE; it does not claim that the condition holds automatically. The

30

positive residuals are direct counterexamples to that false implication. All identities and inequalities that are actually predicted by Theorems 6.1–6.4 pass on their corresponding profiles.

7.8

Evaluation Summary and Limitations

The experiments support the structural divide developed in the analysis. Against an observed pure configuration, routing is exact and inexpensive, so RADAR can test hundreds of local configurations while remaining under 1 ms on average. Against a mixed defender strategy, exact routing and defender response are NP-hard; the combined route generator is highly accurate on the enumerable cases, and the restricted games often match selected fully enumerated payoffs closely, but gaps over generated actions are not global guarantees. The RGG-7 Nash outlier and the larger RGG-10 Nash results show why this distinction matters. The numerical conclusions have four principal limitations. Exact comparisons stop at Diamond-7 and RGG-8. Normalized gaps depend on the enumerated payoff range RD . Nash payoff differences can reflect equilibrium selection rather than unilateral regret. Finally, the supplied records omit several generation parameters listed in Section 7.1. Appendix E reports the aggregates underlying the condensed tables.

8

Conclusion

We studied resource-aware intrusion detection in infrastructure networks where sensing type, processing mode, deployment cost, edge server capacity, false alarms, and attacks that adapt their routes interact in one graph model. The same pure action spaces support three strategic settings. Simultaneous play may have no pure Nash equilibrium but always has a mixed one. When the attacker observes a pure defender configuration, its exact best response reduces to one shortest path computation followed by independent decisions about which targets to attack. The defender’s pure Stackelberg optimization remains NP-hard. When the attacker observes a mixed defender strategy but not its realization, a mixed SSE exists, a pessimistic optimum may fail to be attained, and both exact response oracles and mixed Stackelberg optimization are NP-hard. These results motivate different computational roles for the proposed methods. RADAR exploits the inexpensive exact response to evaluate repairs, upgrades, and exchanges for pure configurations. RGR uses the same configuration search within restricted Nash and mixed Stackelberg games, together with support and geometric surrogate route candidates. On enumerable instances, the methods have small mean normalized differences from exact or fully enumerated references. Larger experiments show that restricted computation remains possible when exhaustive enumeration is unavailable. The expanded proofs and diagnostics also clarify the limitations: local search has no general approximation bound, and generated action gaps are not global certificates when the underlying response problems are NP-hard. The payoff analysis separates the effects of observability from those of target utilities. Under strong tie-breaking, a mixed SSE always gives the defender at least its mixed Nash payoff. Attacks on a single route give the attacker a minimax characterization even with heterogeneous target values. A common ratio between defender and attacker payoff differences extends that characterization to coordinated attacks on multiple routes and bounds both payoff differences. In the weighted zero-sum case, mixed Nash and mixed Stackelberg payoffs coincide, and the value of defender randomization equals the corresponding reduction in attacker payoff.

31

A

Proof of Theorem 4.3

Proof. We give a reduction, computable in polynomial time, from the decision version of Clique [33]. An instance consists of an undirected graph H = (VH , EH ) and an integer r. The question is whether H contains a set of r vertices with every pair adjacent. Let n = |VH |, assume 1 ≤ r ≤ n, and let dH (v) denote the degree of vertex v in H. Construction. Set M = 2n + 1. Build a monitored graph GH with one source vertex s and one target vertex tv for every v ∈ VH . For each input edge {u, v} ∈ EH , add the edge {tu , tv } between the corresponding target vertices. For every v ∈ VH , add M − dH (v) private intermediate vertices xv,1 , . . . , xv,M −dH (v) . For each private vertex xv,j , add edges {s, xv,j } and {xv,j , tv }. Thus each private vertex forms a separate path of length two from s to tv . There are no other vertices or edges. Every edge supports one perfect sensing action of unit cost, zero false alarm probability, and zero server load. The only active feasibility constraint is a cardinality budget BD = rM − r(r − 1).

(76)

Every target has payoffs UAu = 1,

u d UAd = −1, UD = −1, UD = 1. P The construction contains 1 + n + v (M − dH (v)) = O(n2 ) vertices and O(n2 + |EH |) edges, and all numerical parameters require polynomial encoding length. Call a target tv fully covered if every route from s to tv contains at least one selected sensor. Because the sensors are perfect, a fully covered target has maximum route non-detection probability zero and best route attacker utility −1, so the attacker omits it. If a target is not fully covered, a route with no sensed edge remains undetected with probability one and gives attacker utility 1, so every attacker best response includes an attack on that target. The target decisions are independent and strict, so there are no attacker ties that affect payoffs. If exactly τ targets are fully covered, the attacker attacks the other n − τ targets, each of which gives defender utility −1. The defender value is therefore −(n − τ ). (77)

Maximizing defender utility is equivalent to maximizing the number of fully covered targets. A cut lower bound. For any vertex set U ⊆ V (GH ) with s ∈ / U , define W (U ) = {v ∈ VH : tv ∈ U }. Let EH (W ) be the set of input edges with both endpoints in W , and let δH (W ) be the set of input edges with exactly one endpoint in W . Let δGH (U ) be the cut in the constructed graph. Fix v ∈ W (U ). For each private path s − xv,j − tv , the source s lies outside U and the target tv lies inside U . Whether xv,j lies inside or outside U , at least one of the two path edges crosses δGH (U ). These crossing edges are distinct across private paths. Hence the private paths contribute

32

P at least v∈W (U ) (M − dH (v)) cut edges. Every target–target edge corresponding to an input edge in δH (W (U )) also crosses the constructed cut. Additional cut edges can only increase its size, so X |δGH (U )| ≥ (M − dH (v)) + |δH (W (U ))| (78) v∈W (U )

= M |W (U )| −

X

dH (v) + |δH (W (U ))|.

(79)

v∈W (U )

The degree identity X

dH (v) = 2|EH (W )| + |δH (W )|

v∈W

then gives |δGH (U )| ≥ M |W (U )| − 2|EH (W (U ))|.

(80)

If H has an r-clique, the defender covers r targets. Suppose C ⊆ VH is an r-clique. Let UC = {tv : v ∈ C} and select one sensor on every edge of δGH (UC ). Every source–target route to a target in UC must cross this cut, so all r corresponding targets are fully covered. The cut contains one edge from each private path incident to a target in C, together with the target–target edges leaving C. Its size is X |δGH (UC )| = (M − dH (v)) + |δH (C)| v∈C

= rM − 2|EH (C)|   r = rM − 2 2 = rM − r(r − 1) = BD . Thus the selected sensors are feasible and give defender utility at least −(n − r) by (77). If the defender covers at least r targets, H has an r-clique. Conversely, suppose a set Y of at most BD selected edges fully covers at least r targets. Remove the edges in Y from GH , and let U be the union of all connected components that do not contain s. Every fully covered target is disconnected from s and therefore lies in U . Hence τ = |W (U )| ≥ r. Every edge crossing δGH (U ) must have been removed; otherwise it would connect a component in U to the component containing s. Consequently, |δGH (U )| ≤ |Y| ≤ BD .
A set of τ vertices induces at most τ2 edges, so (80) gives |δGH (U )| ≥ τ M − τ (τ − 1). Define f (x) = xM − x(x − 1). For every integer x < n, f (x + 1) − f (x) = M − 2x = 2n + 1 − 2x > 0. 33

(81)

(82)

Thus f is strictly increasing on {1, . . . , n}. If τ > r, then (82) implies |δGH (U )| ≥ f (τ ) > f (r) = BD , contradicting (81). Therefore τ = r. Substituting τ = |W (U )| = r into (80) and using (81) yields rM − 2|EH (W (U ))| ≤ |δGH (U )| ≤ rM − r(r − 1). Hence

  r(r − 1) r |EH (W (U ))| ≥ = . 2 2
No r-vertex set can induce more than 2r edges, so equality holds and every pair of vertices in W (U ) is adjacent. Thus W (U ) is an r-clique. We have shown that H contains an r-clique if and only if the defender can attain utility at least −(n − r). Therefore deciding whether the optimal pure Stackelberg value reaches that threshold is NP-hard. The attacker decisions are strict in the construction, so strong and pessimistic tie-breaking give the same value. This proves the theorem under both rules.

B

Proof of Theorem 5.1

Proof. We first prove existence under strong tie-breaking. For each attacker action a ∈ A, define its best response region in the defender simplex by  Pa = σ ∈ ∆(X ) : ŪA (σ, a) ≥ ŪA (σ, a′ ), ∀a′ ∈ A . (83) Each inequality is linear and weak, so Pa is a closed polytope. It is contained in the compact simplex ∆(X ) and is therefore compact. Some Pa may be empty, but at least one is nonempty: for every defender mixture, the finite attacker action set has a best response, so the union of the Pa covers the simplex. For every a with Pa ̸= ∅, the defender payoff ŪD (σ, a) is linear and continuous in σ. It therefore attains a maximum on compact Pa . Choose σa ∈ arg max ŪD (σ, a).

(84)

σ∈Pa

There are finitely many attacker actions, so among the nonempty regions choose a⋆ ∈ arg max ŪD (σa , a).

(85)

a:Pa ̸=∅

Because σa⋆ ∈ Pa⋆ , the action a⋆ is an attacker best response to σa⋆ . Now take any defender mixture σ and any a ∈ BRA (σ). Then σ ∈ Pa , so by (84), ŪD (σ, a) ≤ ŪD (σa , a) ≤ ŪD (σa⋆ , a⋆ ). Thus no feasible pair consisting of a defender mixture and one of its attacker best responses gives the defender more than (σa⋆ , a⋆ ). This pair maximizes the strong Stackelberg objective and is a mixed SSE. We next construct an instance in which the pessimistic mixed problem does not attain its supremum. There is one target t with one route r. The defender has two feasible configurations. 34

Configuration z0 leaves the route unmonitored, so qr (z0 ) = 1. Configuration z1 detects with certainty, so qr (z1 ) = 0. Set u d UD (t) = −1, UD (t) = 3, UAu (t) = 1, UAd (t) = −1. The attacker may use ar = {r} or the empty action. The pure payoff table is ar ∅ z0 (−1, 1) (0, 0) z1 (3, −1) (0, 0). Let p = σ(z1 ), so σ(z0 ) = 1 − p. If the attacker uses the route, its expected utility is ŪA (σ, ar ) = (1 − p)(1) + p(−1) = 1 − 2p, and the defender’s expected utility is ŪD (σ, ar ) = (1 − p)(−1) + p(3) = −1 + 4p. The empty action gives both players zero for every p. If p < 1/2, then 1 − 2p > 0, so ar is the unique attacker best response and the pessimistic defender value is −1 + 4p. If p > 1/2, then 1 − 2p < 0, so the empty action is the unique best response and the defender value is zero. At p = 1/2, both attacker actions are best responses. They give the defender utilities 1 and 0, respectively, so pessimistic tie-breaking selects the empty action and gives value zero. Therefore ( −1 + 4p, 0 ≤ p < 1/2, VD− (p) = (86) 0, 1/2 ≤ p ≤ 1. As p approaches 1/2 from below, VD− (p) approaches 1. No p attains value 1: all p < 1/2 give strictly less than 1, and all p ≥ 1/2 give zero. Hence the pessimistic supremum is 1 but is not attained. This completes both parts of the theorem.

C

Proof of Theorem 5.2

Proof. We prove the three claims separately. All reductions use graphs of polynomial size and rational parameters. Part (i): attacker best response via Max-Cut. An instance of Max-Cut is an undirected graph H = (VH , EH ). A cut assigns each vertex a binary label and counts the edges whose endpoints receive different labels. Computing a maximum cut is NP-hard [33]. Let VH = {1, . . . , n} and mH = |EH |. We may assume mH ≥ 1, since an edgeless instance is trivial. Construct a chain of n diamond gadgets. Introduce articulation vertices x0 , x1 , . . . , xn , with source s = x0 and the single target t = xn . For every input vertex i and bit b ∈ {0, 1}, introduce a private branch vertex yib and edges {xi−1 , yib },

{yib , xi }.

The two branches of length two form the ith diamond. Every simple s–t route must pass through the articulation vertices in order and choose exactly one branch in every diamond. Thus each bit 35

vector b = (b1 , . . . , bn ) ∈ {0, 1}n uniquely determines a route rb , and every such route determines one bit vector. Designate the first edge on each branch, gib = {xi−1 , yib }, as an edge that supports sensing. It has one perfect sensing action with unit cost, zero false alarm probability, and zero server load. Set the defender budget to two, so every configuration used below is feasible. For each input edge {i, j} ∈ EH , include two pure configurations in the support of the mixed 01 perfectly senses gates g 1 and g 0 and leaves every other gate defender strategy. Configuration zij i j unsensed. Route rb remains undetected under this configuration if and only if (bi , bj ) = (0, 1). 10 senses g 0 and g 1 , so r remains undetected if and only if (b , b ) = (1, 0). Let σ be Configuration zij i j b i j uniform over these 2mH explicitly listed configurations. For route rb , the non-detection probability under each pure configuration is either zero or one. An input edge with bi = bj contributes no orientation under which the route remains undetected. An input edge with bi ̸= bj contributes exactly one of its two orientations. Therefore q̄rb (σ) =

|{{i, j} ∈ EH : bi ̸= bj }| . 2mH

(87)

Set the single target’s attacker payoffs to UAu = 2mH ,

UAd = −1.

The expected utility of route rb is ŪA (σ, rb ) = −1 + (2mH + 1)q̄rb (σ),

(88)

which is strictly increasing in the cut size. Because mH ≥ 1, some cut contains at least one edge, and its route utility is −1 + (2mH + 1)/(2mH ) = 1/(2mH ) > 0. Thus an optimal route strictly dominates the empty action. Decoding the branch choice of an exact attacker best response yields a maximum cut of H. The graph has O(n) vertices and edges, and the mixed strategy has support 2mH , so the reduction is polynomial. Computing an exact attacker best response is NP-hard even with one target and hence at most one attacked route. Part (ii): pure defender best response via Maximum Coverage. An instance of Maximum Coverage consists of a universe Ω = {1, . . . , N }, subsets S1 , . . . , SL ⊆ Ω, and a budget BC . The objective is to select at most BC subsets whose union has maximum cardinality. The problem is NP-hard because deciding whether BC selected sets can cover all elements is the NP-complete Set Cover decision problem [33]. Create common layer vertices v0 , v1 , . . . , vL . For each set Sj , add a direct gate edge that supports sensing, ej = {vj−1 , vj }. For every element u ∈ / Sj , add a private bypass vertex bu,j and edges {vj−1 , bu,j } and {bu,j , vj }. For every element u ∈ Ω, add a private source su connected to v0 and a private target tu connected to vL . Define a prescribed route ru from su to tu as follows: in layer j, it traverses the gate edge ej if u ∈ Sj and traverses its private bypass if u ∈ / Sj . The unique source and target edges make the prescribed routes distinct even if two elements have the same membership pattern. Only the gate edges ej support sensing. Each has one perfect sensing action of unit cost, and the u = −1 and U d = 1. Let the mixed defender budget is BC . Set every target’s defender payoffs to UD D attacker strategy µ be uniform over the explicitly listed singleton actions {ru }, one for each element. 36

Selecting sensors S on a set of gates indexed by J ⊆ {1, . . . , L} detects route ru with certainty if and only if u ∈ j∈J Sj . A covered element therefore contributes defender utility 1, while an uncovered element contributes −1. If C(J) is the number of covered elements, the expected defender utility against µ is C(J) − (N − C(J)) 2C(J) ŪD (J, µ) = = − 1. (89) N N This expression is strictly increasing in C(J), and the defender feasibility condition is exactly |J| ≤ BC . Hence any pure defender best response identifies a maximum coverage selection. The graph and the explicit attacker support are polynomial in the input size, proving NP-hardness. Part (iii): optimal mixed SSE via 0–1 Knapsack. An instance of 0–1 Knapsack has items i = 1, . . . , n with positive integer costs ci , positive values vi , and budget B. The objective is to choose a subset of total cost at most B and maximum total value; this problem is NP-hard [33]. Construct a star with common source s, one target ti per item, and one edge ei = {s, ti }. Edge ei supports a single sensing action with cost ci , detection probability 1/2, zero false alarm probability, and zero server load. The defender budget is B. The unique route to target ti is ri = ei . Set UAu (ti ) = 1,

1 UAd (ti ) = − , 4

u UD (ti ) = −vi ,

d UD (ti ) = vi .

(90)

If ei is unsensed, route ri remains undetected with probability one and gives attacker utility 1. If ei is sensed, it remains undetected with probability 1/2 and gives attacker utility   1 1 1 3 (1) + − = > 0. 2 2 4 8 For any mixed defender strategy, the expected route utility lies between 3/8 and 1 and is therefore strictly positive. Since there is one route per target and utilities are additive, the unique attacker best response to every pure or mixed defender strategy is the action containing all routes {r1 , . . . , rn }. Tie-breaking plays no role. For the defender, an unsensed item route gives utility −vi , while a sensed item route gives 1 1 (−vi ) + (vi ) = 0. 2 2 Thus sensing item edge ei raises defender utility by exactly vi . For a pure feasible subset J, the defender value is n X X X − vi + vi , ci ≤ B. (91) i=1

i∈J

i∈J

P Maximizing (91) is exactly the knapsack optimization problem, up to the additive constant − i vi . Finally, randomization cannot improve this value. Every mixed defender strategy is a distribution over feasible pure subsets, and the attacker response is the same for every realization and every distribution. Its defender payoff is therefore a convex combination of the pure values in (91), which cannot exceed their maximum. Hence an optimal mixed SSE has the optimal knapsack value and may be chosen pure. Computing an optimal mixed SSE is NP-hard. The three reductions establish parts (i)–(iii).

37

D

Proof of Lemma 6.1

Proof. Let (σ NE , µNE ) be a mixed Nash equilibrium, and let vA = ŪA (σ NE , µNE ) be the attacker equilibrium payoff. We consider separately whether the empty action belongs to the support of µNE . Case 1: the empty action is not in the attacker support. Every supported attacker action is then a singleton route. Write µNE (r) for the probability assigned to action {r}. Define κ=

X

µNE (r)

r∈R

∆D (t(r)) . ∆A (t(r))

(92)

Every term is nonnegative, at least one route has positive probability, and both payoff differences are positive, so κ > 0. Define a reweighted route mixture µ b(r) =

µNE (r)∆D (t(r))/∆A (t(r)) . κ

(93)

The weights are nonnegative and sum to one, so µ b is a valid attacker mixture with support contained in supp(µNE ). P For a defender mixture σ, let q̄r (σ) = z σ(z)qr (z). From (7) and (8), the change in defender payoff against µNE between any two defender mixtures σ1 and σ2 is ŪD (σ1 , µNE ) − ŪD (σ2 , µNE ) X   =− µNE (r)∆D (t(r)) q̄r (σ1 ) − q̄r (σ2 ) .

(94)

r

The corresponding change in attacker payoff against µ b is ŪA (σ1 , µ b) − ŪA (σ2 , µ b) X   = µ b(r)∆A (t(r)) q̄r (σ1 ) − q̄r (σ2 ) r

  1 X NE = µ (r)∆D (t(r)) q̄r (σ1 ) − q̄r (σ2 ) . κ r

(95)

Combining the two equations gives   ŪD (σ1 , µNE ) − ŪD (σ2 , µNE ) = −κ ŪA (σ1 , µ b) − ŪA (σ2 , µ b) .

(96)

The defender Nash condition says that σ NE maximizes defender utility against µNE . Applying (96) with σ1 = σ NE and arbitrary σ2 = σ shows that ŪA (σ NE , µ b) ≤ ŪA (σ, µ b),

∀σ ∈ ∆(X ).

(97)

Thus σ NE minimizes attacker payoff against µ b. Every route in supp(µNE ) is an attacker best response to σ NE and gives the common payoff vA . The reweighted mixture has the same support subset, so it is also a best response and ŪA (σ NE , µ b) = vA . 38

(98)

Equations (97) and (98), together with the fact that µ b maximizes attacker payoff against σ NE , make (σ NE , µ b) a saddle point of the zero-sum game whose payoff to the attacker is ŪA . Therefore vA =

min max ŪA (σ ′ , a′ ).

σ ′ ∈∆(X ) a′ ∈A

(99)

For any defender mixture σ and any best response a ∈ BRA (σ), ŪA (σ, a) = max ŪA (σ, a′ ) ≥ min max ŪA (σ ′ , a′ ) = vA . ′ ′ ′ a ∈A

σ

a

This proves the lemma in the first case. Case 2: the empty action has positive Nash probability. Every pure action in the support of a mixed best response gives the same payoff. The empty action always gives zero, so vA = 0. Since it is a best response to σ NE , no attacker action gives more than zero at that defender mixture; hence max ŪA (σ NE , a) = 0. a∈A

For every defender mixture σ, the attacker can choose the empty action and obtain zero, so max ŪA (σ, a) ≥ 0. a∈A

Consequently, min max ŪA (σ, a) = 0 = vA . σ

a

Any attacker best response to any σ attains the corresponding maximum and therefore has payoff at least zero. This again yields (59) and completes the proof.

39

E

Detailed Evaluation Tables

This appendix reports the aggregates underlying Section 7. The tables retain the evaluator grouping by topology, game, candidate source, candidate count, and tie-breaking rule. Values marked “–” were not available because exhaustive enumeration was not performed. The candidate path cap was never reached, so that redundant column is omitted. As in Section 7, every reported value with magnitude below 10−12 is displayed as 0. Table 8: Exact checks for the Dijkstra response to an observed pure configuration. Topology Diamond-4 Diamond-7 RGG-6 RGG-7 RGG-8

Runs Exact checks Within tolerance (%) 100 100 100 100 100

100/100 100/100 100/100 100/100 100/100

100.0 100.0 100.0 100.0 100.0

Search Dijkstra Dijkstra Dijkstra Dijkstra Dijkstra

40

Table 9: Route generation against mixed defender strategies on instances with exhaustive attacker comparisons.

41

Topology

Game

Candidate source Kcand Runs Exact (%) Mean route gap Max route gap

Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-7

Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash

Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support

– 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 –

300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300

100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 26.0 99.0 100.0 100.0 100.0 100.0 100.0 39.0 98.0 100.0 100.0 100.0 100.0 100.0 52.0 94.0 99.0 100.0 94.0 100.0 100.0 47.0 93.0 100.0 100.0 95.0 100.0 100.0 47.0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.01196 0.0001277 0 0 0 0 0 0.009809 0.0003488 0 0 0 0 0 0.01792 0.0008331 0.0001421 0 0.000768 0 0 0.01724 0.0008019 0 0 0.0005901 0 0 0.02436

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.08003 0.01277 0 0 0 0 0 0.08058 0.02818 0 0 0 0 0 0.1297 0.01468 0.01421 0 0.02206 0 0 0.119 0.01468 0 0 0.0142 0 0 0.1056

Continued on the next page

Table 9 continued from the previous page

42

Topology

Game

Candidate source Kcand Runs Exact (%) Mean route gap Max route gap

RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8

Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE

Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined

1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8

100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100

88.0 93.0 99.0 90.0 95.0 100.0 44.0 90.0 96.0 100.0 94.0 98.0 100.0 55.0 81.0 87.0 96.0 85.0 89.0 96.0 28.0 86.0 89.0 91.0 92.0 93.0 96.0

0.00144 0.000193 2.756 × 10−6 0.001432 0.0001131 0 0.02182 0.001153 0.0002893 0 0.0006107 0.0001869 0 0.02226 0.00441 0.002687 0.001016 0.002296 0.001096 0.0002627 0.02594 0.004725 0.002316 0.001666 0.001098 0.001021 0.0003409

0.04533 0.007716 0.0002756 0.04533 0.004388 0 0.1128 0.03095 0.01784 0 0.03095 0.01784 0 0.2543 0.07968 0.05024 0.04166 0.07968 0.03307 0.01262 0.213 0.2162 0.07554 0.07554 0.04319 0.04319 0.01761

Table 10: Optimization over pure configurations by topology, tie-breaking rule, and method. Gap columns are percentages of the enumerated defender payoff range; runtime is in milliseconds.

43

Topology

Tie rule

Method Feasible (%) Exact (%) Mean gap (%) Max gap (%) Time (ms)

Evals

Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8

Pessimistic Pessimistic Pessimistic Pessimistic Strong Strong Strong Strong Pessimistic Pessimistic Pessimistic Pessimistic Strong Strong Strong Strong Pessimistic Pessimistic Pessimistic Pessimistic Strong Strong Strong Strong Pessimistic Pessimistic Pessimistic Pessimistic Strong Strong Strong Strong Pessimistic Pessimistic Pessimistic Pessimistic Strong Strong Strong Strong

Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy Exact RADAR RAD Greedy

33.57 41.79 32 5 33.57 41.79 32 5 3657 182.3 116 9 3657 182.3 116 9 2212 226.1 163.4 17.12 2212 226.1 163.4 17.12 16,850 348.7 236.6 26.03 16,850 348.7 236.6 26.03 56,810 412.1 275.9 38.32 56,810 412.1 275.9 38.32

100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0

100.0 82.1 67.0 0.0 100.0 82.1 67.0 0.0 100.0 22.7 3.7 0.0 100.0 22.7 3.7 0.0 100.0 55.1 23.0 23.0 100.0 55.1 23.0 23.0 100.0 43.4 10.6 27.7 100.0 43.4 10.6 27.7 100.0 33.1 11.3 21.4 100.0 33.1 11.3 21.4

0 0.2207 0.4977 35.81 0 0.2207 0.4977 35.81 0 2.023 4.911 74.04 0 2.023 4.911 74.04 0 7.112 12.48 42.91 0 7.112 12.48 42.91 0 5.066 14.08 39.22 0 5.066 14.08 39.22 0 3.777 11.6 22.28 0 3.777 11.6 22.28

0 3.338 5.421 61.5 0 3.338 5.421 61.5 0 9.673 10.66 77.99 0 9.673 10.66 77.99 0 40.69 62.27 76.77 0 40.69 62.27 76.77 0 45.53 49.04 77.96 0 45.53 49.04 77.96 0 48.36 75.47 77.64 0 48.36 75.47 77.64

0.04092 0.05098 0.03597 0.00658 0.04654 0.05523 0.03495 0.00637 4.277 0.2398 0.1314 0.01285 4.399 0.2548 0.1313 0.01346 2.484 0.2845 0.1836 0.02213 2.492 0.2963 0.1819 0.02264 19.7 0.4789 0.2729 0.03716 19.69 0.4942 0.2747 0.03668 68.6 0.5889 0.3231 0.05399 68.63 0.5976 0.3233 0.05393

Table 11: RGR on enumerable games. Defender differences are percentages of the enumerated defender payoff range.

44

Topology

Game

Candidate source Kcand

Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-4 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 Diamond-7 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6 RGG-6

Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE

Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined

– 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8

Completed (%)

Max Mean Mean 100δD 100|δD | 100|δD |

100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 2.058 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 0 100.0 -0.0939 100.0 0.054 100.0 0.0478 100.0 0.0402 100.0 0.0421 100.0 0.0382 100.0 0.04 100.0 -0.1133 100.0 0.0311 100.0 0.0441 100.0 0.034 100.0 0.0323 100.0 0.0376 100.0 0.0406

2.058 2.058 2.058 2.058 2.058 2.058 2.058 2.058 2.058 2.058 2.058 2.058 2.058 2.058 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.1683 0.0586 0.0478 0.0402 0.0447 0.0382 0.04 0.1658 0.0357 0.0441 0.034 0.0349 0.0376 0.0406

4.34 4.34 4.34 4.34 4.34 4.34 4.34 4.34 4.34 4.34 4.34 4.34 4.34 4.34 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1.569 0.9174 0.9174 0.8186 0.9174 0.9174 0.8186 1.569 0.696 0.8186 0.8186 0.696 0.8186 0.8186

Mean route Mean generated gap action gap Runs 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.01196 0.0001277 0 0 0 0 0 0.009809 0.0003488 0 0 0 0 0 0.01792 0.0008331 0.0001421 0 0.000768 0 0 0.01724 0.0008019 0 0 0.0005901 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100

Continued on the next page

Table 11 continued from the previous page

45

Topology

Game

Candidate source Kcand

RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-7 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8 RGG-8

Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE

Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined

– 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8

Completed (%) 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0

Max Mean Mean 100δD 100|δD | 100|δD | -0.0713 -0.1005 -0.0975 -0.0836 -0.0982 -0.0972 -0.083 -0.0505 0.0577 0.0672 0.0633 0.0593 0.0621 0.0644 0 0.0062 0 0 0.0062 0 0 0 0 0 0 0 0 0

0.3994 0.2133 0.2162 0.2301 0.2155 0.2165 0.2308 0.1101 0.0579 0.0672 0.0633 0.0593 0.0621 0.0644 0 0.0062 0 0 0.0062 0 0 0 0 0 0 0 0 0

Mean route Mean generated gap action gap Runs

15.14 0.02436 15.69 0.00144 15.69 0.000193 15.69 2.756 × 10−6 15.69 0.001432 15.69 0.0001131 15.69 0 1.44 0.02182 0.6459 0.001153 1.231 0.0002893 0.6459 0 0.6459 0.0006107 0.6459 0.0001869 0.6459 0 0 0.02226 0.6211 0.00441 0 0.002687 0 0.001016 0.6211 0.002296 0 0.001096 0 0.0002627 0 0.02594 0 0.004725 0 0.002316 0 0.001666 0 0.001098 0 0.001021 0 0.0003409

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100

Table 12: RGR on larger games without exhaustive defender payoff comparisons.

46

Topology

Game

Candidate source Kcand Runs

Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 Diamond-10 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-9 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10 RGG-10

Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Nash Nash Nash Nash Nash Nash Nash Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE Mixed SSE

Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined Support Surrogate Surrogate Surrogate Combined Combined Combined

– 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8 – 1 4 8 1 4 8

300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100 300 100 100 100 100 100 100

Completed Mean generated (%) action gap 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 91.0 88.0 84.0 87.0 88.0 86.0 87.0 97.0 100.0 100.0 100.0 99.0 99.0 100.0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0.001059 0 0.0006315 0 0 0 0.0007769 0.0008968 0.1803 0.2955 0.2212 0.252 0.2029 0.2273 0.2472 0.02844 0 0 1.789 × 10−5 0.004716 0.004699 9.791 × 10−5

Table 13: Complete numerical checks of the predicted Nash–Stackelberg payoff relationships. Mean and maximum entries are residuals, and “Bound” is the allowed residual.

47

Profile

Evaluator check

Prediction

Common ratio

common-ratio-attacker-gap-bounds

Common ratio

common-ratio-defender-gap-bounds

Common ratio Common ratio Common ratio

common-ratio-NE-minimax-value mixed-SSE-defender-dominates-NE pure-SSE-is-NE-defender-deviation

Common ratio Heterogeneous Heterogeneous

strategic-zero-sum-identity mixed-SSE-defender-dominates-NE pure-SSE-is-NE-defender-deviation

Heterogeneous Heterogeneous Heterogeneous Weighted zero sum Weighted zero sum Weighted zero sum Weighted zero sum Weighted zero sum Weighted zero sum Weighted zero sum Weighted zero sum Weighted zero sum

single-route-mixed-SSE-attacker-bound single-route-NE-minimax-value single-route-pure-SSE-attacker-bound mixed-SSE-defender-dominates-NE

0 ≤ UA (mixed SSE) − UA (mixed NE) ≤ action constant range/λ 0 ≤ UD (mixed SSE) − UD (mixed NE) ≤ action constant range UA (mixed NE) equals the attacker minimax value UD (mixed SSE) ≥ UD (mixed NE) Pure SSE outcome has no profitable defender deviation UD + λUA = action constant UD (mixed SSE) ≥ UD (mixed NE) Pure SSE outcome has no profitable defender deviation UA (mixed SSE) ≥ UA (mixed NE) UA (mixed NE) equals the attacker minimax value UA (pure SSE) ≥ UA (mixed NE) UD (mixed SSE) ≥ UD (mixed NE)

Passed (%)

Mean

Max

Bound

100.0

0

0

0

100.0

0

0

0

100.0 100.0 0.0

0 0 8

0 0 8

0 0 0

100.0 100.0 0.0

0 0 5

0 0 5

0 0 0

100.0 100.0 100.0 100.0

0 0 0 0

0 0 0 0

0 0 0 0

0.0

8

8

0

randomization-gain-identity

Pure SSE outcome has no profitable defender deviation ∆UD = λ[UA (pure SSE) − UA (mixed SSE)]

100.0

0

0

0

weighted-zero-sum-NE-minimax-value

UA (mixed NE) equals the attacker minimax value

100.0

0

0

0

weighted-zero-sum-payoff-identity

UD + λUA = 0

100.0

0

0

0

weighted-zero-sum-pure-mixed-attacker-bound UA (mixed SSE) ≤ UA (pure SSE)

100.0

0

0

0

weighted-zero-sum-pure-mixed-defender-bound UD (pure SSE) ≤ UD (mixed SSE)

100.0

0

0

0

weighted-zero-sum-SSE-NE-attacker-equality

UA (mixed SSE) = UA (mixed NE)

100.0

0

0

0

weighted-zero-sum-SSE-NE-defender-equality

UD (mixed SSE) = UD (mixed NE)

100.0

0

0

0

pure-SSE-is-NE-defender-deviation

References [1] F. Liu, Y. Cui, C. Masouros, J. Xu, T. X. Han, Y. C. Eldar, and S. Buzzi, “Integrated sensing and communications: Toward dual-functional wireless networks for 6G and beyond,” IEEE Journal on Selected Areas in Communications, vol. 40, no. 6, pp. 1728–1767, 2022. [2] F. Devoti, V. Sciancalepore, I. Filippini, and X. Costa-Perez, “PASID: Exploiting indoor mmWave deployments for passive intrusion detection,” in IEEE INFOCOM 2020 - IEEE Conference on Computer Communications. IEEE, 2020, pp. 1479–1488. [3] J. An, H. Li, D. W. K. Ng, and C. Yuen, “Fundamental detection probability vs. achievable rate tradeoff in integrated sensing and communication systems,” IEEE Transactions on Wireless Communications, vol. 22, no. 12, pp. 9835–9853, 2023. [4] Y. He, M. Xu, F. Xiao, and J. Luo, “VersaBeam: Versatile beamforming for integrated sensing and communication over commodity Wi-Fi,” in IEEE INFOCOM 2025 - IEEE Conference on Computer Communications. IEEE, 2025. [5] Y. Hu, J. Chen, and Q. Zhu, “Game-theoretic Neyman–Pearson detection to combat strategic evasion,” IEEE Transactions on Information Forensics and Security, vol. 20, pp. 516–530, 2025. [6] C. Kiekintveld, M. Jain, J. Tsai, J. Pita, F. Ordóñez, and M. Tambe, “Computing optimal randomized resource allocations for massive security games,” in Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2009, pp. 689–696. [7] D. Korzhyk, V. Conitzer, and R. Parr, “Security games with multiple attacker resources,” in Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI), vol. 22, no. 1, 2011, pp. 273–279. [8] A. Sinha, F. Fang, B. An, C. Kiekintveld, and M. Tambe, “Stackelberg security games: Looking beyond a decade of success,” in Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence (IJCAI), 2018, pp. 5494–5501. [9] N. Basilico, N. Gatti, and F. Amigoni, “Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder,” Artificial Intelligence, vol. 184, pp. 78–123, 2012. [10] M. Jain, D. Korzhyk, O. Vaněk, V. Conitzer, M. Pěchouček, and M. Tambe, “A double oracle algorithm for zero-sum security games on graphs,” in Proceedings of the 10th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), vol. 1, 2011, pp. 327–334. [11] J. Letchford and V. Conitzer, “Solving security games on graphs via marginal probabilities,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 27, no. 1, 2013, pp. 591–597. [12] J. Černý, C. K. Ling, C. Kroer, and G. Iyengar, “Layered graph security games,” in Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024, pp. 2695–2703. [13] T. Mai, A. Bose, A. Sinha, T. Nguyen, and A. K. Singh, “Tackling Stackelberg network interdiction against a boundedly rational adversary,” in Proceedings of the 33rd International Joint Conference on Artificial Intelligence, IJCAI 2024. International Joint Conferences on Artificial Intelligence, 2024, pp. 2913–2921.

48

[14] A. Washburn and K. Wood, “Two-person zero-sum games for network interdiction,” Operations Research, vol. 43, no. 2, pp. 243–251, 1995. [15] M. Dahan, L. Sela, and S. Amin, “Network inspection for detecting strategic attacks,” Operations Research, vol. 70, no. 2, pp. 1008–1024, 2022. [16] J. C. Smith and Y. Song, “A survey of network interdiction models and algorithms,” European Journal of Operational Research, vol. 283, no. 3, pp. 797–811, 2020. [17] E. N. Ciftcioglu, S. Pal, K. S. Chan, D. H. Cansever, A. Swami, A. K. Singh, and P. Basu, “Topology design games and dynamics in adversarial environments,” IEEE Journal on Selected Areas in Communications, vol. 35, no. 3, pp. 628–642, 2017. [18] S. Pal, P. Basu, E. N. Ciftcioglu, K. S. Chan, A. Swami, and D. H. Cansever, “Editing network topologies by playing potential games,” in Proceedings of the 55th IEEE Conference on Decision and Control (CDC), 2016, pp. 7030–7035. [19] S. Pal, E. N. Ciftcioglu, P. Basu, K. S. Chan, and A. Swami, “Decentralized network protection games in adversarial environments,” in Proceedings of the IFIP Networking Conference and Workshops, 2017, pp. 1–9. [20] J. Bhargav, S. Sundaram, and M. Ghasemi, “Sensor scheduling in intrusion detection games with uncertain payoffs,” in Proceedings of the 7th Annual Learning for Dynamics and Control Conference, ser. Proceedings of Machine Learning Research, vol. 283. PMLR, 2025, pp. 606–618. [21] Q. Liu, R. Luo, H. Liang, and Q. Liu, “Energy-efficient joint computation offloading and resource allocation strategy for ISAC-aided 6G V2X networks,” IEEE Transactions on Green Communications and Networking, vol. 7, no. 1, pp. 413–423, 2023. [22] P. Liu, X. Wang, Z. Fei, Y. Wu, J. Xu, and A. Nallanathan, “Latency minimization oriented radio and computation resource allocations for 6G V2X networks with ISCC,” IEEE Transactions on Communications, vol. 73, no. 12, pp. 15 851–15 865, 2025. [23] K. Wang, H. Zhang, Z. Liu, X. Li, and D. Niyato, “Collaborative optimization of sensing, communication and computation functionalities in MEC-assisted ISAC systems,” IEEE Transactions on Cognitive Communications and Networking, vol. 12, pp. 1342–1355, 2025. [24] Z. Liu, X. Chen, H. Wu, Z. Wang, X. Chen, D. Niyato, and K. Huang, “Integrated sensing and edge AI: Realizing intelligent perception in 6G,” IEEE Communications Surveys & Tutorials, vol. 28, pp. 2725–2770, 2026. [25] D. Wen, Y. Zhou, X. Li, Y. Shi, K. Huang, and K. B. Letaief, “A survey on integrated sensing, communication, and computation,” IEEE Communications Surveys & Tutorials, vol. 27, no. 5, pp. 3058–3098, 2025. [26] X. Luo, Z. Li, M. Chen, R. Yu, S. Mao, and Y. Liu, “Unified packet compression and model adaptation for integrated sensing and multi-modal communications,” IEEE Journal on Selected Areas in Communications, vol. 44, pp. 913–926, 2025. [27] A. Chang and E. Amir, “Reachability under uncertainty,” in Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, 2007, pp. 41–48.

49

[28] M. Jain, E. Kardeş, C. Kiekintveld, F. Ordóñez, and M. Tambe, “Security games with arbitrary schedules: A branch and price approach,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 24, no. 1, 2010, pp. 792–797. [29] R. Stolkin and I. Florescu, “Probability of detection and optimal sensor placement for threshold based detection systems,” IEEE Sensors Journal, vol. 9, no. 1, pp. 57–60, 2009. [30] R. Viswanathan and P. K. Varshney, “Distributed detection with multiple sensors: Part I— fundamentals,” Proceedings of the IEEE, vol. 85, no. 1, pp. 54–63, 1997. [31] J. Nash, “Non-cooperative games,” Annals of Mathematics, vol. 54, no. 2, pp. 286–295, 1951. [32] D. Korzhyk, Z. Yin, C. Kiekintveld, V. Conitzer, and M. Tambe, “Stackelberg vs. Nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness,” Journal of Artificial Intelligence Research, vol. 41, pp. 297–327, 2011. [33] R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of Computer Computations, R. E. Miller, J. W. Thatcher, and J. D. Bohlinger, Eds. New York: Plenum Press, 1972, pp. 85–103.

50

Related documents

• Evolution of Log-Based Detection Rules in Public Repositories#1118542
• Jev-IDS: System One Models for Network Intrusion Detection#1160951
• Jev-IDS: System One Models for Network Intrusion Detection#1156014
• The Next Generation Cognitive Security Operations Center: Network Flow Forensics Using Cybersecurity Intelligence#671904
• Bird-inspired optimization approach using taper-shape transfer function for intrusion detection in IoT networks.#123139