Carlos Casorrán
email: ccasorra@ulb.ac.be

Bernard Fortz
email: bernard.fortz@ulb.ac.be

Martine Labbé
email: mlabbe@ulb.ac.be

Fernando Ordóñez

Novel formulations for general and security Stackelberg games

Keywords: Operations Research, Game Theory, Mixed Integer Linear Programming, Bilevel Optimization

niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Stackelberg games (SG) are used to model situations where players with different objectives strive to optimize their payoff in a sequential, one-off encounter. If a party has the capacity to commit to a given action first, it is referred to as the leader, whereas the players responding to the leader's action are referred to as the followers. If there is a single leader and one follower, the payoffs in such a game are encoded in a matrix whose elements are couples. In this matrix, each row represents an action of the leader and each column represents an action of the follower. The payoffs that both players obtain, as a result of selecting a row and column, are determined by the values in the couple at the intersection between the chosen row and column: the first element of the pair is the reward for the leader and the second element of the pair is the reward for the follower. If the leader (resp. follower) commits to a single row (resp. column), he plays a pure strategy whereas if the leader (resp. follower) assigns a probability to a row (resp. column), he plays a mixed strategy. The leader's objective is to take an action-a mixed strategy-that will maximize his payoff, knowing that the follower is aware of such an action and will in turn optimize his own reward by selecting a strategy of his own. When the leader faces a single follower, the problem is polynomially solvable and can be solved using the multiple LP method devised by [START_REF] Conitzer | Computing the optimal strategy to commit to[END_REF]. If there are several followers, each with a distinct payoff matrix, then a classic model, due to [START_REF] Harsanyi | A Generalized Nash Solution for Two-Person Bargaining Games with Incomplete Information[END_REF], combines the leader's rewards over the different followers and assumes a known probability of facing each follower to compute the leader's expected reward. We refer to this as the 'p-follower' problem. This problem has been shown to be NP-hard in [START_REF] Conitzer | Computing the optimal strategy to commit to[END_REF]. Solution methods for this problem are due to [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF], [START_REF] Jain | Quality-bounded solutions for finite bayesian stackelberg games: Scaling up[END_REF], [START_REF] Yang | Scaling-up security games with boundedly rational adversaries: A cutting-plane approach[END_REF], among others. Note that, if the number of follower types is fixed, the problem is then polynomially solvable; the distinct payoff matrices can be transformed into a single payoff matrix, effectively reducing the multiple follower type case to a single follower type case, by applying the Harsanyi transformation [START_REF] Harsanyi | A Generalized Nash Solution for Two-Person Bargaining Games with Incomplete Information[END_REF]. However, the number of follower strategies in this single payoff matrix is exponential in the number of followers. Stackelberg game theory has been recently used to solve real-world security problems. In this domain, the leader is referred to as the defender whereas the followers are referred to as attackers. Stackelberg security game-theoretic applications have included effectively assigning Federal Air Marshals to transatlantic flights [START_REF] Jain | Software assistants for randomized patrol planning for the lax airport police and the federal air marshal service[END_REF], determining randomized patrols for the U.S. Coast Guard to efficiently protect port infrastructure [START_REF] Shieh | Protect: A deployed game theoretic system to protect the ports of the united states[END_REF], preventing fare evasion in public transport systems [START_REF] Yin | Trusts: Scheduling randomized patrols for fare inspection in transit systems using game theory[END_REF] as well as protecting endangered wildlife [START_REF] Yang | Adaptive resource allocation for wildlife protection against illegal poachers[END_REF]. In this paper, we introduce new Mixed Integer Linear Programming (MILP) formulations for p-follower general Stackelberg games and p-attacker Stackelberg security games. The MILP formulations we develop are provably better than existing formulations in the literature as the upper bounds provided by the continuous relaxations of our formulations are tighter than those provided by formulations in the literature. Further, we establish theoretical projection results relating the different formulations and linking the general games with their security counterparts. For the single attacker type scenario, the new linear formulation we propose constitutes a linear description of the convex hull of feasible integer solutions. We perform computational experiments to compare the performance of our formulations with that of existing ones. This paper is organized as follows. In Section 2, we define general and security Stackelberg games. In Section 3, we present general Stackelberg formulations from the literature and introduce a new formulation. Further, we provide theoretical results comparing the formulations presented. In Section 4, we describe our computational experiments for the formulations in Section 3 and subsequent analysis of the results. In Section 5, we present Stackelberg security formulations using projections, in the appropriate space of variables, of the formulations in Section 3. We then extend our theoretical results to the security formulations. In Section 6, we describe and analyze the computational experiments for the security formulations. We conclude with some closing remarks in Section 7.

Notation and definition of the problem

In this section, we provide a formal definition of the two types of problems which are the object of our study.

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 ∈ K, denoted by π k ∈ [0, 1]. We denote the n-dimensional simplex by S n = {x ∈ [0, 1] n : n x i = 1}. A mixed strategy for the leader consists in a vector x ∈ S |I| such that for i ∈ I, x i is the probability with which the leader plays pure strategy i. Analogously, a mixed strategy for a follower k ∈ K is a vector q k ∈ S |J| such that, q k j is the probability with which follower k replies with pure strategy j ∈ J. The rewards or payoffs for the leader and each follower, resulting from their choice of strategy, are encoded in a different matrix for each follower. These payoff matrices are denoted by (R k , C k ), where R k ∈ R |I|×|J| is the leader's reward matrix when facing follower k ∈ K and C k ∈ R |I|×|J| is the reward matrix for follower k. The expected reward of the leader and follower k, respectively, can be expressed as follows:

i∈I j∈J k∈K π k R k ij x i q k j , (1)
i∈I j∈J C k ij x i q k j , ∀k ∈ K. (2)
For all k ∈ K we define the function B k : S |I| -→ S |J| as the function that, given the leader mixed strategy x, returns a best response q k for each follower k. The solution concept employed in these games is the Strong Stackelberg Equilibrium (SSE), introduced in [Leitman, 1978] and defined below.

Definition 1. A profile of mixed strategies (x, {B k (x)} k∈K ) form an SSE if:

1. The leader always plays a payoff-maximizing strategy:

x T R k B k (x) ≥ x T R k B k (x ) ∀x ∈ S |I| , ∀k ∈ K.
2. Each follower always plays a best-response, B k (x) ∈ F k (x), where ∀k ∈ K,

F k (x) = arg max q k {x T C k q k : q k ∈ S |J| }
is the set of best responses for each follower.

3. Each follower breaks ties optimally in favor of the leader:

x T R k B k (x) ≥ x T R k q k ∀q k ∈ F k (x).
An SSE assumes that the follower breaks ties in favor of the leader by choosing, when indifferent between different follower strategies, the strategy that maximizes the payoff of the leader. An SSE is in practice always achievable as the leader can always induce one by selecting a sub-optimal mixed strategy arbitrarily close to the equilibrium, which will cause the follower to prefer the desired strategy [von Stackelberg, 1952].

Remark 1. For any leader strategy x and any k ∈ K, there is a best response to the k-th follower's problem that is given by a vector q k ∈ {0, 1} |J| such that j∈J q k j = 1. Proof. Assume that B k (x) = qk ∈ {0, 1} |J| . We show that any canonical vector e jk such that qk j > 0, is also a best response vector, i.e., e jk ∈ F k (x) and x T R k e jk ≥ x T R k q k for all q k ∈ F k (x). Since qk = j∈J qk j e jk , with e jk ∈ S |J| , and

x T C k e jk ≤ x T C k qk for all j ∈ J, we have that x T C k qk = j∈J qk j (x T C k e jk ) ≤ j∈J qk j (x T C k qk ) = x T C k qk .
This implies that for any qk j > 0 we have x T C k e jk = x T C k qk , giving e jk ∈ F k (x). A similar argument shows that for any j such that qk j > 0 we have x T R k e jk = x T R k qk ; Hence, e jk is a best response vector.

In Mathematical Optimization, Stackelberg games are addressed by Bilevel Programming (BP). Introduced in [START_REF] Bracken | Mathematical programs with optimization problems in the constraints[END_REF], BP targets hierarchical optimization problems in which part of the constraints translate the fact that some of the variables are an optimal solution to another nested optimization problem. The main optimization problem corresponds to the leader's decision problem and the nested problem corresponds to the follower's decision problem. The following model, (BIL-p-G x,q ), provides a bilevel programming formulation of the general Stackelberg game problem:

(BIL-p-G x,q ) Max x,q i∈I j∈J k∈K π k R k ij x i q k j (3) s.t. i∈I x i = 1, (4)
x i ∈ [0, 1] ∀i ∈ I, (5)
q k = arg max r k    i∈I j∈J C k ij x i r k j    ∀k ∈ K, (6)
r k j ∈ {0, 1} ∀j ∈ J, ∀k ∈ K, ( 7
) j∈J r k j = 1 ∀k ∈ K. ( 8
)
The objective function maximizes the leader's expected reward. Constraints (4)-(5) characterize the mixed strategies considered by the leader. The second level problem defined by ( 6)-( 8) indicates that the follower maximizes his own payoff by best responding with a pure strategy to the leader's commitment. If there are multiple optimal strategies for the follower, the main level problem selects the one that benefits the objective of the leader

Stackelberg security games-SSGs

A Stackelberg security game (SSG) involves allocating the defender's security resources to protect a subset of targets. 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 ω ∈ Ω to target j ∈ J protects the target. The set I of defender pure strategies i ∈ I is composed by all m i=1 n i subsets of at most m targets of J that the defender can protect simultaneously. The elements j ∈ J constitute the pure strategies of each attacker. In SSGs, payoffs 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 payoffs. We use this fact to construct a compact representation of the payoffs. We denote by D k the utility of the defender when facing an attacker k ∈ K and by A k the utility of attacker k. Associated with each target and each player are two payoffs depending on whether or not the target is covered, see Table 1.

Covered Uncovered Defender D k (j|c) D k (j|u) Attacker A k (j|c) A k (j|u)
Table 1: Payoff structure in an SSG when target j is attacked by an attacker k [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF] take advantage of the aforementioned compact representation to define a coverage vector c whose components, c j , represent the frequency of coverage of target j. The components of the vector c satisfy c j = i∈I:j∈i x i , ∀j ∈ 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 q k j indicate whether an attacker k strikes a target j. The defender's and attacker k's expected rewards, are, respectively:

j∈J k∈K π k q k j {c j D k (j|c) + (1 -c j )D k (j|u)}, ( 9
) j∈J q k j {c j A k (j|c) + (1 -c j )A k (j|u)}, ∀k ∈ K. ( 10
)
As with GSGs, such a game can be modeled by means of bilevel programming.

(BIL-p-S x,c,q ) Max j∈J k∈K

π k q k j {c j D k (j|c) + (1 -c j )D k (j|u)} s.t. i∈I x i = 1, ( 11
)
x i ≥ 0 ∀i ∈ I, (12)
i∈I:j∈i

x i = c j ∀j ∈ J, (13)
q k = arg max r k    j∈J r k j (c j A k (j|c) + (1 -c j )A k (j|u)    ∀k ∈ K, r k j ∈ {0, 1} ∀j ∈ J, ∀k ∈ K, j∈J r k j = 1 ∀k ∈ K.
The objective function maximizes the defender's expected reward. Constraints (11)-( 13) characterize the exponentially many mixed strategies considered by the defender and relate them to coverage frequencies over the targets. The remaining constraints constitute the second level optimization problem which ensures that the attacker maximizes his profit by attacking a single target, best responding to the defender's selected strategy.

Remark that a more compact formulation-one involving a polynomial number of variables and constraintscan be obtained if projecting out the exponentially many x variables does not lead to exponentially many constraints. This would give a polynomial size formulation involving only the c and the q variables. Given an optimal solution to this compact formulation-an optimal coverage vector c and an optimal attack vector q-a probability vector x, solution to this game in extensive form, can be obtained by solving the system of linear inequalities defined by ( 11), ( 12) and (13). As this system involves n + 1 equalities, there exists a solution in which the number of variables x i with a positive value is not larger than n + 1, i.e., the output size of an SSG, under extensive form, is polynomial in the input size. See Section 5 for more details.

General Stackelberg games-GSGs

We present equivalent MILP formulations for the p follower GSG in Section 3.1 and provide a comparison between the polyhedra of the linear programming relaxations for the different formulations in Section 3.2.

General

Stackelberg games: single level formulations [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF] tackle the problem of solving the bilevel formulation presented earlier, (BIL-p-G x,q ) by using a MILP reformulation. They replace the second level nested optimization problem, described by ( 6)-( 8), by the following set of constraints:

j∈J q k j = 1 ∀k ∈ K, (14)
q k j ∈ {0, 1} ∀j ∈ J, ∀k ∈ K, ( 15
) 0 ≤ (s k - i∈I C k ij x i ) ≤ (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, (16)
where s k ∈ R for all k ∈ K. The two inequalities in Constraint ( 16) ensure that q k j = 1 only for a pure strategy that maximizes the follower's payoff. The problem defined by (3)-( 5) and ( 14)-( 15) is referred to as (QUAD x,q,s ). Formulation (D2 x,q,s,f ), below, avoids the quadratic term in the objective of (BIL-p-G x,q ) by adding |K| new variables and introducing a second family of constraints involving a big M constant.

(D2 x,q,s,f ) Max k∈K π k f k (17) s.t. (14) -(16), f k ≤ i∈I R k ij x i + (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, ( 18
) i∈I x i = 1, ( 19
)
x i ≥ 0 ∀i ∈ I, (20)
s, f ∈ R |K| ∀k ∈ K.
Alternatively, one can eliminate the nonlinearity in the objective function, as discussed in [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF], by adding additional variables that represent the product between x and q. To be more precise, we introduce z k ij = x i q k j for all i ∈ I, j ∈ J and k ∈ K. This gives rise to the following formulation called (DOBSS q,z,s ):

(DOBSS q,z,s ) Max i∈I j∈J k∈K π k R k ij z k ij s.t. (14), (15), j∈J z k ij = j∈J z 1 ij ∀i ∈ I, ∀k ∈ K, ( 21
) i∈I z k ij = q k j ∀j ∈ J, ∀k ∈ K, (22)
z k ij ≥ 0 ∀i ∈ I, ∀j ∈ J, ∀k ∈ K, ( 23
) 0 ≤ s k - i∈I j ∈J C k ij z k ij ≤ (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, ( 24
) s ∈ R |K| .
Additionally, the real variables s k in Constraints ( 16) and ( 24) can be projected out by using Fourier-Motzkin elimination [START_REF] Dantzig | Fourier-Motzkin Elimination and Its Dual[END_REF]. This gives rise to constraints:

i∈I (C k ij -C k i )x i ≤ (1 -q k ) • M ∀j, ∈ J, ∀k ∈ K, ( 25
) i∈I j ∈J (C k ij -C k i )z k ij ≤ (1 -q k ) • M ∀j, ∈ J, ∀k ∈ K. (26)
Replacing ( 16) by ( 25) in (D2 x,q,s,f ) and ( 24) by ( 26) in (DOBSS q,z,s ) yields (D2 x,q,f ) and (DOBSS q,z ). We compare the behavior of these last two formulations compared to that of (D2 x,q,s,f ) and (DOBSS q,z,s ) to evaluate if removing variables s at the expense of adding constraints is worthwile. Another equivalent MILP formulation for the p-follower GSG can be obtained by replacing Constraint (24) with the following constraint:

i∈I (C k ij -C k i )z k ij ≥ 0 ∀j, ∈ J, ∀k ∈ K. ( 27
)
This constraint is derived by multiplying Constraint (25) by q k , reorganizing and replacing the nonlinear terms x i q k j by z k ij . The final equivalent MILP formulation, (MIP-p-G q,z ) is: 14), ( 15), ( 21)

(MIP-p-G q,z ) Max i∈I j∈J k∈K π k R k ij z k ij s.t. (
-(23), i∈I (C k ij -C k i )z k ij ≥ 0 ∀j, ∈ J, ∀k ∈ K. ( 28
)
Formal proofs that these are equivalent MILP formulations, i.e., that they are valid for the p-follower GSG, appear in [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF], for (DOBSS q,z,s ) and [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF] and [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF] for (D2 x,q,s,f ). These proofs show that each of them is equivalent to (QUAD x,q,s ). The equivalence of (DOBSS z,q ) and (D2 x,q,f ) is obtained from the Fourier-Motzkin elimination procedure [START_REF] Dantzig | Fourier-Motzkin Elimination and Its Dual[END_REF].

The equivalence proof for (MIP-p-G q,z ) is analogous to the proof used to show the equivalence for (DOBSS q,z,s ) and is omitted here. [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF] 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.

Proposition 1. The tightest values for the positive constants M are:

1. In (18), M = max i∈I {max ∈J R k i -R k ij } ∀j ∈ J, ∀k ∈ K.
2. In ( 16) and ( 24)

, M = max i∈I {max ∈J C k i -C k ij } ∀j ∈ J, ∀k ∈ K.
3. In ( 25) and ( 26)

, M = max i∈I {C k ij -C k i }, ∀j, ∈ J, ∀k ∈ K.

Comparison of the formulations

Given a formulation F, we denote by F its linear (continuous) relaxation and by P(F) the polyhedral feasible region of F. Further, let

Q = {(x, z) ∈ R n × R m : Ax + Bz ≤ d}.
Then the projection of Q into the x-space, denoted P roj x Q, is the polyhedron given by P roj x Q = {x ∈ R n : ∃z ∈ R m for which (x, z) ∈ Q}, see [START_REF] Pochet | Production Planning by Mixed Integer Programming[END_REF]. First, we introduce an additional formulation which we denote by (DOBSS x,q,z,s,f ). This formulation is equivalent to (DOBBS q,z,s ), in the sense that the values of their LP relaxations coincide. In this formulation we introduce variables f k for all k ∈ K to rewrite the objective function so that it matches (17). We also add variables x i for all i ∈ I by rewriting (21) as j∈J z k ij = x i for all i ∈ I and all k ∈ K. Using this last condition, we can simplify (24) to ( 16). The formulation (DOBSS x,q,z,s,f ) is as follows.

(DOBSS x,q,z,s,f ) Max

k∈K π k f k s.t. (14) -(16), i∈I z k ij = q k j ∀j ∈ J, ∀k ∈ K, (29)
z k ij ≥ 0 ∀i ∈ I, ∀j ∈ J, ∀k ∈ K, (30)
f k = i∈I j∈J R k ij z k ij ∀k ∈ K, (31)
j∈J z k ij = x i ∀i ∈ I, ∀k ∈ K, ( 32
) s ∈ R |K| .
Further, note that from the Fourier Motzkin elimination procedure we have that P(D2 x,q,f ) = P roj x,q,f P(D2 x,q,s,f ) and, P(DOBSS q,z ) = P roj q,z P(DOBSS q,z,s ).

Proposition 2. P roj x,q,s,f P(DOBSS x,q,z,s,f ) ⊆ P(D2 x,q,s,f ). Further, there exist instances for which the inclusion is strict.

Proof. Note that all the constraints of P(D2 x,q,s,f ) can be found in the description of P(DOBSS x,q,z,s,f ) except for Constraints ( 18) and ( 19). Constraint ( 19) is implied by Constraints ( 14), ( 29) and (32). Further, the projection of P(DOBSS x,q,z,s,f ) on the (x, q, s, f )-space can be obtained by applying Farkas' Lemma [Farkas, 1902]. Constraints ( 29), ( 30), ( 31) and ( 32) are the only ones involving variables z k ij to project out and are separable by k ∈ K. For a fixed k ∈ K the projection is given by:

A k = {(x, q, f ) : αf k + i∈I β i x i + j∈J γ j q k j ≥ 0 ∀(α, γ, β) : αR k ij + β i + γ j ≥ 0 ∀i ∈ I, ∀j ∈ J} (33)
For a fixed j ∈ J, define α = -1,

β i = R k ij for all i ∈ I, γ j = 0 and γ = max i∈I (R k i -R k ij
) for all ∈ J with = j. This definition of the parameters satisfies αR k ij + β i + γ j ≥ 0 for all i ∈ I, j ∈ J. Substituting these parameters in the generic constraint of A k yields

f k ≤ i∈I R k ij x i + ∈J: =j max i∈I (R k i -R k ij )q k ∀j ∈ J, ∀k ∈ K. (34)
Constraint (34) implies Constraint (18) for the tight value of M provided in Proposition 1 since for all j ∈ J and k ∈ K,

∈J: =j max i∈I (R k i -R k ij )q k ≤ max i∈I max ∈J R k i -R k ij ∈J: =j q k = max i∈I max ∈J R k i -R k ij (1 -q k j ).
This proves the inclusion. To show that the inclusion may be strict, consider the following example where |I| = |J| = 3 and |K| = 1. Let the payoff matrix for the game be

(R, C) =   (1, 0) (0, 0) (0, 0) (0, 0) (1, 0) (0, 0) (0, 0) (0, 0) (0, 0)  
and consider the point defined by x = (1, 0, 0) t , q = ( 1 3 , 1 3 , 1 3 ) t , s = 10 and f = 2/3. Such a point is feasible for (D2 x,q,s,f ) but violates Constraint (34) for j = 2 and is therefore infeasible for P roj x,q,s,f P(DOBSS x,q,z,s,f ).

Next, we compare the polyhedra P(MIP-p-G q,z ) and P roj q,z P(DOBSS q,z,s ).

Theorem 1. P(MIP-p-G q,z )⊆ P(DOBSS q,z )=P roj q,z P(DOBSS q,z,s ). Further, there exist instances for which the inclusion is strict.

Proof. The description of P(DOBSS q,z ) differs from that of P(MIP-p-G q,z ) by only one constraint: (26) must hold instead of (28). Hence, the remainder of the proof consists in showing that ( 26) is implied by ( 14), ( 21)-( 23), ( 28) and the nonnegativity of the q variables. The LHS of ( 26) can be rewritten as:

i∈I (C k ij -C k i )z k i + i∈I j ∈J:j = (C k ij -C k i )z k ij ≤ i∈I j ∈J:j = (C k ij -C k i )z k ij , using (28), ≤ max i∈I {C k ij -C k i } j ∈J:j = i∈I z k ij ≤ M j ∈J:j = q k j ,
given Proposition 1 and (29) = M (1 -q k ), by (14).

To show that the inclusion may be strict consider the p-follower GSG between a leader and a fixed follower k ∈ K where the payoff bimatrix is:

(R k , C k ) = (0, 1) (1, 0) (0, 0) (0, 0)
The point with coordinates x = (1/2, 1/2) t , q k = (1/2, 1/2) t and

z k = 1/4 1/4 1/4 1/4
has an objective value of 1/4 and is feasible in P(DOBSS q,z ). However it is not a feasible point in P(MIP-p-G q,z ) as it doesn't verify Constraint (28) for values of j = 2 and = 1.

From an interpretation point of view, (MIP-p-G q,z ) can be seen as the result of applying Reformulation Linearization Technique (RLT) [START_REF] Sherali | A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems[END_REF] to (DOBSS q,z ). Indeed, by multiplying both sides of Constraint (25) by variable q k and noticing that q k (1 -q k ) = 0 since q is binary, one obtains

i∈I (C k ij -C k i )x i q k ≤
0 which, once linearized by introducing variables z k i , yields (28). For a given formulation F, we denote its optimal value by v(F) and the optimal value of its LP relaxation by v(F). Since (D2 x,q,s,f ) and (DOBSS x,q,s,f ) and (DOBSS q,z ) and (MIP-p-G q,z ) have the same objective function, the following corollary holds.

Corollary 1. v(MIP-p-G q,z ) ≤ v(DOBSS q,z ) = v(DOBSS x,q,s,f ) ≤ v(D2 x,q,s,f ).
Finally, when (MIP-p-G q,z ) is restricted to a single follower type, [START_REF] Conitzer | Commitment to correlated strategies[END_REF] showed that the integrality constraints are redundant, i.e., the remaining constraints in (MIP-1-G q.z ) provide a complete linear description of the convex hull of feasible solutions.

Computational experiments for GSGs

We present computational experiments for the formulations in Section 3. The machine used for these experiments is an Intel Core i7-4930K CPU, 3.40GHz, equipped with 64 GByte RAM, 6 cores, 12 threads and operating system Ubuntu release 12.10 (kernel linux 3.5.0-41-generic). The experiments were coded in the programming language Python and GUROBI version 6.5.1 was the optimization solver used with a 3 hour solution time limit. The instances solved in the computational experiments are randomly generated. We consider two different ways of randomly generating the payoff matrices for the leader and the different follower types. First, we consider matrices where all the elements are randomly generated between 0 and 10 and second, we consider matrices where 90% of the values are between 0 and 10 but we allow for 10% of the data to deviate between 0 and 100. In the first case we will say that there is no variability in the payoff matrices, in the sense that all the data is uniformly distributed, whereas in the second case, we will refer to the payoff matrices as matrices with variability. A general Stackelberg game instance is defined by three parameters: |I|, the number of leader pure strategies, |J|, the number of follower pure strategies and |K|, the number of follower types. For the purpose of these experiments, we have considered instances where |I| ∈ {10, 20, 30}, |J| ∈ {10, 20, 30} and |K| ∈ {2, 4, 6}. For each instance size, 5 instances are generated without variability in the payoff matrices and 5 are generated with variability. In total, we consider 135 instances without variability and 135 instances with variability. We present performance profiles to summarize the results of this experiment, with respect to the following 4 measures: total running time employed to solve the integer problem, running time employed to solve the linear relaxation of the integer problem, total number of nodes explored in the branch and bound solving scheme and gap percentage at the root node. The gap percentage at the root node is calculated by comparing the optimal values of the formulation and of its LP relaxation:

v(F)-v(F ) v(F )
• 100. A performance profile graph plots the total percentage of problems solved for each value of these measures. We study the behavior of (D2 x,q,s,f ), (D2 x,q,f ), (DOBSS q,z,s ), (DOBSS q,z ) and (MIP-p-G q,z ). Figures 1 and 2 compare the performance profiles when the payoff matrices are generated without variability and with variability, respectively. We observe that the instances where variability is introduced in the payoff matrices solve faster than those where no variability is considered. When there is no variability, (DOBSS q,z,s ) and (MIP-p-G q,z ) are the two most competitive formulations. (D2 x,q,s,f ) can also be solved efficiently for the mid-range instances but significantly slows down for the more difficult to solve instances. Introducing variability in the payoff matrices, however, leads to a dominance of (MIP-p-G q,z ) with (DOBSS q,z,s ) coming in a close second and (D2 x,q,s ) becoming noncompetitive for these instances. In what regards the time spent solving the linear relaxation of the problems, (MIP-p-G q,z ) is the formulation that is hardest to solve, this due to the fact that is has the most variables and constraints, O(|K||J| 2 ). On the other hand, (D2 x,q,s,f ), that has the lightest LP relaxation, with O(|K||J|) variables and constraints, is the fastest. With respect to the number of nodes and gap percentage our theoretical findings are corroborated: (MIP-p-G q,z ) is the tightest formulation and therefore uses the fewest nodes. The effect is further intensified when variability in the payoff matrices is introduced. Table 2 summarizes the mean gap obtained across the instances solved. Finally, remark that the formulations obtained through Fourier-Motzkin, (D2 x,q,f ) and (DOBSS q,z ), explore slightly less nodes in the branch and bound scheme than their counterparts, (D2 x,q,s,f ) and (DOBSS q,z,s ), but because of the increase in the number of constraints the time to solve each linear relaxation increases. This increases the overall solution time of the Fourier-Motzkin formulations.

(D2 x,q,s,f ) (DOBSS q,z,s ) (MIP-p-G q,z )

Stackelberg security games-SSGs

In this section, we will derive three SSG formulations. We will do this by exploring the inherent link between the general setting we have considered up to now and the security setting defined in Section 2.2. In this setting, the defender pure strategies i ∈ I are the different ways in which up to m targets can be protected simultaneously. For this problem, we refer to i ∈ I as a set indicating which targets are covered by security resources. Recall that the payoff matrices of SSGs satisfy:

R k ij = D k (j|c) if j ∈ i D k (j|u) if j / ∈ i (35) C k ij = A k (j|c) if j ∈ i A k (j|u) if j / ∈ i (36)
The payoff for the leader when he commits to a pure strategy i ∈ I and a follower of type k ∈ K responds by selecting strategy j ∈ J is either a reward if pure strategy i ∈ I allocates security coverage to attacked target j ∈ J, or, a penalty if strategy i does not cover target j. The same argument explains the link between payoffs for the attackers.

Stackelberg security games: single level formulations

The first formulation we derive is based on (D2 x,q,s,f ). Consider (D2 c,x,q,s,f ), an extended description of (D2 x,q,s,f ) where we introduce the c variables through Constraint (13) (see Section 2.2). We further use i∈I:j∈i

x i = c j ∀j ∈ J (38) j∈J q k j = 1 ∀k ∈ K, (39)
q k j ∈ {0, 1} ∀j ∈ J, ∀k ∈ K, ( 40
) i∈I x i = 1, (41)
x i ≥ 0 ∀i ∈ I (42) 0 ≤ s k -A k (j|c)c j -A k (j|u)(1 -c j ) ≤ (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, (43)
f k ≤ D k (j|c)c j + D k (j|u)(1 -c j ) + (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, (44)
s, f ∈ R K .
This extended formulation is equivalent to (D2 x,q,s,f ), because, even though they are defined in different spaces of variables, the value of their LP relaxations coincide.

The formulation above has a large number of non-negative variables since in the security setting, the set I of all defender pure strategies is exponential in the number of targets as it contains all subsets of at most m targets of J that the defender can protect simultaneously. In order to avoid having exponentially many non-negative variables in our formulation, we project out variables x i , i ∈ I, from the formulation. Note that the only constraints involving said variables are ( 38), ( 41) and ( 42).

Proposition 3. Consider the following two sets: 41), ( 42)

A = P roj c (x, c) ∈ R |I| × R |J| : (38), (
B =    c ∈ R |J| : j∈J c j ≤ m, c j ∈ [0, 1] ∀j ∈ J    Then, A = B.
Proof. Remark first that using Farkas' Lemma [Farkas, 1902]:

A =    c ∈ R |J| : j∈J α j c j + α |J|+1 ≥ 0 ∀α ∈ R |J|+1 : j∈J:j∈i α j + α |J|+1 ≥ 0 ∀i ∈ I : |i| ≤ m and α |J|+1 ≥ 0    ,
We use this representation of A to show that A ⊆ B. Indeed, the following 2|J| + 1 vectors in R |J|+1 : ∀j ∈ J, e j ∈ R |J|+1 : e j j = 1, e j k = 0 ∀k ∈ J : k = j and e j |J|+1 = 0,

∀j ∈ J, f j ∈ R |J|+1 : f j j = -1, f j k = 0 ∀k ∈ J : k = j and f j |J|+1 = 1 and g ∈ R |J|+1 : g j = -1 ∀j ∈ J and g |J|+1 = m,
α j + α |J|+1 ≥ 0 ∀i ∈ I : |i| ≤ m and α |J|+1 ≥ 0, ( 46
)
is dominated by some nonnegative linear combination of the constraints defining B.

First, note that we can restrict our attention to constraints such that α j ≤ 0 for all j ∈ J. If there exists ĵ ∈ J such that α ĵ > 0, since α must satisfy ( 46) and |i \ { ĵ}| ≤ |i| ≤ m, it follows that ᾱ with ᾱĵ = 0 and ᾱj = α j for all j ∈ J \ { ĵ} also satisfies ( 46) and since c ≥ 0, we have that

j∈J ᾱj c j + ᾱ|J|+1 ≤ j∈J α j c j + α |J|+1 .
Therefore, the constraint defined by α is dominated by the constraint defined by ᾱ. We thus distinguish two cases of α satisfying (46):

Case 1. |{j : α j < 0}| = k ≤ m, and Case 2. |{j :

α j < 0}| = k > m.
In Case 1, by considering a linear combination of inequalities c j ≤ 1 for 1 ≤ j ≤ k with respective weights -α j ≥ 0, we obtain that:

0 ≤ k j=1 α j c j - k j=1 α j ≤ j∈J α j c j + α |J|+1 ,
since α j = 0 for all j > k and α satisfies ( 46) for i = {1, . . . , k}.

For Case 2, assume w.l.o.g that α 1 ≤ α 2 ≤ . . . ≤ α k < 0 and α j = 0 for all j > k. Then, build a linear combination of inequality j∈J c j ≤ m with weight -α m ≥ 0 and inequalities c j ≤ 1 for 1 ≤ j ≤ m with respective weights α m -α j ≥ 0. The valid inequality thus obtained is:

0 ≤ m j=1 α j c j + j>m α m c j - m j=1 α j ≤ j∈J α j c j - m j=1 α j , since α j ≥ α m for all j > m ≤ j∈J α j c j + α |J|+1 ,
since α satisfies ( 46) for i = {1, . . . , m}.

Proposition 3 leads to the following formulation based on (D2 c,x,q,s,f ):

(ERASER c,q,s,f ) Max k∈K π k f k (47) s.t. j∈J c j ≤ m, 0 ≤ c j ≤ 1 ∀j ∈ J, j∈J q k j = 1 ∀k ∈ K, q k j ∈ {0, 1} ∀j ∈ J, ∀k ∈ K, 0 ≤ s k -A k (j|c)c j -A k (j|u)(1 -c j ) ≤ (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, ( 48
)
f k ≤ D k (j|c)c j + D k (j|u)(1 -c j ) + (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, (49) s, f ∈ R K .
This new formulation involves a polynomial number of variables and constraints and was presented in [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF]. The following result is also an immediate consequence of Proposition 3.

Corollary 2. P roj c,q,s,f P(D2 c,x,q,s,f ) = P(ERASER c,q,s,f ).

We now derive SSG formulations based on (DOBSS q,z,s ) and (MIP-p-G q,z ). We first present extended descriptions of both formulations by considering y k j variables satisfying:

y k j = i∈I: ∈i z k ij ∀j, ∈ J, ∀k ∈ K. ( 50
)
We also use relations ( 35) and ( 36) to adapt the payoffs to the security setting leading to (DOBSS q,z,y,s )

and (MIP-p-G q,z,y ), respectively:

(DOBSS q,z,y,s )

Max

j∈J k∈K {π k (D k (j|c)y k jj + D k (j|u)(q k j -y k jj ))} (51) s.t. j∈J z k ij = j∈J z 1 ij ∀i ∈ I, ∀k ∈ K, ( 52
) i∈I: ∈i z k ij = y k j ∀ , j ∈ J, ∀k ∈ K, ( 53
) i∈I z k ij = q k j ∀j ∈ J, ∀k ∈ K, (54)
z k ij ≥ 0 ∀i ∈ I, ∀j ∈ J, ∀k ∈ K, ( 55
) 0 ≤ s k -A k (j|c) j ∈J y k jj - A k (j|u)(1 - j ∈J y k jj ) ≤ (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, ( 56
) j∈J q k j = 1 ∀k ∈ K, (57)
q k j ∈ {0, 1} ∀j ∈ J, ∀k ∈ K, (58)
s ∈ R |K| . ( 59
) (MIP-p-G q,z,y ) Max j∈J k∈K π k (D k (j|c)y k jj + D k (j|u)(q k j -y k jj ))
s.t. ( 52) -( 55), ( 57) -(58)

A k (j|c)y k jj + A k (j|u)(q k j -y k jj )- A k ( |c)y k j -A k ( |u)(q k j -y k j ) ≥ 0 ∀j, ∈ J, ∀k ∈ K. (60)
Further, consider the following constraint:

j∈J y k j = j∈J y 1 j ∀ ∈ J, ∀k ∈ K, (61)
noindent and let us define the following polyhedra C and D: 59), ( 61) 57), ( 60), ( 61) Lemma 1. C ⊇ P(DOBSS q,z,y,s ) and D ⊇ P(MIP-p-G q,z,y )

C := (q, z, y, s) ∈ [0, 1] |K||J| × [0, 1] |K||I||J| × [0, 1] |K||J| 2 × R |K| : (53) -(57), (
D := (q, z, y) ∈ [0, 1] |K||J| × [0, 1] |K||I||J| × [0, 1] |K||J| 2 : (53) -(55), (
Proof. Consider Constraint (52) and sum over all i ∈ I such that ∈ i:

i∈I: ∈i j∈J z k ij = i∈I: ∈i j∈J z 1 ij ∀ ∈ J, ∀k ∈ K. (62)
Applying ( 53) to ( 62) yields ( 61) and the result follows.

We shall now project the z variables from the larger polyhedra C and D. Said variables only appear in Constraints ( 53)-(55).

Lemma 2. Consider the following two sets;

X = P roj q,y (q, z, y) ∈ R |K||J| 2 +|K||J|+|I||J||K| : (53) -(55) Y = {(q, y) ∈ R |K||J| 2 +|K||J| : ∈J y k j ≤ mq k j ∀j ∈ J, ∀k ∈ K, 0 ≤ y k j ≤ q k j ∀j, ∈ J, ∀k ∈ K} Then, X = Y.
Proof. Note that Constraints ( 53)-( 55) can be treated independently for each k ∈ K and each j ∈ J. First consider the case where q k ĵ = 0 for ĵ ∈ J and k ∈ K. Constraint (54) then implies that for all i ∈ I, z k i ĵ = 0 and Constraint (53) forces y k ĵ = 0 for all ∈ J and the result holds. For all j ∈ J, k ∈ K such that q k j = 0, consider x i = z k ij /q k j and c = y k j /q k j and apply Propostion 3. The result follows.

Consider P roj q,y,s C and P roj q,y D as the feasible regions of the linear relaxations of two MILP formulations-(SDOBSS q,y,s ) and (MIP-p-S q,y )-where we maximize the objective function ( 51) under the additional requirement that the q variables be binary. Hence, we present (SDOBSS q,y,s ), a security formulation based on (DOBSS q,z,y,s ), (SDOBSS q,y,s ) Max

j∈J k∈K π k (D k (j|c)y k jj + D k (j|u)(q k j -y k jj )) s.t. j∈J q k j = 1 ∀k ∈ K (63) q k j ∈ {0, 1} ∀j ∈ J, ∀k ∈ K, (64)
j∈J y k j = j∈J y 1 j ∀ ∈ J, ∀k ∈ K, ( 65
) ∈J y k j ≤ mq k j ∀j ∈ J, ∀k ∈ K, ( 66
) 0 ≤ y k j ≤ q k j ∀j, ∈ J, ∀k ∈ K, ( 67
) 0 ≤ s k -A k (j|c) j ∈J y k jj - A k (j|u)(1 - j ∈J y k jj ) ≤ (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, (68)
s ∈ R |K| .
And we also present (MIP-p-S q,y ), a security formulation based on (MIP-p-G q,z,y ), (MIP-p-S q,y ) Max

j∈J k∈K π k (D k (j|c)y k jj + D k (j|u)(q k j -y k jj )) s.t. (63) -(67) (69) A k (j|c)y k jj + A k (j|u)(q k j -y k jj )- A k ( |c)y k j -A k ( |u)(q k j -y k j ) ≥ 0 ∀j, ∈ J, ∀k ∈ K. (70)
The following corollaries are an immediate consequence of Lemmas 1 and 2.

Corollary 3. P roj q,y,s P(DOBSS q,z,y,s ) ⊆ P(SDOBSS q,y,s ).

Corollary 4. P roj q,y P(MIP-p-G q,z,y ) ⊆ P(MIP-p-S q,y ).

In addition, note that if we restrict (MIP-p-G q,z,y ) to a single type of follower, Constraint (52) disappears and one thus obtains the following corollary.

Corollary 5. P roj q,y P(MIP-1-G q,z,y ) =P(MIP-1-S q,y )

The above corollary immediately leads to the following theorem.

Theorem 2. (MIP-1-S q,y ) is a linear description of the convex hull of feasible solutions for the Stackelberg security game with a single type of attacker.

Proof. The result follows from Corollary 5 and the fact that [START_REF] Conitzer | Commitment to correlated strategies[END_REF] show that (MIP-1-G q,z ) is a linear description for general games.

As in general games, we can use Fourier-Motzkin elimination on Constraints ( 48) and ( 68) to project out the s variables from formulations (ERASER c,q,s,f ) and (SDOBSS q,y,s ) respectively. This leads to the following two families of inequalities:

(A k (j|c) -A k (j|u))c j + (A k ( |u) -A k ( |c))c + A k (j|u) -A k ( |u) ≤ (1 -q k ) • M ∀j, ∈ J, ∀k ∈ K, (71) (A k (j|c) -A k (j|u)) h∈J y k jh + (A k ( |u) -A k ( |c)) h∈J y k h + A k (j|u) -A k ( |u) ≤ (1 -q k ) • M ∀j, ∈ J, ∀k ∈ K, (72)
Replacing Constraint ( 48) by ( 71) in (ERASER c,q,s,f ) and ( 68) by ( 72) in (SDOBSS q,y,s ) leads to (ERASER c,q,f ) and (SDOBSS q,y ).

In the same spirit as Proposition 1, we present the following proposition, establishing the tightest values for the big M constants in the formulations seen so far:

Proposition 4. The tightest values for the positive constants M are:

1. In (49), M = max ∈J {D k ( |c), D k ( |u)} -min{D k (j|c), D k (j|u)}, ∀j ∈ J, k ∈ K.
2. In ( 48), ( 68), M = max ∈J {A k ( |c), A k ( |u)} -min{A k (j|c), A k (j|u)}, ∀j ∈ J, k ∈ K.

3. In ( 71), ( 72), M = max{A k (j|c), A k (j|u)} -min{A k ( |c), A k ( |u)}, ∀j, ∈ J, k ∈ K.

Comparison of the formulations

First, we introduce an additional formulation which we denote by (SDOBSS c,q,y,s,f ). This formulation is equivalent to (SDOBSS q,y,s ), in the sense that the value of their LP relaxations coincide. In this formulation we introduce variables f k for all k ∈ K to rewrite the objective function so that it matches (47). We also add variables c for all ∈ J and rewrite Constraint (65) as j∈J y k j = c for all ∈ J and all k ∈ K. Using this last condition we can simplify (68) to (48). The formulation (SDOBSS c,q,y,s,f ) is as follows.

(SDOBSS c,q,y,s,f ) Max

k∈K π k f k s.t.
(63), ( 64), ( 66) -(68),

f k = j∈J {y k jj (D k (j|c) -D k (j|u))+ q k j D k (j|u)} ∀k ∈ K (73) j∈J y k j = c ∀ ∈ J, ∀k ∈ K, (74)
s ∈ R |K| .

Note that P(ERASER c,q,f ) = P roj c,q,f P(ERASER c,q,s,f ) and P(SDOBSS q,y ) = P roj q,y P(SDOBSS q,y,s ).

Based on Theorem 1 we can present the following theorem comparing the polyhedra P(MIP-p-S q,y ) and P roj q,y P(SDOBSS q,y,s ): Theorem 3. P(MIP-p-S q,y ) ⊆ P(SDOBSS q,y ) = P roj q,y P(SDOBSS q,y,s ).

Proof. The inclusion is a consequence of Theorem 1, the relations between the payoffs described in ( 35) and ( 36) and the relation between the z and y variables described in (50).

To show that the inclusion may be strict, consider the following game. We set m = 2, |J| = 2 and |K| = 1. The reward and penalty payoff matrices for both the defender and the attacker are given by

D(•|c) = [1, 0], D(•|u) = [0, 0], A(•|c) = [0, 0] and A(•|u) = [0, 1].
Additionally, the point with coordinates c t = (1/2, 1/2), q t = (1/2, 1/2) and y k = 1/4 1/4 1/4 1/4 has an objective value of 1/4 and is a valid feasible solution of P(SDOBSS q,y ). However, it is not feasible in P(MIP-p-S q,y ) as it does not verify Constraint (70) for j = 1 and = 2.

Remark that (MIP-p-S q,y ) can be obtained by applying RLT [START_REF] Sherali | A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems[END_REF] to (SDOBSS q,y ). Multiplying both sides of Constraint (71) by variable q k and noticing that q k (1 -q k ) = 0, since q k is binary, one obtains a constraint that once linearized, introducing variables y k j , yields (70). Since (ERASER c,q,s,f ) and (f -SDOBSS c,q,s,f ) and (SDOBSS q,y ) and (MIP-p-S q,y ) have the same objective function, the following corollary holds. Corollary 6. v(MIP-p-S q,y ) ≤ v(SDOBSS q,y ) = v(SDOBSS c,q,s,f ) ≤ v(ERASER c,q,s,f ).

Computational experiments for SSGs

Our security experiments are run on randomly generated instances. For each instance, four payoff matrices have to be generated that satisfy D k (•|c) ≥ D k (•|u) and A k (•|u) ≥ A k (•|c). We consider two ways of generating these matrices. First, we generate matrices where the values for the penalty matrices (D k (•|u) and A k (•|c)) are randomly generated between 0 and 5 and all values for the reward matrices (D k (•|c) and A k (•|u)) are randomly generated between 5 and 10. We shall refer to these as matrices with no variability. Second, we consider an alternative where 90% of the values for the penalty matrices are randomly generated between 0 and 5 (between 5 and 10 for the reward matrices) and 10% of the values for the penalty matrices are randomly generated between 0 and 50 (between 50 and 100 for the reward matrices). We refer to these as matrices with variability. We use a solution limit of 3 hours. A Stackelberg security game instance is defined by |J|, the number of targets, |K| the number of attacker types and m, the number of security resources available to the defender. Recall from the computational experiments for GSGs that using payoff matrices with variability amounts to endowing the game with more structure, thus making it somewhat easier to solve. We have encountered the same phenomenon in SSGs. For games whose payoff matrices have variability, we have considered J = {30, 40, 50, 60, 70}, K = {6, 8, 10, 12} and we have allowed m to be either 25%, 50% or 75% of the number of targets. For games whose payoff matrices don't have variability we have had to be less ambitious in order to solve all instances to optimality within the stipulated time limit and have considered J = {10, 20, 30, 40, 50}, K = {2, 4, 6, 8} while still considering m to be either 25%, 50% or 75% of the number of targets. In either case, for each instance size we generate 5 random instances as described above. In total, we consider 300 randomly generated instances. We study the behavior of (ERASER c,q,s,f ), (SDOBSS q,y,s ) and (MIP-p-S q,y ). For the sake of clarity we no longer consider the Fourier-Motzkin formulations (ERASER c,q,f ) and (SDOBSS q,y ). Performance-wise, (ERASER c,q,s,f ) and (SDOBSS q,y,s ) compare to their Fourier-Motzkin formulations in a similar way to how (D2 x,q,s,f ) and (DOBSS q,z,s ) compared to theirs in Section 4. We plot performance profile graphs in Figures 3 and4.

Remark that for the experiments with variability, (ERASER c,q,s,f ) is the fastest formulation for most of the instances. However, we see that for the more difficult instances, its solution time increases significantly, almost surpassing the solution time of (MIP-p-S q,y ). This indicates that for these instances (ERASER c,q,s,f ) ceases to be competitive and (MIP-p-S q,y ) is the formulation that solves the fastest. As for the instances whose payoff matrices have no variability, and are thus harder to solve, we observe that (ERASER c,q,s,f ) outperforms the running time of the other two formulations for 80% of the instances. However, for the most difficult instances, (MIP-p-S q,y ) is faster than the other two formulations. For the last 5% of the instances, (ERASER c,q,s,f ) is the worst formulation. In terms of size of the formulations, (ERASER c,q,s,f ) is the formulation with the least number of constraints and variables: O(|J||K|). Observe that (MIP-p-S q,y ) and (SDOBSS q,y,s ) have O(|J| 2 |K|) constraints and variables. Thus, these formulations have significantly heavier LP relaxations and thus take longer time to solve than (ERASER c,q,s,f ) does. However, Figures 3 and4 confirm our theoretical findings: (MIP-p-S q,y ) has the tightest LP relaxation and this translates into a clear dominance with respect to node usage in the B&B solving scheme. In the above results we have observed a trend that indicates that for difficult instances, particularly in the case of payoff matrices with no variability, one could expect (ERASER c,q,s,f ) and (SDOBSS q,y,s ) to perform very poorly compared to (MIP-p-S q,y ). To analyze this, we consider instances where the payoff matrices have no variability and where K = {6, 8, 10, 12}, J = {30, 40, 50, 60, 70} and m is 25%, 50% and 75% of the targets. We generate 5 random instances for each size. In addition, for practical reasons, we consider a time limit of 30 minutes. The computational results for these instances are shown in Figure 5. Note that (MIP-p-S q,y ) is able to solve 95% of the 300 instances within the stipulated time limit, outper- forming (SDOBSS q,y,s ) and (ERASER c,q,s,f ) which are only able to solve 56% and 45% of the instances, respectively, within the same time frame. For the 45% of instances which can be solved by the three formulations, we observe that (MIP-p-S q,y ) offers a much tighter gap percentage than the other two formulations. Because of this, the node usage in the branch and bound scheme is significantly smaller in (MIP-p-S q,y ) compared to (ERASER c,q,s,f ) and (SDOBSS q,y,s ). Table 3 records the mean gap percentage across all the instances for the three formulations under study. Observe that (MIP-p-S q,y ) is significantly tighter than the LP relaxations of the other formulations. We may thus conclude that for the payoff matrices without variability, (MIP-p-S q,y ) is the fastest formulation for the most difficult instances. (ERASER c,q,s,f ) is the fastest formulation when we endow the security game with further structure by allowing matrices to experience variability. Even then, (ERASER c,q,s,f ) looses ground to (MIP-p-S q,y ). This is due to the fact that (MIP-p-S q,y ) has the tightest LP relaxation. The quality of the upper bound obtained from (MIP-p-S q,y ) translates into a smaller B&B tree and this translates into reaching optimality of the integer problem faster in many cases.

(ERASER c,q,s,f ) (SDOBSS q,y,s ) (MIP-p-S q,y )

Conclusions and future work

In this paper we consider Stackelberg games in two different settings. We first analyze the general Stackelberg setting, which models a hierarchical and competitive game between different agents, and the specific Stackelberg security setting, where an agent must secure subsets of targets from attackers.

For the general Stackelberg setting, we have proposed a new MILP formulation-(MIP-p-G q,z )-and we have compared its performance with other existing formulations in the literature from both theoretical and computational standpoints.

For the Stackelberg security setting, we have proposed a new MILP formulation-(MIP-p-S q,y )-which is an ideal formulation when restricted to a single type of attacker. The performance of the formulations for security games has been compared both from a theoretical and computational standpoint.

In both cases, (MIP-p-G q,z ) and (MIP-p-S q,y ) are stronger than the other formulations from an LP relaxation point of view and both have been computationally shown to be highly competitive with respect to solution time. Both formulations have brought forth a significant theoretical and practical improvement over previously known formulations.

However, the obvious bottleneck, at this time, is solving the tighter but significantly heavier LP relaxations. The main challenge is to provide an efficient way of solving the two formulations we have proposed. It is our contention that this can be done by exploiting the inherent problem structure in the Stackelberg paradigm to develop either decomposition or cutting plane approaches. Finally, to the best of our knowledge, literature concerning heuristics and meta-heuristics specific to the security domain is rather scarce. We believe that contributing heuristics to this domain could be a fruitful avenue of research to follow.

Figure 1 :

 1 Figure 1: GSGs: |I| ∈ {10, 20, 30}, |J| ∈ {10, 20, 30}, |K| ∈ {2, 4, 6}-without variability.

Figure 2 :

 2 Figure 2: GSGs: |I| ∈ {10, 20, 30}, |J| ∈ {10, 20, 30}, |K| ∈ {2, 4, 6}-with variability.

  satisfy j∈J:j∈i α j + α |J|+1 ≥ 0 and α |J|+1 ≥ 0. Additionally, when we substitute the above vectors into the generic constraint defining A, they yield all the constraints defining B. To show that A = B, it remains to show that any other inequality j∈J α j c j + α |J|+1 ≥ 0 (45) such that α satisfies j∈J:j∈i

Figure 3 :Figure 4 :

 34 Figure 3: SSGs: K = {6, 8, 10, 12}, J = {30, 40, 50, 60, 70}-with variability

Figure 5 :

 5 Figure 5: SSGs: K = {6, 8, 10, 12}, J = {30, 40, 50, 60, 70}-without variability

Table 2 :

 2 Mean gap percentage recorded for GSG formulations.

	Mean gap % (no variability)	117.68	23.01	9.94
	Mean gap % (with variability)	103.44	40.74	5.17
	Total mean gap %	110.56	31.88	7.56

Table 3 :

 3 Mean gap percentage recorded for GSG formulations.

	Mean gap % (no variability)	241.26	38.87	3.09
	Mean gap % (with variability)	168.37	18.66	0.35
	Total mean gap %	204.82	28.76	1.72

Acknowledgements

The first author wishes to acknowledge the FNRS for funding his PhD research through a FRIA grant. This work is also partially supported by the Interuniversity Attraction Poles Programme P7/36 "COMEX" initiated by the Belgian Science Policy Office.

Proposition 5. P roj c,q,s,f P(SDOBSS c,q,y,s,f ) ⊆ P(ERASER c,q,s,f ). Further, there exist instances for which the inclusion is strict.

Proof. The projection of P(SDOBSS c,q,y,s,f ) onto the (c, q, s, f )-space is obtained by applying Farkas' Lemma. Constraints (66)-( 67) and ( 73)-( 74) are the only ones involving variables y k j and are separable by k ∈ K. For a fixed k ∈ K, the projection is given by:

Consider, for each k ∈ K, the following set B k :

First note that if we set α = 0, the following definitions of the parameters β, γ and δ comply with the conditions in (75):

Substituting these valid parameters in the generic constraint in A k , produces all of the constraints in B k except (79). Further, for a fixed j ∈ J, consider α = -1, β = 0 and γ = 1 m (D k ( |c) -D k ( |u)) for all ∈ J such that = j, β j = D k (j|c) -D k (j|u) and γ j = 0. Finally, set δ j = 0 for all , j ∈ J. This definition of parameters is valid as it satisfies the conditions in (75). Substituting in the generic constraint in A k yields (79). It remains to show that for all k ∈ K, Constraint (79) implies (49) for the tight value of M shown in Proposition 4. The implication holds because

Hence, P roj c,q,s,f P(SDOBSS c,q,y,s,f ) ⊆ P(ERASER c,q,s,f ). To show that the inclusion may be strict, consider the following example where m = 1, |J| = 3 and |K| = 1. Let the reward and penalty matrices for the defender and attacker be D(

. Consider the point defined by q = ( 1 3 , 1 3 , 1 3 ) t , c = (1, 0, 0) t , s = 10 and f = 2/3. Such a point is feasible for (ERASER c,q,s,f ) but violates Constraint (79) for j = 2 and is therefore infeasible for P roj c,q,f,s P(SDOBSS c,q,y,s,f ).