The Price of Usability: Designing Operationalizable Strategies for Security Games

1 Introduction

The problem of protecting vulnerable targets from attackers using limited security resources manifests in many real world applications. A notable example, which serves as a key thrust in this paper, is the problem of screening for threats at (airport or border) checkpoints [AAA, 2014]. Deterministic solutions to these problems, which maintain the allocation of security resources constant, are highly predictable and thus severely suboptimal. The game-theoretic security game model was proposed as a means to mitigate this predictability against strategic adversaries [Tambe, 2011; Korzhyk et al., 2010; Yin et al., 2015; Balcan et al., 2015; Basilico et al., 2009]. Recently and in collaboration with the US Transportation Security Administration (TSA), this work was extended in the form of the threat screening game (TSG) model to tackle the problem of screening for threats at checkpoints. As this area of research continues to grow, security agencies have begun adopting these more sophisticated game-theoretic strategies making ease of practical use and implementation a key concern. Motivated by our discussions with the TSA, we focus our discussions in this paper on the problem of screening for threats.

There are two major issues that come in the way of practical operationalization of these game theoretic solutions to the problem of screening for threats at checkpoints.The first challenge relates to the practical difficulty of integrating decisions made by different levels of authority: a) higher level strategic decisions related to the design of teams of security resources and the assignment of personnel to shifts and teams; and b) lower level tactical decisions related to the online allocation of screenees to preformed teams of resources. Although these problems are intimately related, to date, no attempt has been made to address them in tandem making their solutions difficult to integrate and apply.

The second challenge relates to the fact that optimal solutions to TSGs typically involve randomizing over large numbers of pure strategies, each corresponding to a different security protocol. Thus, while they are by far preferable to deterministic strategies from an efficiency perspective, they are difficult to operationalize, requiring the security personnel to be familiar with numerous protocols in order to execute them.

Contributions We address these two shortcomings related to usability of TSG. First, we build upon the work on Simultaneous Optimization of Resource Teams and Tactics

(SORT) [Mc Carthy et al., 2016] to propose SORT-TSG, a model for TSG that yields solutions that can be directly applied in their entirety in practice and where security personnel schedules are integrated with screening needs. Second, we propose an easy to use mixed-integer optimization model for computing strategies that are easy to operationalize and that bridge the gap between the suboptimal deterministic solution and the optimal yet impracticable mixed strategy. These strategies only randomize over an optimally chosen subset of pure strategies whose cardinality is selected by the defender, enabling them to conveniently tune the trade-off between ease of operationalization and efficiency using a single design parameter. The optimization formulation does not scale to realistic size instances and we propose a novel solution approach for computing ϵ-optimal equilibria as well as a heuristic for computing operationalizable strategies to SORTTSG. We perform extensive numerical evaluation that showcases the solution quality and scalability of our approach and illustrate that the Price of Usability is typically not high.

2 Usability in Security Games

Security games deal with the challenge of allocating scarce security resources among heterogeneous targets to avert a possible attack. These problems can be formulated as Stackelberg games between the defender (leader) and the attacker (follower) and admit an optimal (albeit challenging to compute) mixed strategy solution.

Definition 1 (Mixed Strategy in a Security Game). The defender pure strategies are given by a finite set of integral points Q ⊂ Nn where n denotes the number of targets and S := |Q| is the number of pure strategies. Intuitively, each q ∈ Q corresponds to a (static) allocation of security resources. To maximize the chances of thwarting an attacker, the defender randomizes over pure strategies to build a mixed strategy, defined as a distribution over pure strategies:

The objective of the defender is to select the mixed strategy that maximizes her expected utility assuming best response from the adversary. For our focus domain of threat screening at airports [Brown et al., 2016; Schlenker et al., 2016; McCarthy et al., 2017], the corresponding TSG model often has an extremely large pure strategy space. Further, the number of pure strategies in the support of a mixed strategy is also large as we show in our experiments.

In practice, each pure strategy can be viewed as a separate security protocol. In the context of TSG, these are different configurations and number of screening equipment. Thus, mixed strategies with large support sets can be problematic to operationalize as they require security agents to be familiar with a large variety of protocols to execute them all properly. These types of complex tasks increase the cognitive load in individuals [Hogg, 2007] increasing the likelihood that mistakes are made [Paas, 1992; Cooper and Sweller, 1987] and making the system vulnerable to exploitation. While such usability concerns have always been present in deployed security games, these have often been addressed in an ad-hoc fashion, and not explicitly discussed in the literature. For example, the US Coast Guard limited the number of pure strategies used in the Staten Island Ferry security game to avoid cognitive overload for boat operators [Fang et al., 2013][Fang private communication 2018]. To the best of our knowledge, [Paruchuri et al., 2007] is the only paper that explicitly discussed limiting the number of pure strategies in security games; although they only handled small games (100s pure strategies), and they did not consider the impact of such restriction on solution quality. In this paper, we explicitly formulate usability in security games and motivate our definition to limit the cognitive load placed on security personel, and refer to such strategies as being operationalizable.

Operationalizable Security Games Motivated by our discussions with practitioners in the security domain, we propose a model for usability in security games which we refer to as Operationalizable Security Games that admits solutions whose mixed strategy support cardinality is a design parameter selected by the defender; the choice of cardinality enables explicit trade-off between ease of implementation and efficiency. Rather than pre-committing to a fixed subset of pure strategies to be used in the randomization, our model decides on the best subset of policies to employ. Our hope (which we confirmwith extensive experiments, see Section 5) is that the price of usability, i.e., the loss in efficiency due the restriction of the space of feasible mixed strategies, will not be high even if only a moderate number of strategies is employed.

Definition 2 (k-Operationalizable Mixed Strategy). A mixed strategy p is k-operationalizable if the cardinality of the support of p is limited to k, i.e. |{i ∈ {1, . . . , S} : pi > 0}| ≤ k.

For usability's sake, we propose to restrict solutions of security games to be k-operationalizable. A large k produces solutions that randomizes over a large number of pure strategies (maximizes optimal utility but not easy to operationalize) and low k produces more deterministic strategies (easy to operationalize, but exploitable by an intelligent adversary). We can balance between usability and efficiency using the single parameter k. The following theorem postulates that unfortunately usability comes at a computational price.

Theorem 1. Let G be a zero sum game with pure strategy space Q. The problem of finding optimal solutions that are koperationalizable is NP-Hard to solve even if G can be solved in polynomial time. 1

For a player in such a game G, an optimal mixed strategy which is k-operationalizable is one which minimizes that player's Price of Usability.

Definition 3 (Price of Usability). Let G be a game with optimal mixed strategy solution p and utility U(p). Let pk be an optimal k-operationalizable mixed strategy solution to G. We define the price of usability (PoU) as the ratio between the utilities of p and pk so that PoU := U(p)/U(pk ).

3 SORT for Threat Screening Games

Addressing the two usability limitations of TSG [Brown et al., 2016; Schlenker et al., ] discussed earlier, in this section we first present (1) the model of Simultaneous Optimization (SORT) for TSGs and second (2) the problem of computing operationalizable strategies for TSGs. We assume a zero-sum game. Throughout this section we use the example of passenger screening at airports, but emphasize that the TSG applies to generalized screening problems.

1 All proofs can be found in the appendix at: http://teamcore.usc.edu/papers/2018/POU appendix.pdf

3.1 ProblemDescription

A TSG is a game between the screener (defender) and adversary over a finite planning horizon W consisting of W time windows. The defender is operating a checkpoint through which screenees (passengers) arrive at during each time window. Each screenee belongs to a category c ∈ C where a category c := (ρ, f) consists of components which are controllable and uncontrollable. In the airport security domain, the controllable component f corresponds to a flight type, dictated by the adversary's choice of flight to attack, while the uncontrollable element ρ describes the risk level assigned to each passenger (i.e. if they are TSA pre-check). It is assumed that the number of passengers of category c arriving during each time window, N w c , is known.

The adversary attempts to pass through screening by disguising themselves as one of the screenees. He has a choice of flight to attack, and thus can choose his flight type category, a time window w to arrive in and an attack method m ∈ M. The adversary cannot control his risk level ρ and we assume a prior distribution Pρ over the risk level of the adversaries.

At the checkpoint, the defender has a set of r ∈ R resources which are combined into teams indexed in the set T to which incoming passengers are assigned. If a passenger is assigned to be screened by a team t ∈ T , they must be screened by all resources R(t) ⊂ R in that team. The efficiency of a team, Et,m, denotes the probability that an attacker carrying out an attack of type m be detected when screened by team t. This efficiency depends on the resources in that team: Et,m = 1- ∏r∈R(1-er,m), where er,m is the efficiency of resource r against attack method m.

Each resource r ∈ R has a fixed capacity Cr for the number of passenger which it can process in any time window. In the case that it is not possible to screen all passengers in a single time window, we allow these passengers to be screened in the next time window by their assigned resources, at a cost φr per passenger overflowing to the next window. Each resource r maintains an overflow queue owr corresponding to the number of passengers waiting to be processed by that resource in the beginning of time window w.

To speed up processing, the defender can increase the number of resources of each type that are available in a particular window (by e.g., opening up more lanes). However, the number of resources of each type r that can be operated at any given time is limited by the number of resources of that type that are available in the arsenal of the defender, denoted by Mr ∈ R, and by the number of operators that are working in that window. Specifically, to operate each resource of type r, Ar workers are needed. The workforce of the defender consists of S workers and the defender can decide on the number of workers available in any window. However, the workers must follow shifts: they can start in arbitrary time windows but must work for δ consecutive time windows.

3.2 SORT-TSG ProblemFormulation

We now formulate the SORT problem for TSG as a mixedinteger linear optimization problem. For convenience, we first introduce the pure strategy spaces related to the strategic and tactical decisions of the defender, respectively, and then go on to formulate the optimization problem which randomizes over these strategies.

The core strategic decisions of the SORT-TSG problem correspond to the number of resources of each type r ∈ R to operate in each window, which we denote by yw r ∈ N+. They also include the number of workers bw ∈ N+ to start their shift in window w and the number of workers sw available in window w. The space of pure strategic strategies can then be expressed as:

The first constraint above counts the total number of workers with shifts currently in progress at time window w. The second constraint stipulates that the total number of workers assigned to each shift cannot exceed the size of the workforce. The third and fourth constraints enforces that in each time window there must be enough workers to operate each resource, and that the number of operating resources cannot exceed the maximum number available for each type.

The core tactical decision variables of the SORT-TSG problem correspond to the number of passengers of each type c to screen with team t in window w, denoted by nwt,c . For any choice y of strategic decisions, the space of pure tactical strategies is expressible as:

where the two constraints above stipulate that all arriving passengers must be assigned to be screened by a team and enforce the capacity constraints on each of the resource types. Note that the capacity is determined by the number of operating resources of each type. The full defender pure strategy space can be expressed compactly as:

Next, given the probability distribution as the defender's mixed strategy, we denote by Ep[ ] the expectation operator with respect to p (the mixed strategy). Thus, the expected number nwt,c of passengers in category c screened by team t in time window w and the expected number owr of passengers waiting to be screened by a resource of type r in time window w are given by:

The utility of the defender is linear in the pure strategies, so the defender's optimization problem can be expressed as:

where zw c,m is the adversary's detection probability for an adversary of type c, using attack m during w and θρ is the expected utility when the passenger's risk level is ρ. We denote this formulation of the SORT-TSG as problemP .

Reduces to [Brown et al., 2016] when there is no overflow and when strategic decisions are fixed.

3.3 Operationalizable Strategies for SORT-TSG

The SORT-TSG problem admits additional usability concerns; not only can the mixed strategy have a very large support, but the number of types of resource configurations (teams) used by any pure strategy may also be very large (as the number of team types grows combinatorially with the number of resources). This can also pose the same operationalization issues, and so we also propose to limit the number of possible resource configurations that may be used in any pure strategy. Formally, we say that a mixed strategy solution to a SORT problem is operationalizable if the following property holds.

Definition 4 ((k, τ)-Operationalizable Mixed Strategy). A mixed strategy p is said to be (k, τ)-operationalizable if the support size of p is less than k, and each pure strategy uses no more than τ unique teams, i.e., if lt is a binary variable indicating the formation of a team of type t then ∑Tt=1 lt ≤ τ . We can compute operationalizable strategies for the TSG problem by constructing a new set of allowed pure strategies Qτ by adding the following additional constraints to the set Q which enforce that each pure strategy may use no more than than τ resource configurations:

Where the second constraint enforces that lt = 1 if a strategy uses team t at any point, i.e., if ∃ w, c, t : nwc,t > 0 We then enforce that the support of the mixed strategy has maximum cardinality k by replacing equations (1) with:

such that p ∈ Pk = {pi ≥ 0, i = 1, ..., k, ∑ki=1 pi = 1}. Lastly, for the TSG problem it is undesirable to have many different schedules for staff members and have employees work different shifts throughout the week. For this reason we specifically enforce that the scheduling decisions s should be the same across all k pure strategies i.e.

These additions (2,3,4) to P , define the operationalizable SORT-TSG problem, we refer to the problem as Pk .

4 Solving the Operationalizable SORT-TSG

The SORT-TSG problem is expressible as a mixed integer linear program (MILP). However the resulting operationalizable problemPk is non-linear, with bilinear terms introduced in (3). Since the domains of n and o are finite we can express each integer variable n and o as a sum of binary variables, and the bilinear terms can be easily linearized using standard optimization techniques. However, the resulting program has a number of binary variables which grows with the number of passengers, making the full MILP formulation intractable to solve. Other standard approaches for dealing with these types of problems, such as column generation, also do not work well as we show in Section 5. In the following, we provide our new solution approach for efficiently solving Pk .

For convenience we define the following notation. Let P be an optimization problem with integer variables xi ∈ N ∀i. We denote the LP relaxation of P , i.e., the problem obtained by letting xi ∈ R ∀i, as P LP . Additionally let the LP relaxation of a problemP with respect to a single variable xj, i.e., the problem obtained by letting xj ∈ R, be denoted byP LPxj . Let the marginal value of xj (i.e., the expectation Ep[xj]) be denoted ˜xj. Lastly we denote the problem with a fixed variable xj as P |xj .

Our novel solution approach Pk is based on the two following ideas: (1) we allow the k pure strategies to form a multiset (so that a single strategy may appear multiple times) and (2) we restrict the mixed strategy to be a uniform distribution over the multiset of k pure strategies. The intuition behind this approach is that the multiset allows us to approximate any optimal mixed strategy P using multiples of the fractions 1k . If pi ≥ 1k (probability of playing strategy i), then strategy i will appear multiple times in the multiset, and thus will be played with probability a k where a is the number of times it appears. If pi < 1k then as k grows large enough, the loss in utility from not playing strategy i becomes negligible.

This intuition is formalized in Theorem 3 which stipulates that we can compute approximate equilibria (with approximation error ϵ) for any choice of k by fixing a uniform distribution over the multiset of k pure strategies.

Theorem 3. Given a game G with Stackelberg equilibrium x∗ , z∗ and game value (x∗ )⊤Rz∗ there exists a solution x′ , z′ such that x′ is k-operationalizable and is uniformly distributed over its support where for k > 4 log(1+n) ϵ2 (where n is the size of the adversary's action space) we have that x′ , z′ is an ϵ-Stackelberg equilibrium with game value (x∗ )⊤Rz∗ - (x′ )⊤Rz′ ≤ ϵ.

We derive these bounds following the proof of [Lipton et al., 2003], which for our problem are a factor 3 tighter. By fixing p = 1k , Pk can be solved directly as an MILP without the creation of extra binary variables. Algorithm 1 outlines this process. To speed up computation we first solve the full relaxation Pk LP to get marginal values ˜ y and ˜n (line 2). We then round these to get integral values yr and nr (line 3) which we then use as a warm start to solve the MILP (line 5).

For any choice of k, we can then compute an ϵ-equilibrium and show that in practice this approach performs well. Additionally, it provides a general framework from which we can

Algorithm 1 k-Uniform Strategies

• 1: procedure k-UNIFORM
• 2: ˜ y, ˜n, ˜ o ← Pk LP 3: yr , nr , or ← Round(˜ y, ˜n, ˜ o) 4: p ← pi = 1k , i = 1, ..., k 5: y, n, o ← WarmStart(Pk |qk, yr , nr , or ) 6: return y, n, o

build more sophisticated and scalable algorithms which we demonstrate in the next section.

4.1 Heuristic Approach

While the approach described in Section 4 provides guarantees for any choice of k, in practice the problem can still be slow to solve, as it requires solving an MILP. Thus we provide a heuristic approach which can be solved more efficiently and still yields high solution quality in practice.

The novelty in our approach comes from exploiting the hierarchical structure of the SORT variables, as well as an optimized rounding procedure to decompose marginal solutions into an operationalizable set of k integral strategies.

The tactical variables (n, o) are dependent on the strategic variables y and so, starting from marginal solution to the LP relaxation, we first impose the operationalizable constraints on the strategic variables, keeping the tactical variables unconstrained. This gives us a set of k strategies with integral y, from which we can compute the corresponding integral tactical variables n for each of the k strategies. Both of these steps use an optimized rounding procedure. Because our objective is a function of the expected value of n and o, it becomes important to optimize over how we do our rounding. Ideally we would like to be able to exactly reconstruct the marginal values obtained from the LP relaxation in order to maximize our objective. Arbitrarily rounding the marginal variables to generate k integral strategies does not take into account the value of the resulting marginal and may result in very suboptimal solutions. Instead we compute an optimal rounding to compute feasible solutions, which take into account the value of the resulting marginal with respect to our objective.

Algorithm 2 outlines the steps of this solution method. We start by solving the full relaxation Pk LP (line 2) to obtain a marginal solution for the strategic variables ˜ y. We then decompose this marginal solution into a set of k integral pure strategies (line 3) using an optimized rounding procedure (which we formalize in the later section) which computes the best k roundings of the marginal ˜ y (keeping a marginal ˜ni for each strategy i, i = 1, ..., k). We then compute the best integral assignment ni and corresponding overflow oi for each resource configuration yi (line 4) using the same optimized rounding procedure on the marginals ˜ni, i = 1, ..., k.

Strategic Variables: Resource Configurations At this stage (line 3) we determine what the k optimal integral variables yi are assuming no integrality constraints on the ni variables, i.e. we solve the problemPk LPn equivalent to letting Ep[nwt,c] = ∑ki=1 pi ˜nw,i t,c and Ep[owr ] = ∑ki=1 pi˜ ow,i r , where ˜nw,i t,c , ˜ ow,i r are in the integer relaxation of Xyi . Unfortunately the following theorem shows that Pk LPn is still intractable to solve.

Algorithm 2 Multiple Hierarchical Relaxations

• 1: procedure MHR 2: ˜ y, ˜n, ˜ o ← Pk LP 3: yi, ˜ni, ˜ oi i = 1, ..., k ←Strategic(Pk LPn |q, ˜ y) 4: yi, ni, oi i = 1, ..., k ←Tactic(Pk |y, ˜n) 5: return y, n, o

Theorem 4. ProblemPk LPn is NP-hard to solve.

To approximate this problem, as in Algorithm 1, we assume a uniform distribution for the mixed strategy. Note that by Theorem 3 for any choice of k that Pk LPn |p is an ϵ approximation to Pk LPn . Given Pk LPn |p, we compute a multiset of k integral solutions yi, i = 1, ..., k, from the marginal ˜ y using the following optimized rounding procedure. We make the change of variables yi = ⌊˜ y⌋+δi such that δi ∈ N+, i = 1, ..., k. Solving Pk LPn |p with this change of variables computes the best k roundings of the marginal ˜ y which we use as our k pure strategies. This subroutine is outlined in Algorithm 3.

Algorithm 3 Determine resource allocations ys

• 1: procedure STRATEGIC(Pk LPn |p, ˜ y)
• 2: p ← pi = 1k , i = 1, ..., k
• 3: y ← yi = ⌊˜ y⌋ + δi, δi ∈ N+, i = 1, ..., k
• 4: return argmax y,˜n,˜ o Pk LPn |p

Tactic Variables: Passenger Allocations (line 4) We now have for each pure strategy i, a marginal ˜ni, i = 1, ..., k. In this step we again apply the same optimized rounding procedure to these variables to obtain integral values ni. Additionally, here we relax the constraint pi = 1k and allow the program to optimize over the distribution over pure strategies.

Reintroducing the mixed strategy p as a variable reintroduces the bilinear terms (3) inPk . However, with our rounding procedure, we can efficiently linearize these terms without creating a very large number of binary variables (as with the full MILP). We let ni = ⌊˜ni⌋ + γi and are left with the bilinear terms pi(γi). To linearize these we make a change of variable zi = pi(γi) and can express constraints (3) as:

This subroutine is outlined in Algorithm 4. First, we make the change of variable for the rounding procedure, and linearize the bilinear terms. We then solve the resulting optimization problem for the fixed y and b solved in the previous stage of the algorithm and finally return n and p which gives us a complete (k, τ)-operationalizable solution.

Algorithm 4 Determing Passenger type allocation ns

• 1: procedure TACTIC(Pk |(y, b), ˜n)
• 4: return argmax n,p

2: n←ni = ⌊˜ni⌋ + δni , δni ∈ N+, i = 1, ...k 3: LinearizeTerms(Pk |(y, b)) Pk |(y, b)

5 Evaluation

We evaluate our algorithms on several different sized instances of SORT-TSG. We use instances of three types: small, moderate and large instance with time windows, passenger types and resources (W=1, C=2, R=2), (W=5, C=10, R=5), (W=10, C=20, R=5) respectively. The large instances correspond to a 10 hour planning window for a single terminal at a large airport. 2 Each experiment is averaged over 50 randomized instances of the remaining parameters.

The Price of Usability In this paper, we proposed to mitigate the price of usability (PoU) by computing (k, τ)- operationalizable strategies. We have defined the price of usability similarly to the price of anarchy, as the ratio between the optimal solution with no usability constraints and the operationalizable equilibrium, (i.e. P /Pk ) so that when the operationalizable game Pk has the same optimal objective as P the PoU = 1. In order to compare the operationalizable utility to that of P , we use column generation to compute the optimal solution to the security game without usability constraints. We do this for moderately sized games, as the column generation method does not scale up to large instances. In Figure 1, we show that the PoU shrinks to almost 1 with increasing number of pure strategies k and team types τ . We note that the bump in runtime with increasing τ is due to a phenomenon in security games known as the deployment to saturation ratio [Jain et al., 2012].

Solution quality We evaluate the solution quality of our algorithms by comparing to (1) two variations of a column generation heuristic, one which cuts off after I iterations and one which selects and re-optimizes over the top k strategies,

2 LAX (Los Angeles airport) has an average of 20 unique flight types per terminal (185 destination locations spread over 9 terminals).

k

Figure 2: a) Comparison of our algorithms with CG which is cut off after I iterations (k = 5, τ = 10). b) Support size of CG solutions for increasing problem size.

and (2) the full MIP which optimally solves operationalizable security game Pk . Figure 2(a) shows the comparison of our methods with the first column generation (CG) baseline. When run to convergence, (CG) optimally solves P , without operationalizable constraints (CG). We approximate Pk by cutting off (CG) after I iterations. We see that for small I, CG achieves very poor utilities compared to our algorithm, and that it takes up to 150 generated strategies (iterations) to match the solution quality of our methods. Additionally we investigate the support size of the mixed strategies computed by (CG) without operationalizable constraints. Figure 2(b) shows that number of strategies used grows as we increase the problem size (here, the number of flight types). We also compared to a second variation of the column generation method where we pick the top k pure strategies, and compute the optimal mixed strategy over these k strategies. This was done cutting column generation off after 10, 20, 50, 100 columns as well as after full convergence. The results are shown in Figure 3. We see on average a 30% loss in PoU when using this baseline compared to our methods, and in the worst case up to 100% loss with PoU ∼ 2 for the baseline when compared to our methods. This demonstrates that we can significantly reduce the support size and still obtain a PoU ∼ 1

In Table 1, we compare utility of our algorithms with the utility obtained from solving the full MILP (which optimally solves Pk ). The full MILP can only be solved for small instances (maximum of k = 3). For these instances, we see that both our methods produce near-optimal solutions and can be executed significantly faster. For moderate and large sized instances, we see the k-uniform algorithm outperform MHR in terms of utility, but that MHR can solve large instances faster.

Scalability To evaluate the scalability of our algorithms, we compare the running time for different time windows W and number of passenger categories C. Figure 4 shows the running time for different values of W and C where the rest of the parameters are fixed. This figure shows that the running time is only slightly increasing in W and that our algorithms can be scaled up to a very large number of passenger types.

6 Conclusion

We introduce the new problem of operationalizable strategies in security games and provide a single framework which reasons about the three levels of planning: strategic, tactical and operational level decision problems. Motivated by the important problem of screening for threat we provide algorithmic solutions to overcome the computational challenges that arise when these planning problems are addressed for TSGs and which mitigate the Price of Usability.