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.     

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.     

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.     

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.     

New solution approaches for the maximum-reliability stochastic network interdiction problem

We investigate methods to solve the maximum-reliability stochastic network interdiction problem (SNIP). In this problem, a defender interdicts arcs on a directed graph to minimize an attacker’s probability of undetected traversal through the network. The attacker’s origin and destination are unknown to the defender and assumed to be random. SNIP can be formulated as a stochastic mixed-integer program via a deterministic equivalent formulation (DEF). As the size of this DEF makes it impractical for solving large instances, current approaches to solving SNIP rely on modifications of Benders decomposition. We present two new approaches to solve SNIP. First, we introduce a new DEF that is significantly more compact than the standard DEF. Second, we propose a new path-based formulation of SNIP. The number of constraints required to define this formulation grows exponentially with the size of the network, but the model can be solved via delayed constraint generation. We present valid inequalities for this path-based formulation which are dependent on the structure of the interdicted arc probabilities. We propose a branch-and-cut (BC) algorithm to solve this new SNIP formulation. Computational results demonstrate that directly solving the more compact SNIP formulation and this BC algorithm both provide an improvement over a state-of-the-art implementation of Benders decomposition for this problem.     

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.     

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.     

Individual versus overarching protection and attack of assets

Two agents protect and attack a collection of assets overarchingly versus individually. Examples of overarching protection are border security, counter intelligence, and public health measures. Both layers of protection have to be breached for an attack to be successful. We consider a simultaneous game, and a two period game with overarching contest in period 1 and individual contests in period 2 if the attacker wins period 1. With reasonable assumptions, such as contest intensities not exceeding one, the defender prefers two protection layers, while the attacker prefers one protection layer. When the unit effort costs of overarching protection and attack are equal, and the agents’ valuations for each asset are equal, in the simultaneous game defender and attacker efforts are equal in the overarching contest. In contrast, for the two period game, the defender invests more than the attacker in the overarching contest to prevent the occurrence of period 2. If the attacker nevertheless wins period 1, both agents exert larger efforts in period 2 compared with the individual contests in the simultaneous game. Framed within the Colonel Blotto literature, the attacker must win the first battlefield (overarching contest) in order to engage in the contests over the n other battlefields (individual contests).     

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.     

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.     

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.     

A Stackelberg equilibrium for a missile procurement problem

This paper deals with a procurement problem of missiles involving the efficient assignment of the missiles to some targets. Within a fixed amount of budget, a leader purchases several types of missiles, by which he aims to damage as much value as possible a follower hides into some facilities later. The effectiveness of the missile depends on the type of missile and facility. A payoff of the game is the expected amount of destroyed value. The problem is generalized as a two-person zero-sum game of distributing discrete resources with a leader and a follower. Our problem is to derive a Stackelberg equilibrium for the game. This type of game has an abundance of applications. The problem is first formulated into an integer programming problem with a non-separable objective function of variables and it is further equivalently transformed into a maximin integer knapsack problem. We propose three exacts methods and an approximation method for an optimal solution.     

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.     

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.     

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.     

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.     

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.     

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.     

On a class of bilevel linear mixed-integer programs in adversarial settings

We consider a class of bilevel linear mixed-integer programs (BMIPs), where the follower’s optimization problem is a linear program. A typical assumption in the literature for BMIPs is that the follower responds to the leader optimally, i.e., the lower-level problem is solved to optimality for a given leader’s decision. However, this assumption may be violated in adversarial settings, where the follower may be willing to give up a portion of his/her optimal objective function value, and thus select a suboptimal solution, in order to inflict more damage to the leader. To handle such adversarial settings we consider a modeling approach referred to as \(\alpha \)-pessimistic BMIPs. The proposed method naturally encompasses as its special classes pessimistic BMIPs and max–min (or min–max) problems. Furthermore, we extend this new modeling approach by considering strong-weak bilevel programs, where the leader is not certain if the follower is collaborative or adversarial, and thus attempts to make a decision by taking into account both cases via a convex combination of the corresponding objective function values. We study basic properties of the proposed models and provide numerical examples with a class of the defender–attacker problems to illustrate the derived results. We also consider some related computational complexity issues, in particular, with respect to optimistic and pessimistic bilevel linear programs.