Evolutionary Approach to Security Games with Signaling

1 Introduction

Artificial intelligence is increasingly being used as a decision aide in many real-world scenarios, including for the protection of natural resources, such as wildlife, from illegal activities, such as wildlife poaching. These domains are often modeled as Green Security Games (GSGs) with two competing players [Fang et al., 2015; Wang et al., 2019], the defender and adversary. Finding the Stackelberg Equilibrium [Leitmann, 1978] in such games allows the defender to design an optimal strategy that minimizes attacks given limited resources. These strategies have proven to be effective in multiple real-world deployments, including in Queen Elizabeth National Park in Uganda [Yang et al., 2014].

∗Contact Author

Recently, sensors have emerged for use in these domains as additional defender resources [de Cote et al., 2013; Basilico and Gatti, 2014; Basilico et al., 2015; De Nittis and Gatti, 2018; Bondi et al., 2018]. Because they have the potential to detect an adversary in real time, they hold promise in improving GSG strategies. However, attacks may still occur if no human defender (henceforth, patroller) is nearby to interdict. Security games with signaling (SGS) have been proposed to help address this [Bondi et al., 2020]. In these games, warning signals are sent to an adversary to convey that a patroller is responding, even sometimes when no patroller is truly responding. These must be used strategically [Bondi et al., 2020; Xu et al., 2018], as a total lack of response after a signal would render it meaningless.

However, these methods for solving SGS employ traditional optimization techniques, such as Linear Programming (LP) or Mixed Integer Linear Programming (MILP) and suffer from poor time scalability and large memory requirements. In this paper, we aim to solve SGS with Evolutionary Algorithms (EAs), which are inspired by the process of (biological) evolution. Recently, EAs have been successfully applied to sequential security games [ ˙Zychowski and Ma´ndziuk, 2021a], including games played in continuous space with moving targets [Karwowski et al., 2019], or games with bounded rationality [ ˙Zychowski and Ma´ndziuk, 2021b].

Motivated by finding a scalable algorithm for SGS, we propose Evolutionary Algorithm for Security Games with Signaling (EASGS), the first metaheuristic for SGS based on an EA. In particular, we propose: (a) a novel defender-centered chromosome representation to facilitate an EA-based approach to SGS, (b) evolutionary operators, including a novel mutation and crossover approach, a population refreshing scheme, and local (memetic) optimizations, (c) a new set of benchmark games with various underlying graph structures, designed to reflect real-life SGS scenarios, (d) improved performance over state-of-the-art methods based on MILP and reinforcement learning (based on a substantial adaptation of [Venugopal et al., 2021], which we call m-CombSGPO) in terms of expected payoffs, time scalability, and memory.

Due to space limits, certain aspects related to the game scenario, EASGS implementation details, parameterization, and benchmark games are further discussed in supplementary material [ ˙Zychowski et al., 2022].

2 ProblemDefinition

We consider repeated interactions between defender and adversary agents, assuming there is only one adversary. Note that EASGS can be easily applied to games with multiple adversaries, as only chromosome evaluation needs to be modified, however, we focus on one adversary for comparison purposes. The defender resources consist of l sensors and k patrollers. The sensors can detect an adversary in real time and notify the patrollers. There is uncertainty in the detection, as automatic detection in conservation drone imagery may be imperfect, particularly given occlusions such as trees. We specifically consider false negative detections as in [Bondi et al., 2020; Basilico et al., 2016; Basilico et al., 2017].

In addition to sending notifications after a detection, sensors can also send two potential signals to an adversary, represented by σ0 and σ1. We consider σ0 to be a weak signal, e.g., if considering a conservation drone as in [Bondi et al., 2020], no lights are illuminated aboard the drone. On the other hand, σ1 is a strong signal, e.g., lights are illuminated aboard the drone. Typically, we think of the strong signal as indicating that a patroller is (likely) responding, i.e., the lights turn on to deter the adversary. There is also observational uncertainty when the adversary observes the signal, again due to potential occlusions or difficulties viewing the true signal.

Sensors cannot directly prevent an attack, only signal to an adversary or notify the patrollers regarding an observation (which we assume is always done on an observation). If the adversary is deterred from attacking by a signal, both the defender and adversary receive 0 utility. If patrollers are at a target with an adversary, or nearby, they can interdict. The defender receives a positive utility if an attack is prevented successfully, while the defender receives a negative utility if an attack is successful. The opposite is true for the adversary.

The geography of the protected region is modeled using a graph, G = (V,E), where each potential target in the region is represented by a vertex ν ∈ V . If a sensor and patroller are at vertices connected by an edge ϵ ∈ E, the patroller can successfully respond to that sensor's notification to prevent an attack. The number of vertices, |V |, is denoted by N.

If there are no observations by either patrollers or sensors, patrollers may move to a neighboring vertex to have another chance of preventing an attack. This is known as the reaction stage, and is particularly useful if there is detection uncertainty, as a patroller would be able to move to a neighboring vertex with a sensor if the sensors have high uncertainty. Therefore, the order of the game is as follows: the defender first fixes their mixed strategy offline, then carries out a pure strategy allocation. The adversary proceeds to choose a target, and then may be detected by the defender's sensors. The defender may send a signal from the sensor and/or patrollers to respond to notifications, or re-allocate in the reaction stage. The adversary may observe the signal and react (flee). The game scenario is depicted in Figure 1.

A defender pure strategy, e, therefore consists of an allocation of l sensors, an initial allocation of k patrollers, and a reaction stage allocation of k patrollers to neighboring vertices. The defender also has a signaling scheme, which is a series of probabilities over all targets and states. There are different signaling schemes when there is or is not a detection, as [Bondi et al., 2020] found that it was necessary to occasionally signal without a detection due to uncertainty. Per the Stackelberg model, the adversary knows (only) the defender mixed strategy and signaling scheme.

In SGS, two sources of uncertainty are considered: detection uncertainty and observational uncertainty. The detection uncertainty is related to the limited capability of sensors, e.g., false negative detections. In real-life scenarios, a sensor's imperfection (whether the detection algorithm, the sensor itself, or both) can cause mistakes in reporting an adversary's presence. The most common situation is a false negative detection, i.e., a sensor misses the adversary due to, for example, poor visibility, weather conditions, occlusions, or even a power outage. In order to account for this, a probability of its occurrence is denoted by γ. Namely, the sensor with a probability equal to γ does not note the adversary's presence in the target during an attack.

The observational uncertainty is related to the adversary's observation of a signal. The true state may differ from the adversary's observation, i.e., the adversary may not notice the presence of a sensor or signal, possibly due to occlusions or other conditions. There are therefore 3 possible signaling states: (1) the sensor is not present in the target vertex at all (denoted by n), (2) the sensor is present, but does not send a strong signal (it sends a weak signal: σ0), (3) the sensor is present and sends a strong signal: σ1. Let us denote a conditional probability that the adversary will observe state ˆω while the true signaling state is ω by P[ˆω|ω]. Then, we can define an observational uncertainty matrix Π.

3 RelatedWork

[Bondi et al., 2020] achieves state-of-the-art performance solving the problem described in the previous section. We omit the details for the sake of brevity, but in short, they adapt the multiple linear programs (LPs) approach from [Conitzer and Sandholm, 2006]. By maximizing the defender expected utility for an LP at each vertex, the strategy yielding the highest defender expected utility of all LPs is the optimal strategy overall. Unfortunately, each LP is exponential in the number of possible pure strategies. The baseline method proposed in [Bondi et al., 2020] solves each exponential LP to get an exact solution. We will also compare with this when possible, and refer to it as the exponential LP method (SELP).

In order to solve the problem more efficiently, [Bondi et al., 2020] adapt the branch-and-price method. The overall idea is that they can (1) speed up solving each individual LP by using column generation, i.e., adding pure strategies gradually based on the result of a mixed integer linear program (MILP), and (2) use the branch and bound technique by solving a relaxation of each LP and pruning. We will denote this algorithm as branch-and-price (SBP) in comparisons. The most efficient method proposed in [Bondi et al., 2020] uses the same branch-and-price method, but greedily generates an initial set of pure strategies for the LPs. We will denote this as branch-and-price with warm-up (SBP+W).

Another approach (called CombSGPO) proposed in [Venugopal et al., 2021] is based on reinforcement learning, using competitive gradient descent and a multi-agent Deep QNetwork [Van Hasselt et al., 2016] (MADQN) to solve a zerosum game between the defender and the adversary on a grid graph. Our game model differs from [Venugopal et al., 2021] by imposing no restrictions on the game graph topology, allowing a wider range of adversary's observation-reaction scenarios, and using different defender's strategy representation. We modify CombSGPO to work with our general-sum game model on any type of graph and call it m-CombSGPO (modified CombSGPO). m-CombSGPO uses an actor-critic algorithm for computing the defender mixed strategy for allocation and reallocation, in the space of defender pure strategies [Bondi et al., 2020]. Observing this mixed strategy, the adversary, represented by an actor-critic algorithm, chooses the target. Since we have a reaction stage instead of a patrolling stage like in [Venugopal et al., 2021], instead of using a MADQN, we use a sensor signaling network, a neural network to choose the sensor (drone) signaling strategy, followed by an adversary decision neural network to choose whether the adversary should continue attacking or flee, both trained using the policy gradient algorithm [Sutton et al., 2000]. mCombSGPO is used as a reinforcement learning baseline.

4 Evolutionary Algorithm

We propose a novel Evolutionary Algorithm for Security Games with Signaling (EASGS). EASGS is a populationbased algorithm, which means that a set of individuals representing solutions (i.e., defender's mixed strategies) iteratively evolve to find the optimal solution. Each individual is represented in the form of a chromosome. Initially, a population of npop chromosomes is randomly generated. Then, evolutionary operators (crossover, mutation, local optimization, and selection), which are described in detail in the following subsections, are repeatedly applied in subsequent generations. A total of npop chromosomes are maintained throughout the process of applying these operators, and ultimately, this leads to a final set of solutions.

Chromosome representation. Each chromosome encodes a valid solution, i.e., a candidate defender's mixed strategy, in the form of a list of pure strategies and their respective probabilities, and the sensors' signaling strategy:

CHj = {(ej1 , qj1 ), . . . , (eji , qj i ), . . . , (ejdj , qjdj ), Ψθj , Φθj } where CH represents the chromosome, j ∈ {1, . . . , npop} is the individual's identifier, dj is the number of pure strategies included in the mixed strategy represented by the chromosome CHj, eji ∈ E is a pure strategy in the set of pure strategies, qj i ∈ [0, 1] is the probability of pure strategy eji , ∑dj i=1 qj i = 1. θ ∈ {¯ s, s+, s-} are allocation states: ¯ s when no patroller is in the sensor's neighbourhood (i.e., no one can respond to a notification), s+ when a sensor has a patroller who will visit in the reaction stage (and could respond), s- when no patroller will visit in the reaction stage (but there is a patroller in at least one neighbouring vertex who could respond), Ψθj = [Ψθj,1 ,Ψθj,2 , . . . ,Ψθj,N ] is the sensors' signaling strategy when an adversary is detected, i.e., Ψθj,ν is the conditional probability 1 that the sensor at vertex ν sends signal σ0 given the allocation state θ and that it detects an adversary, Φθj = [Φθj,1 ,Φθj,2 , . . . ,Φθj,N ] is the sensors' signaling strat-

egy in the case of no adversary detection, i.e., Φθj,ν is the conditional probability that the sensor at vertex ν sends signal σ0 given the allocation state θ and that it does not detect an adversary.

Pure strategies, e, are represented by tuples which contain defender's decisions according to the game rules described in problem definition section: e = (Vp, Vs, Vr), where Vp = {ν p 1 , ν p 2 , . . . , ν p k } ⊆ V is the patrollers' allocation plan, i.e., a set of vertices in which patrollers will be placed, Vs = {ν s 1 , ν s 2 , . . . , ν s l } ⊆ V is the sensors' allocation plan, Vr = {ν r 1 , ν r 2 , . . . , ν r k } ⊆ V is the patrollers' reallocation plan, i.e., the neighboring vertices to which each patroller moves if no adversaries are observed; the ik-th patroller moves from vertex ν p ik to ν r ik (if relevant edge in the graph exists).

Observe that in [Bondi et al., 2020], a pure strategy is defined in a vertex-centered way, i.e. each vertex is assigned an allocation state (please consult [Bondi et al., 2020] for the details). In EASGS, we propose a defender-centered strategy representation. Instead of focusing on the state of each vertex, a list of "actions" to be performed by the defender is encoded (i.e., to which vertices patrollers/sensors will be allocated/reallocated). Both encodings are equivalent, albeit, the latter one makes formulation of evolutionary operators (especially mutation) simpler and more effective.

Initial population. At the beginning, the population is initialized with individuals containing only one pure strategy: ∀j dj = 1 ∧ qj1 = 1. These strategies are generated randomly according to the game rules defined in the problem definition, i.e., Vp, Vs, Vr are randomly selected subsets of V , and each element of Ψθ and Φθ (signaling probability) is chosen uniformly at random from the unit interval.

1 In [Bondi et al., 2020], ψθ /xθ , where x is the marginal probability of state θ.

Crossover. The crossover operation combines two chromosomes by merging their sets of pure strategies such that the resulting child strategy contains a union of two parent strategies. A probability of each pure strategy in the resulting child chromosome depends on the previous probability (in the parent chromosome) and its utility (defender's payoff in case of playing this pure strategy). Formally, the probability of pure strategy e in the child chromosome is set to: 2u(e) q where q is the probability of strategy e in the parent chromosome and u(e) is its utility, i.e. the defender's payoff when playing strategy e, normalized to interval [-1; 1]. In particular, probability of the best pure strategy is doubled (its normalized utility equals 1), whereas that of the pure strategy with the lowest utility is halved (normalized utility equals -1). After that, the probabilities of all pure strategies are normalized so as to sum to 1. The intuition behind the above setting is to strengthen pure strategies with higher utilities and weaken lower-valued ones while, at the same time, not neglecting any of them. The above crossover definition extends the one proposed in [ ˙Zychowski and Ma´ndziuk, 2021a] in which utilities of strategies are not considered and all probabilities are first halved, and then normalized to 1.

Sensors' signaling strategies Ψθ and Φθ in the child chromosome contain the averaged signaling probability from each parent. A result of the crossover operation on chromosomes CH1 and CH2 will be the new chromosome, CH1-2:

Repeating crossover operation in subsequent generations without any means of strategy removing would lead to chromosomes with a large number of pure strategies with tiny probabilities. To avoid this, after the crossover operation, each pure strategy eji in the child chromosomeCHj is deleted with probability (1-qj i )2 . The choice of deletion probability was empirically found to keep a good balance between the removal of less significant strategies (with lower qj i values) and the overall size of a mixed strategy. After deletion, the probabilities of the remaining pure strategies are normalized

A set of chromosomes that are subject to crossover is chosen randomly in the following way. First, each individual from the population is selected for the crossover with crossover probability Pc. Then, all selected chromosomes are randomly paired, and a crossover operation is performed. In the case of an odd number of individuals, a randomly chosen one is removed. From each set of parents, one new child chromosome is created and added to the population. An example crossover process is presented in Figure 2. The crossover operation helps in exploitation of the solution space by mixing strategies found so far.

Mutation. The mutation operator is applied to each chromosome CHj from the current population independently with probability Pm. There are 3 types of mutations: probability change (M1), allocation/signaling strategy modification (M2) and coverage improvement (M3).

Probability change (M1 : Rdj ↦→ Rdj ) assigns a new prob-

ability ρ (uniformly drawn from the unit interval) to a randomly selected pure strategy eji . Then, a softmax function is applied to all probabilities in a chromosome: ∀i qj i ′ := qj i Στ qjτ . Thus, the M1 mutation can be formulated as follows: M1([qj1 , . . . , qj i , . . . , qjdj ]) = [qj1 ′, . . . , ρ, . . . , qjdj ′]. M1 modifies the influence of particular pure strategies on the result. Allocation/signaling strategy modification (M 1 2 : E ↦→ E, M 2 2 : [0, 1]N ↦→ [0, 1]N ) randomly selects one of the pure strategies (M 1 2 ) or signaling strategy (M 2 2 ) in the mutated chromosome. In case of M 1 2 , a random perturbation is applied to a randomly chosen part of that pure strategy (Vp, Vs, or Vr). It means that the randomly selected sensor/patroller allocation/reallocation vertex νold is changed to another one (νnew), selected randomly: M 1 2 ((Vp, Vs, Vr)) = (V ′ p , V ′ s , V ′ r ) and ∃!zVz ̸= V ′ z : z ∈ {p, s, r}, Vz = (ν1, . . . , νold, . . . , νk), V ′ z = (ν1, . . . , νnew, . . . , νk).

In the case of M 2 2 , a random element of the signaling probability strategy Ψθ or Φθ (θ ∈ {¯ s, s+, s-}) is changed to the complementary probability: M 2 2 (Ψθ ) = Ψθ′ and ∃!z∈{1,...,N}: Ψθ = [Ψθ1 , . . . ,Ψθz , . . . ,ΨθN ], Ψθ′ = [Ψθ1 , . . . , 1 - Ψθz . . . , ΨθN ], with an analogous operation for Φθ . By applying a random perturbation, M2 aims to explore new areas of the search space to find potential improvements.

Coverage improvement (M3 : E ↦→ E) is based on information from the evaluation process from the previous generation. In the evaluation procedure, the adversary's optimal strategy is computed (see Evaluation below), which contains a target vertex, νadv, that the adversary will choose. Thus, a natural idea is to increase the coverage probability of this vertex. This is realized by randomly finding a pure strategy that does not cover νadv (i.e., no patroller or sensor is allocated to this vertex), and adding νadv either to Vp or Vs in this strategy, in place of another randomly selected vertex νrand: M3((Vp, Vs, Vr)) = (V ′ p , V ′ s , Vr) and ∃!zVz ̸= V ′ z : z ∈ {p, s}, Vz = (ν1, . . . , νrand, . . . , νk), V ′ z = (ν1, . . . , νadv, . . . , νk) . Observe that it is not guaranteed that this greedy approach will improve the defender's strategy. In some situations, however, the lack of target coverage is done purposefully and increases the final expected payoff.

If a chromosome is chosen for mutation based on Pm, one of the three above described mutation types is randomly chosen and applied to the chromosome (see Figure 2). This procedure is repeated until a better-fitted chromosome is obtained or mlimit trials is reached. After each unsuccessful mutation attempt, the chromosome is reverted to its state before mutation. The last mutation attempt is kept even if it leads to a lower-fitted chromosome. In preliminary experiments we observed that, in case none of the mutation attempts returned a better individual, keeping the best mutated individual is not statistically superior to simply using the last resulting individual.

Evaluation. After population initialization, as well as crossover and mutation, a post-processing step (local optimization) takes place to ensure chromosomes' feasibility. Next, the evaluation procedure calculates the fitness value of each chromosome which is the defender's expected payoff when the mixed strategy encoded in the chromosome is played. Since it is proven in [Conitzer and Sandholm, 2006] that for Stackelberg Games there always exists at least one best adversary's response to the defender's mixed strategy in the form of a pure strategy, it is sufficient to evaluate the defender's strategy against all pure adversary strategies.

To this end, we first determine the adversary's strategy by iterating over all possible adversary's pure strategies. Each adversary's pure strategy contains a commitment to allocation (vertex to be attacked) and signaling reaction scheme (response to observed signals - run away or continue the attack). For each possible pair (a vertex and a signaling reaction scheme), players' payoffs are computed. Next, we choose the adversary's strategy yielding the best adversary payoff, and determine the defender's payoff for this scenario, which is considered the expected defender's payoff. This value is assigned as the chromosome fitness value.

To compute players' payoffs, we determine the marginal probability xθν of the presence of a patroller, a sensor, or no defender resource at the currently attacked vertex based on the list of allocation pure strategies e and their corresponding probabilities q. Then, for each defender's pure strategy, each of the three possible states ((1)-(3) below) is considered separately and assumed to be the final defender's strategy. The respective defender's payoff is multiplied by the marginal probability. The following three states are considered: (1) In the case of a patroller's presence in the vertex, the defender simply catches the adversary. (2) If neither a patroller nor a sensor are located in the attacked vertex, then the resulting payoff depends on the patroller's reallocation. If a patroller is reallocated to the attacked vertex in the reaction stage, the adversary will be caught. (3) The last possibility is that a sensor is located in the attacked vertex (and there is no patroller allocated). In that case, two scenarios must be considered, depending on whether or not the sensor detects the adversary. The probability of each scenario is defined by

γ, the detection uncertainty. The probability of sending signal σ0, given by Ψθ and Φθ , depends on several factors: the adversary's detection, the signaling strategy, and the reallocation state (whether there is a patroller in the neighborhood that will visit this vertex in the reaction stage). All the above information leads to computing the probability of a sensor's signaling strategy 2 :

where Pσ1 (ν) and Pσ0 (ν) are probabilities of sending signals σ1 and σ0 in vertex ν, respectively,

θ ∈ {¯ s, s+, s-} are allocation states,

xθν represents the marginal probability that vertex ν is in the allocation state θ.

xθν is computed based on allocation strategies (ei, qi), for example: xs+ ν = ∑ qi : ν ∈ Vr ⊂ ei.

The next step is to determine the adversary's reaction. Based on the signaling strategy and probabilities of how certain signals can be observed by the adversary (Π), the adversary's reaction is computed which, together with the defender's strategy, allows for computing the final payoffs.

The detailed diagram of the evaluation procedure is presented in supplementary material.

Selection. In order to construct a population for the next generation, the selection procedure is executed on a pool of all parent individuals (the current population), and the results of crossover and mutation operators (offspring individuals). In the beginning of the selection process, a fixed number, ne of elite individuals from this pool are automatically promoted to the new population. The elite individuals are top-ranked chromosomes with the highest fitness values.

Next, the following iterative procedure is executed until the next generation population is filled with npop individuals. In each iteration, two chromosomes are randomly drawn with return from the pool. Then, from this pair, the one with a higher fitness value is promoted to the next generation with probability Psp (selection pressure). Otherwise, the lowerfitted one is promoted.

Stop condition. Multiple applications of the proposed operators can, in principle, lead to any arbitrary solution. Repeated crossover can create a mixed strategy with an arbitrary number of pure strategies, M1 can set any probability distribution of these strategies, and M2 applied multiple times is able to transform each arbitrary pure strategy to any other. Hence, any mixed strategy can be potentially achieved through repeated application of these operators, independently of the initial population selection. However, it is difficult to say anything about theoretical time requirements of the method. Providing theoretical convergence guarantees for EAs is generally a challenging task and formal results in this area occur rarely in the literature. Thus, the whole routine (crossover, mutation, local optimization, evaluation, and selection) is repeated until some fixed number of generations ngen is reached.

2 chromosome's identifier (j) is omitted for clarity in equations

Furthermore, if for nref (refresh) generations a payoff of the top-ranked individual does not change, some fresh chromosomes are added to the population, i.e., we randomly select half of the population, which is replaced by the same number of new individuals with randomly assigned pure strategies, generated in the same way as in the initial population. The best individual is preserved and cannot be deleted. This approach avoids getting stuck in sub-optimal solutions and shifts the population to new potentially better areas.

5 Experimental Setup

Access to the data from the real-world scenario is strictly secured, e.g. to protect the locations of wild animals and rangers resources, so we randomly generated 342 artificial games with various utilities, graph architectures, numbers of vertices, patrollers, and sensors. All generated games are publicly available on github.com/easgs/benchmark games.

EASGS was compared with the exact approach, SELP, and the three heuristic methods: SBP, SBP+W and mCombSGPO, summarized in Related Work. Results for nondeterministic algorithms (including EASGS) were obtained in 30 independent runs per game instance. Tests were performed on a cluster running CentOS Linux 7 (Core) with Intel(R) Xeon(R) CPU E5-2683 v4 @ 2.1 GHz with 128 GB RAM and 4 cores. EASGS source code can be found on github.com/easgs/source code.

Benchmark games. Let N and ad denote the graph size and the average vertex degree. Games were generated within four groups: sparse (50 games), with ad = 2, moderate (50 games) (ad = N/2), dense (50 games) (ad = N - 2) and locally-dense (192 games), a set of connected cliques.

Sparse, moderate, and dense game graphs were random Watts-Strogatz graphs with N = 10, 20, . . . , 100. In locallydense graphs, the number of cliques and their size varied from 3 to 10. locally-dense games are inspired by certain real-life scenarios, in which there exist areas (cliques) which patrollers can quickly explore, and these are connected via larger links, e.g., roads, which speed up travel. In [Xu et al., 2020], patrollers travel to areas via motorbikes and then patrol on foot. The graphs are further described in supplementary material. Figure 3 presents four examples.

EASGS parameterization. EASGS parameters were tuned on a set of 12 games with 20 vertices (3 games of each type: sparse, moderate, dense and locally-dense), which were separated from the 342 EASGS benchmark graphs and not used during the method evaluation. Based on 5000 runs, the following parameter values were finally chosen: population size npop = 200, crossover probability Pc = 0.5, mutation probability Pm = 0.8, mutation repetition limit mlimit = 10, number of elite chromosomes ne = 2, selection pressure Psp = 0.8, generations limit ngen = 2000, number of generations between refreshes nref = 300.

6 Results and Discussion

The results are averaged over 30 runs and presented in 3 perspectives: payoffs, time scalability, and memory.

Payoffs. SELP managed to calculate the payoffs only for games with up to 20 vertices. For larger games, its memory consumption exceeded the limit of 128 GB. Thus, we were able to compare obtained results with the optimal solution only for 30 game instances - 6 for each of sparse, moderate and dense type, and 12 locally-dense ones. Results for these games are presented in Table 1.

Table 1: In order to make a thorough comparison, we compare the best EASGS, SBP, SBP+W solutions with the optimal ones in terms of both the average difference (left columns) and the ratio between the defender's payoffs (middle columns). Right columns present fractions of games for which optimal solutions were found. Each method is assumed to have reached the optimal result if the returned payoff difference smaller than 0.01. The best results are bolded.

SBP and SBP+W reached optimal solutions in all sparse test games. However, for denser graphs, their accuracy degrades significantly, and overall, the leading method is EASGS. At the same time, EASGS reaches the exact optimal result less frequently (5 out of 30 games). In other words, EASGS is able to find areas with high quality solutions, but may have some difficulties with precise exploitation of those areas. m-CombSGPO (which is based on reinforcement learning) is not a suitable method for finding exact solutions. It has not reached the optimal solution for any game instance and therefore is omitted in Table 1.

Table 2 shows a comparison of heuristic methods based on all 342 test games. The results confirm that EASGS works better for all types of games except for sparse ones, whereas both SBP and SBP+W degrade on denser graphs. The reason may lie in the increasing branching factor of denser games, as each additional connection between vertices opens the possibility for patroller reallocation and enlarges the game strategy tree. In all cases m-CombSGPO reaches the lowest payoffs. Overall, for 200 out of 342 test game instances, EASGS yielded the best result. For each type of benchmark game, the advantage of the winning method (SBP+W for sparse games and EASGS for all other types) is statistically significant according to a 1-tailed paired t-test with a significance level equal to 0.05, and with a normal distribution of data checked by a Shapiro-Wilk test. However, when all 342 games of all types are considered together, it is not statistically significant, with the significance level equal to 0.08. EASGS is also a stable method. The average standard deviation (30 runs of each game) equals 0.86 (about 1.2% of the average absolute payoff - cf. Table 2) with the maximal value of 1.63.

Time scalability. Another critical aspect of the proposed algorithm is time scalability. Figure 4 compares time efficiency of the considered methods. Except for the smallest game graphs and moderate-size sparse ones (where SBP+W performs slightly better), EASGS outperforms all competitive methods, sometimes by a large margin (e.g. on dense graphs). The explanation of this phenomenon is related to the way the EASGS operations are implemented. Action complexity in EASGS is independent of the underlying graph density: mutation assigns vertices to patrollers/sensors randomly, and the topology of connections between vertices (and the number of them) do not influence those choices.

Memory consumption. Although memory consumption is typically not a key factor in recent years, in some cases (especially for methods based on traditional optimization techniques), memory utilization can hinder real-life applications. SELP, for example, consumes more than 200 GB of memory for small games with 20 vertices. At the other extreme, EASGS memory utilization is almost constant. The only data stored in EASGS memory is the game definition and the EA population. This is reflected in Figure 4, which presents memory utilization for all tested methods. Even for 100vertex games, EASGS memory does not exceed 150 MB.

Qualitative analysis. The majority of EASGS resultant mixed strategies contained between 4 to 8 pure strategies (with the mean of 5.3). There wasn't a single resultant strategy with an uncovered vertex, i.e. for each vertex there was at least one pure strategy with a sensor or patroller assigned to that vertex, meaning the target coverage generated by EASGS was complete. Moreover, the patrollers were generally assigned to higher degree vertices, which allowed patrollers to respond to more targets (checked by sensors) during the reallocation stage. Targets with higher defender penalties were generally covered with higher probability. EASGS also considered adversary utilities by protecting targets of high value for the adversary, as well as graph architecture by assigning the vast majority of the sensors to vertices that are connected to targets with assigned patrollers.

7 Conclusion

The paper introduces a novel approach to solving Security Games with Signaling based on the Evolutionary Computation paradigm. The method maintains a population of potential solutions (mixed strategies) and modifies them using specially-designed operators which address domain characteristics. A comprehensive experimental evaluation confirmed that EASGS provides better payoffs than state-of-theart methods, especially for locally-dense graphs that are inspired by real-world settings. Additionally, EASGS largely outperforms competitive methods in terms of time scalability. Thanks to nearly constant memory scalability and the ability to return a valid solution at any time during the execution process, EASGS can be employed to larger games that are beyond the capacity of the state-of-the-art methods. Being well-suited for field computing requirements, EASGS takes us a step closer towards deploying real-world applications on a larger scale to protect valuable natural resources and biodiversity. As future work, we plan to test how well EASGS performs in the field by integrating it with more advanced sensors based on real-world object detection from images.

Acknowledgements

The project was funded by POB Research Centre Cybersecurity and Data Science of Warsaw University of Technology within the Excellence Initiative Program - Research University (ID-UB).

Research was sponsored by the Army Research Office and was accomplished under Grant Number: W911NF-17-10370. The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of Army Research Office or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein.