Parallel systems under two sequential attacks with contest intensity variation

Single and double attacks against a system of parallel elements are analyzed. The vulnerability of each element depends on an attacker-defender contest success function. The contest intensity may change from the first to the second attack as determined by a contest intensity variation factor. The defender allocates its resource between deploying elements to provide redundancy, and protecting each element. The attacker allocates its resource optimally across the two attacks, may attack a subset of the elements in the first attack, observes which elements are destroyed in the first attack, and attacks all surviving elements in the second attack. A minmax two period game is analyzed where the defender moves first and the attacker moves second. The paper shows how the contest intensity variation factor affects the defense and attack strategies.     

Defending against multiple different attackers

One defender defends, and multiple heterogeneous attackers attack, an asset. Three scenarios are considered: the agents move simultaneously; the defender moves first; or the attackers move first. We show how the agents’ unit costs of defense and attack, their asset evaluations, and the number of attackers influence their investments, profits, and withdrawal decisions. Withdrawal does not occur in one-period (simultaneous) games between two agents, at least with the commonly used ratio-form contest success function, but can occur in two-period games between two agents. The presence of one particularly strong attacker can cause other attackers to withdraw from the contest if the advantaged attacker appropriates so much of the defender’s asset that it is no longer sufficiently attractive to interest other attackers. In such cases, the defender focuses exclusively on the strong attacker. An advantaged defender may be able to deter attacks by moving first, but will continue to suffer from attacks if moving second. This suggests the importance of proactive rather than reactive defense.     

Individual <Emphasis Type="Italic">versus</Emphasis> overarching protection against strategic attacks

This article considers a system consisting of elements that can be protected and attacked individually and collectively. To destroy the system, the attacker must always penetrate/destroy the collective (overarching) protection. In the case of the parallel system, it also must destroy all elements, whereas in the case of the series system, it must destroy at least one element. Both the attacker and the defender have limited resources and can distribute these freely between the two types of protection. The attacker chooses the resource distribution and the number of attacked elements to maximize the system destruction probability. The defender chooses the resource distribution and the number of protected elements to minimize the system destruction probability. The bi-contest minmax game is formulated and its analytical solutions are presented and analysed. The asymptotical analysis of the solutions is presented. The influence of the game parameters on the optimal defence and attack strategies is discussed.     

Separation in homogeneous systems with independent identical elements

The paper considers strategic defense and attack of a system which can be separated into independent identical homogeneous parallel elements. The defender distributes its resource between separation of the elements and their protection from outside attacks. The attacker distributes its effort evenly among all attacked elements. The vulnerability of each element is determined by a contest success function between the attacker and the defender. The defender can choose a subset of the elements to defend. The attacker does not know which elements are protected and can choose a number of randomly chosen elements to attack. Separation efficiency conditions are formulated dependent on the defender’s and attacker’s budgets, separation costs, contest intensity, and system demand. An algorithm for determining the optimal number of protected elements is suggested for the case when both the defender and the attacker can choose the number of protected and attacked elements freely. The article considers both the cases without and with performance redundancy. Illustrative numerical examples are presented.     

Strategic defense and attack for series and parallel reliability systems

A system of independent components is defended by a strategic defender and attacked by a strategic attacker. The reliability of each component depends on how strongly it is defended and attacked, and on the intensity of the contest. In a series system, the attacker benefits from a substitution effect since attacker benefits flow from attacking any of the components, while the defender needs to defend all components. Even for a series system, when the attacker is sufficiently disadvantaged with high attack inefficiencies, and the intensity of the contest is sufficiently high, the defender earns maximum utility and the attacker earns zero utility. The results for the defender (attacker) in a parallel system are equivalent to the results for the attacker (defender) in a series system. Hence, the defender benefits from the substitution effect in parallel systems. With budget constraints the ratio of the investments for each component, and the contest success function for each component, are the same as without budget constraints when replacing the system values for the defender and attacker with their respective budget constraints.     

False targets efficiency in defense strategy

The paper analyzes the efficiency of deploying false targets as part of a defense strategy. It is assumed that the defender has a single object that can be destroyed by the attacker. The defender distributes its resource between deploying false targets and protecting the object from outside attacks. The attacker cannot distinguish the false targets from the defended object (genuine target). Therefore the attacker has no preferences for attacking one target rather than another target. The defender decides how many false targets to deploy whereas the attacker decides how many targets to attack. The article assumes that both the defender and attacker have complete information and full rationality. The optimal number of false targets and the attacked targets are obtained for the case of fixed and variable resources of the defender and the attacker as solutions of a non-cooperative game between the two agents.     

Parallel systems under two sequential attacks with imperfect detection of the first attack outcome

The paper compares the efficiency of single and double attack against a system consisting of identical parallel elements. An attacker maximizes the system vulnerability (probability of total destruction). In order to destroy the system, the attacker distributes its constrained resource optimally across two attacks and chooses the number of elements to be attacked in the first attack. The attacker observes which elements are destroyed and not destroyed in the first attack and allocates its remaining resource into attacking the remaining elements in the second attack. The paper considers two types of identification errors: wrong identification of a destroyed element as not destroyed, and wrong identification of a not destroyed element as destroyed. First, the influence of the identification error probabilities on the optimal attack strategy against a system with a fixed number of elements is analysed. Thereafter, a minmax two-period game between the attacker and the defender is considered, in which the defender in the first period distributes its constrained resource between deploying redundant elements and protecting them against the attack in the second period. It is shown how the identification error probabilities affect the defence strategy.     

Modeling secrecy and deception in a multiple-period attacker–defender signaling game

In this paper, we apply game theory to model strategies of secrecy and deception in a multiple-period attacker–defender resource-allocation and signaling game with incomplete information. At each period, we allow one of the three possible types of defender signals—truthful disclosure, secrecy, and deception. We also allow two types of information updating—the attacker updates his knowledge about the defender type after observing the defender’s signals, and also after observing the result of a contest (if one occurs in any given time period). Our multiple-period model provides insights into the balance between capital and expense for defensive investments (and the effects of defender private information, such as defense effectiveness, target valuations, and costs), and also shows that defenders can achieve more cost-effective security through secrecy and deception (possibly lasting more than one period), in a multiple-period game.     

A Bilevel p-median model for the planning and protection of critical facilities

The bilevel p-median problem for the planning and protection of critical facilities involves a static Stackelberg game between a system planner (defender) and a potential attacker. The system planner determines firstly where to open p critical service facilities, and secondly which of them to protect with a limited protection budget. Following this twofold action, the attacker decides which facilities to interdict simultaneously, where the maximum number of interdictions is fixed. Partial protection or interdiction of a facility is not possible. Both the defender’s and the attacker’s actions have deterministic outcome; i.e., once protected, a facility becomes completely immune to interdiction, and an attack on an unprotected facility destroys it beyond repair. Moreover, the attacker has perfect information about the location and protection status of facilities; hence he would never attack a protected facility. We formulate a bilevel integer program (BIP) for this problem, in which the defender takes on the leader’s role and the attacker acts as the follower. We propose and compare three different methods to solve the BIP. The first method is an optimal exhaustive search algorithm with exponential time complexity. The second one is a two-phase tabu search heuristic developed to overcome the first method’s impracticality on large-sized problem instances. Finally, the third one is a sequential solution method in which the defender’s location and protection decisions are separated. The efficiency of these three methods is extensively tested on 75 randomly generated instances each with two budget levels. The results show that protection budget plays a significant role in maintaining the service accessibility of critical facilities in the worst-case interdiction scenario.     

Optimal defence of single object with imperfect false targets

The paper considers an object exposed to external intentional attacks. The defender distributes its resource between deploying false targets and protecting the object. The false targets are not perfect and there is a nonzero probability that a false target can be detected by the attacker. Once the attacker has detected a certain number of false targets, it ignores them and chooses such number of undetected targets to attack that maximizes the probability of the object destruction. The defender decides how many false targets to deploy in order to minimize the probability of the object destruction assuming that the attacker uses the most harmful strategy to attack. The optimal number of false targets and the optimal number of attacked targets are obtained for the case of single and multiple types of the false targets. A methodology of finding the optimal defence strategy under uncertain contest intensity is suggested.     

An attrition game on a network ruled by Lanchester’s square law

We consider two-person zero-sum attrition games in which an attacker and a defender are in combat with each other on a network. The attacker marches from a starting node to a destination node, hoping that the initial members survive the march. The defender deploys his forces on arcs in order to intercept the attacker. If the attacker encounters the defender on an arc, the attacker incurs casualties according to Lanchester’s square law. We consider two models: a one-shot game in which the two players have no information about their opponents, and a two-stage game in which both players have some information about their opponents. For both games, the payoff is defined as the number of survivors for the attacker. The attacker’s strategy is to choose a path, and the defender’s is to deploy the defending forces on arcs. We propose a numerical algorithm, in which nonlinear programming is embedded, to derive the equilibrium of the game.     

Defence and attack of systems with variable attacker system structure detection probability

A system consists of identical elements. The cumulative performance of these elements should meet a demand. The defender applies three types of defensive actions to reduce a damage associated with system performance reduction caused by an external attack: deploying separated redundant genuine system elements, deploying false elements, and protecting genuine elements. If the attacker cannot distinguish between genuine and false elements, he chooses a number of elements to attack and then selects the elements at random, distributing his resources equally across these elements. By obtaining intelligence data, the attacker can get full information about the system structure and identify false and unprotected genuine elements. The defender estimates the probability that the attacker can identify all system elements. This paper analyses the influence of this probability in a non-cooperative two-period minmax game between the defender and the attacker.     

The timing and deterrence of terrorist attacks due to exogenous dynamics

In this paper, we develop a model for the timing and deterrence of terrorist attacks due to exogenous dynamics. The defender moves first and the attacker second in a two-stage game which is repeated over T periods. We study the effects of dynamics of several critical components of counter-terrorism games, including the unit defence costs (eg, immediately after an attack, the defender would easily acquire defensive funding), unit attack costs (eg, the attacker may accumulate resources as time goes), and the asset valuation (eg, the asset valuation may change over time). We study deterministic dynamics and conduct simulations using random dynamics. We determine the timing of terrorist attacks and how these can be deterred.     

An attrition game on an acyclic network

This paper deals with noncooperative games in which two players conflict on a network through an attrition phenomenon. The associated problem has a variety of applications, but we model the problem as a military conflict between an attacker and a defender on an acyclic network. The attacker marches from a starting node to a destination node, expecting to keep his initial members untouched during the march. The defender deploys his forces on arcs to intercept the attacker. If the attacker goes through an arc with deployed defenders, the attacker incurs casualties according to Lanchester’s linear law. In this paper, we discuss two games having the number of remaining attackers as the payoff and propose systems of linear programming formulations to derive their equilibrium points. One game is a two-person zero-sum (TPZS) one-shot game with no information and the other is a TPZS game with two stages separated by information acquisition about players’ opponents.     

A cutting-plane algorithm for solving a weighted influence interdiction problem

We consider a two-stage defender-attacker game that takes place on a network, in which the attacker seeks to take control over (or “influence”) as many nodes as possible. The defender acts first in this game by protecting a subset of nodes that cannot be influenced by the attacker. With full knowledge of the defender’s action, the attacker can then influence an initial subset of unprotected nodes. The influence then spreads over a finite number of time stages, where an uninfluenced node becomes influenced at time t if a threshold number of its neighbors are influenced at time t?1. The attacker’s objective is to maximize the weighted number of nodes that are influenced over the time horizon, where the weights depend both on the node and on the time at which that is influenced. This defender-attacker game is especially difficult to optimize, because the attacker’s problem itself is NP-hard, which precludes a standard inner-dualization approach that is common in many interdiction studies. We provide three models for solving the attacker’s problem, and develop a tailored cutting-plane algorithm for solving the defender’s problem. We then demonstrate the computational efficacy of our proposed algorithms on a set of randomly generated instances.     

Heterogeneous surface-to-air missile defense battery location: a game theoretic approach

In the context of an air defense missile-and-interceptor engagement, a challenge for the defender is that surface-to-air missile batteries often must be located to protect high-value targets dispersed over a vast area, subject to which an attacker may observe the disposition of batteries and subsequently develop and implement an attack plan. To model this scenario, we formulate a two-player, extensive form, three-stage, perfect information, zero-sum game that accounts for, respectively, a defender’s location of batteries, an attacker’s launch of missiles against targets, and a defender’s assignment of interceptor missiles from batteries to incoming attacker missiles. The resulting trilevel math programming formulation cannot be solved via direct optimization, and it is not suitable to solve via full enumeration for realistically-sized instances. We instead adapt the game tree search technique Double Oracle, within which we embed either of two alternative heuristics to solve an important subproblem for the attacker. We test and compare these solution methods to solve a designed set of 52 instances having parametric variations, from which we derive insights regarding the nature of the underlying problem. Enhancing the solution methods with alternative initialization strategies, our superlative methodology attains the optimal solution for over 75% of the instances tested and solutions within 3% of optimal, on average, for the remaining 25% of the instances, and it is promising for realistically-sized instances, scaling well with regard to computational effort.     

Bilevel “Defender–Attacker” Model with Multiple Attack Scenarios

We consider a bilevel “defender-attacker” model built on the basis of the Stackelberg game. In this model, given is a set of the objects providing social services for a known set of customers and presenting potential targets for a possible attack. At the first step, the Leader (defender) makes a decision on the protection of some of the objects on the basis of his/her limited resources. Some Follower (attacker), who is also limited in resources, decides then to attack unprotected objects, knowing the decision of the Leader. It is assumed that the Follower can evaluate the importance of each object and makes a rational decision trying to maximize the total importance of the objects attacked. The Leader does not know the attack scenario (the Follower’s priorities for selecting targets for the attack). But, the Leader can consider several possible scenarios that cover the Follower’s plans. The Leader’s problem is then to select the set of objects for protection so that, given the set of possible attack scenarios and assuming the rational behavior of the Follower, to minimize the total costs of protecting the objects and eliminating the consequences of the attack associated with the reassignment of the facilities for customer service. The proposed model may be presented as a bilevelmixed-integer programming problem that includes an upper-level problem (the Leader problem) and a lower-level problem (the Follower problem). The main efforts in this article are aimed at reformulation of the problem as some one-level mathematical programming problems. These formulations are constructed using the properties of the optimal solution of the Follower’s problem, which makes it possible to formulate necessary and sufficient optimality conditions in the form of linear relations.     

Defence resource distribution between protection and decoys for constant resource stockpiling pace

The paper considers the optimal resource distribution between increasing protection of genuine elements and deploying decoys (false targets) in a situation when the attacker's and defender's resources are stockpiling and the resource increment rate is constant. It is assumed that the system must perform within an exogenously given time horizon and the attack time probability is uniformly distributed over this horizon. Series and parallel systems are considered. The defender optimizes the resource distribution in order to minimize the system vulnerability. The attacker cannot distinguish genuine and false elements and can attack a randomly chosen subset of the elements.     

Secure sets and their expansion in cubic graphs

Consider a graph whose vertices play the role of members of the opposing groups. The edge between two vertices means that these vertices may defend or attack each other. At one time, any attacker may attack only one vertex. Similarly, any defender fights for itself or helps exactly one of its neighbours. If we have a set of defenders that can repel any attack, then we say that the set is secure. Moreover, it is strong if it is also prepared for a raid of one additional foe who can strike anywhere. We show that almost any cubic graph of order n has a minimum strong secure set of cardinality less or equal to n/2 + 1. Moreover, we examine the possibility of an expansion of secure sets and strong secure sets.     

Choosing fair lotteries to defeat the competition

We study the following game: each agent i chooses a lottery over nonnegative numbers whose expectation is equal to his budget b _i . The agent with the highest realized outcome wins (and agents only care about winning). This game is motivated by various real-world settings where agents each choose a gamble and the primary goal is to come out ahead. Such settings include patent races, stock market competitions, and R&D tournaments. We show that there is a unique symmetric equilibrium when budgets are equal. We proceed to study and solve extensions, including settings where agents choose their budgets (at a cost) and where budgets are private information.