Project topics and materials
Get Complete Project Material File(s) Now! »
General Stackelberg games{GSGs
Let K be the set of p followers. We denote by I the set of leader pure strategies and by J the set of follower pure strategies. The leader has a known probability of facing follower k 2 K, denoted by k 2 [0; 1]. We denote the n-dimensional simplex by Sn = fx 2 [0; 1]n : Pn xi = 1g. A mixed strategy for the leader consists in a vector x 2 SjIj such that for i 2 I, xi is the probability with which the leader plays pure strategy i. Analogously, a mixed strategy for a follower k 2 K is a vector qk 2 SjJj such that, qjk is the probability with which follower k replies with pure strategy j 2 J. The rewards or payo s for the leader and each follower, resulting from their choice of strategy, are encoded in a di erent matrix for each follower. These payo matrices are denoted by (Rk; Ck), where Rk 2 RjIj jJj is the leader’s reward matrix when facing follower k 2 K and Ck 2 RjI j jJj is the reward matrix for follower k. The expected reward of the leader and follower k, respectively, can be expressed as follows: kRijkxiqjk; (2.1.1).
Stackelberg security games{SSGs
A Stackelberg security game (SSG) is a speci c case of a GSG where the pure strategies for the leader, now referred to as the defender, involve allocating a limited number of security resources (law enforcement o cers, for example) to protect a subset of targets (critical infrastructure, for example) and the pure strategies for each follower type consist in attacking a single target. Formally, let J be the set of n targets that could be attacked and let be the set of m < n security resources available to protect these targets. Allocating resource ! 2 to target j 2 J protects the target. The set I of defender pure strategies i 2 I is composed of all Pm n subsets of at most m targets of J that the defender can protect simultaneously. i=1 i.
The elements j 2 J constitute the pure strategies of each attacker. In SSGs, payo s for the players only depend on whether a target is attacked and whether that target was covered or not. This means that many of the strategies have identical payo s. This fact is used to construct a compact representation of the payo s. We denote by Dk the utility of the defender when facing an attacker k 2 K and by Ak the utility of attacker k. Associated with each target and each player are two payo s depending on whether or not the target is covered, see Table 2.2.1. Further, it is generally assumed that for each j 2 J and k 2 K, Dk(jjc) Dk(jju) and Ak(jju) Ak(jjc), i.e., it is more bene cial for the defender to receive an attack on a protected target instead of su ering an attack on an unprotected target and, similarly, it is more bene cial for the attacker to attack an unprotected target instead of a protected one. Defender Dk(jjc) Dk(jju), Attacker Ak(jjc) Ak(jju) .
The authors in [Kiekintveld et al., 2009] take advantage of the aforementioned com-pact representation to de ne a coverage vector c 2 [0; 1]jJj whose components, cj, rep-resent the probability of coverage of target j. The components of the vector c satisfy P j cj = i2I:j2i xi; 8j 2 J, i.e., the frequency of coverage is expressed as the sum of all probabilities of the strategies that assign coverage to that target. Variables qk indicate whether an attacker k strikes a target j.
Recovering an optimal mixed strategy for the defender{The box method
The box method algorithm presented in this section provides a simple graphic way of recov-ering an optimal mixed strategy x, solution to the GSG, and which is easily implementable by the leader, based on the vector c of optimal coverage probabilities returned by the com-pact SSG. The box method algorithm’s construction and validity comes from a result, and its constructive proof, for scheduling problems found in [McNaughton, 1959]. In their work, the authors consider m processors, which are exactly alike, and there are J = f1; : : : ; ng tasks that need to be completed. Each task j has a processing time cj. The tasks can be split in any number of ways, but two processors cannot work on the same task at the same time. The following theorem, which is a speci c case of the result in [McNaughton, 1959], guarantees the existence of a schedule.
Theorem 2.2.1. If j2J cj m, then a necessary and su cient condition that there exists a schedule in which all tasks are completed by time 1 is that, for all j 2 J, cj 1. In our setting, the m processors correspond to the security resources, the tasks, that need to be completed, correspond to the targets, that need to be covered, and the processing time of a task corresponds to the coverage probability on a target. In the constructive proof of Theorem 2.2.1, the authors construct a schedule where the following condition is ful lled: the schedule of every processor, with the possible exception of one, is either entirely lled up or is entirely empty. The schedule is constructed as follows. One stacks up the optimal cj values consecu-tively inside m columns, which represent the processors/resources, of height one, from left to right. Whenever a column is topped up, one can either start lling up the next column with the remaining quantity of unassigned cj from the previous column, or continue with cj+1. Further, upon inspection of the resulting diagram, one can determine, before a pro-cessor switches task, all tasks that are currently being processed and the time taken before a given con guration of tasks being processed changes. In our setting these con gurations correspond to the pure strategies{coverage of m targets{and the time taken between con g-uration changes, corresponds to the probability with which the coverage con guration prior to the change occurs. Algorithm 1, summarizes the steps required to recover the defender’s implementable mixed strategy.
General Stackelberg games{GSGs
In Section 4.2.1, we present equivalent MILP formulations for the p-follower GSG. In Section 4.2.2 we compare the polyhedra of the LP relaxations for the di erent formulations.
Single level MILP formulations
The linear relaxation of (MIP-p-Gq;z) appears in [Yin and Tambe, 2012]. The MILP for-mulation is a p-follower extension to the single follower formulation (MIP-1-Gq;z), due to [Conitzer and Korzhyk, 2011]. Formal proofs that the formulations seen thus far are equiva-lent MILP formulations, i.e., that they are valid for the p-follower GSG, appear in [Paruchuri et al., 2008], for (DOBSSq;z;s) and [Paruchuri et al., 2008] and [Kiekintveld et al., 2009] for (D2x;q;s;f ). These proofs show that each of them is equivalent to (QUADx;q;s). The equivalence of (DOBSSz;q) and (D2x;q;f ) is obtained from the Fourier-Motzkin elimination procedure [Dantzig and Eaves, 1973]. The equivalence proof for (MIP-p-Gq;z) is analogous to the proof used to show the equivalence for (DOBSSq;z;s) and omitted here. For com-pleteness, the proof is included in the appendix (See Appendix A, Section A.1). [Paruchuri et al., 2008] state that the big M constants used are arbitrarily large. To be as computationally competitive as possible, we provide the tightest value for each big-M constant in the formulations discussed thus far.
Table of contents :
Acknowledgments
Abstract
Resume
Resumen
1 Introduction
1.1 Game Theory
1.2 Bilevel Programming
2 Problem denition
2.1 General Stackelberg games{GSGs
2.2 Stackelberg security games{SSGs
2.2.1 Recovering an optimal mixed strategy for the defender{The box method
3 State of the art
3.1 Computational complexity
3.2 Computational challenges
3.3 Methods
3.4 Noteworthy extensions
4 A study of general and security Stackelberg game formulations
4.1 Introduction
4.2 General Stackelberg games{GSGs
4.2.1 Single level MILP formulations
4.2.2 Comparison of the formulations
4.2.3 Computational experiments for GSGs
4.3 Stackelberg security games{SSGs
4.3.1 Single level MILP formulations
4.3.2 Comparison of the formulations
4.3.3 Computational experiments for SSGs
4.4 Conclusions
5 Benders decomposition methods
5.1 Introduction
5.2 Benders decomposition
5.3 Decomposition approaches
5.3.1 General Stackelberg games
5.3.2 Stackelberg security games
5.4 Cutting plane approach
5.5 Implementation considerations
5.5.1 Root node cut loop stabilization
5.5.2 Primal lower bound-enhancing heuristics
5.5.3 Primal upper bound-enhancing heuristics
5.6 Computational experiments
5.6.1 Conguring the cutting plane approaches
5.6.2 Comparing the performance of the cutting plane approaches
5.7 Conclusions
6 Stackelberg security games with combined defender strategies
6.1 Introduction
6.2 Problem denition
6.3 Solving the problem
6.3.1 The formulation: (FENCEc;z;q;s;f;g)
6.3.2 Recovering an implementable defender mixed strategy
6.4 Computational experiments
6.4.1 Performance of the two-stage sampling method
6.4.2 Performance of (FENCEc;z;q;s;f;g)
6.5 Conclusions
7 Case Study: Border Protection
7.1 Introduction
7.2 The border patrol problem
7.3 Parameter generation: Constructing the game
7.4 Building software for Carabineros
7.4.1 Parameter estimation software
7.4.2 Deployment generation software
7.5 Computational tests
7.6 Evaluating our deployed system
7.6.1 Evaluating the mathematical model
7.6.2 Evaluating the software
7.7 Conclusions
8 Conclusions and future work
8.1 Summary of main results
8.2 Perspectives
8.3 Closing remarks
Bibliography
