Víctor Bucarey
email: vbucarey@ing.uchile.cl

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

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

Fernando Ordoñez

Oscar Figueroa
email: oscar.figueroa@carabineros.cl

Coordinated defender strategies for border patrols

Keywords: Stackelberg games, Matching polyhedra, Security application 1

An effective patrol of a large area can require the coordinated action of diverse security resources. In this work we formulate a Stackelberg Security game that coordinates such resources in a border patrol problem.

In this security domain, resources from different precincts have to be paired to conduct patrols in the border due to logistic constraints. Given this structure the set of pure defender strategies is of exponential size.

We describe the set of mixed strategies using a polynomial number of variables but exponentially many constraints that come from the matching polytope. We then include this description in a mixed integer formulation to compute the Strong Stackelberg Equilibrium efficiently with a branch and cut scheme. Since the optimal patrol solution is a probability distribution over the set of exponential size, we also introduce an efficient sampling method that can be used to deploy the security resources every shift. Our computational results evaluate the efficiency of the branch and cut scheme developed and the accuracy of the sampling method. We show the applicability of the methodology by solving a real world border patrol problem.

Introduction

Security is a worldwide concern that can require the coordinated use of diverse types of resources.

For instance, a police force can use patrol cars, motorcicles, police on horse, on foot, or by helicopter to patrol a city. These different types of resources have different capabilities (patrolling range, ability to move through different terrain, ability to interact with the population) and a coordinated use of these specialized resources is used in providing an overall security level. Pooling resources from different units also helps provide preventive patrols without burdening any single unit.

Securing national borders to defend from the illegal movement of contraband, drugs and people is a natural concern of nations. The European Union (EU) created the European Border and Coast Guard in October 2016 in response to increases in migrant flows into the EU Council of the EU (2016). In the United States the Department of Homeland Security states as a primary objective that of "protecting [the] borders from the illegal movement of weapons, drugs, contraband, and people, while promoting lawful entry and exit" claiming it is "essential to homeland security, economic prosperity, and national sovereignty" Department of Homeland Security (2017). The European Border and Coast Guard lists as one of its prime objectives "organizing joint operations and rapid border interventions to strengthen the capacity of the member states to control the external borders, and to tackle challenges at the external border resulting from illegal immigration or cross-border crime". Such operations involve different resources possibly from different locations in a joint effort to coordinate a global border plan. It is crucial to balance the effectiveness of a global plan with the cost and difficulty of locally coordinating resources in undermanned areas.

In this paper we consider the operational problem of patrolling the border in the presence of strategic adversaries that seek to trespass it taking into account the defender patrols. We model the situation as a Stackelberg game where the defender acts as the leader executing a preventive border patrol, which is observed prior to the optimal response by the strategic adversary, which acts as the follower. Due to the size of the border, the defender coordinates local resources to achieve a global defender strategy. Motivated by a real border patrol problem, we consider that resources from adjacent precincts are paired together to patrol a location in their area.

Optimization and mathematical models have been used in diverse homeland security applications to efficiently assign limited security resources to defend systems and infrastructure from attack [START_REF] Von Stackelberg | A survey of operations research models and applications in homeland security[END_REF]. Previous work that addresses operational decisions in homeland security applications include [START_REF] Dreiding | An integrated screening model for screening cargo containers for nuclear weapons[END_REF] and [START_REF] Yan | Optimal placement of multiple types of detectors under a small vessel attack threat to port security[END_REF] that consider optimization models for container screening and port security respectively. Passenger screening decisions in airports is addressed in [START_REF] Nie | Passenger grouping with risk levels in an airport security system[END_REF] by an integer optimization model that uses risk level grouping and in [START_REF] Mcclay | Risk-based policies for airport security checkpoint screening[END_REF] where adaptive risk-based screening policies are determined via Dynamic Programming. Models that explicitly take into account the strategic nature of the adversary lead to game theory models, which include network interdiction problems, [START_REF] Dimitrov | Interdiction models and applications[END_REF], and patrolling games over networks, [START_REF] Alpern | Patrolling games[END_REF]. In particular, in [START_REF] Papadaki | Patrolling a border[END_REF], the authors determine the optimal patroling strategy on a border by considering a zero sum simultaneous game over a line network.

Stackelberg Games, introduced by von Stackelberg (2011), are an example of bilevel optimization programs, [START_REF] Bracken | Mathematical programs with optimization problems in the constraints[END_REF], where top level decisions are made by a player -the leader -that takes into account an optimal response -of a follower -to a nested optimization problem. Recent research has used Stackelberg games to model and provide implementable defender strategies in real life security applications. In these applications, a defender aims to defend targets from a strategic adversary by deploying limited resources to protect them. The defender deploys resources to maximize the expected utility, anticipating that the adversary attacks a target that maximizes its own utility. Examples of Stackelberg security games applications include assigning Federal Air Marshals to transatlantic flights, Jain et al. (2010b), determining U.S. Coast Guard patrols of port infrastructure [START_REF] Shieh | Protect: A deployed game theoretic system to protect the ports of the united states[END_REF], police patrols to prevent fare evasion in public transport systems Yin et al. (2012), as well as protecting endangered wildlife [START_REF] Yang | Adaptive resource allocation for wildlife protection against illegal poachers[END_REF].

One of the challenges that has to be addressed in solving these Stackelberg games for real-world security applications is problem size. When the defender action is to allocate limited resources to various targets, the set of possible defender actions can be quite large, i.e the different combinations in which the resources can be assigned to the targets. The size of this set of actions is exponential in the number of resources. In [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF] a relaxation of the Stackelberg security game is formulated which determines the frequency with which each target is protected. This polynomial formulation (in the number of targets and security resources) is shown to be exact when there are no constraints on what constitutes a feasible defender action, but it is only an approximation in the general case. Decomposition approaches have been developed for the general case, when feasible defender actions satisfy additional constraints. For instance a column generation approach is introduced in Jain et al. (2010a) and a cutting plane approach in [START_REF] Yang | Scaling-up security games with boundedly rational adversaries: A cutting-plane approach[END_REF]. A branch and cut approach based on Benders' decomposition is introduced in Yin and Tambe (2012).

A specialized decomposition method that exploits specific problem structure was introduced in [START_REF] Hochbaum | Security routing games with multivehicle chinese postman problem[END_REF].

To represent the coordination in our border patrol problem, we consider a graph composed of nodes for the police precincts and edges that determine if two precincts can be paired. Within each precinct there is a set of locations, or targets, that can be patrolled. In this case the set of pure strategies corresponds to the set of all matchings of size m together with the corresponding possible targets that are protected. This set increases exponentially as the instance grows. We address this computational challenge by introducing compact formulations and using cut a branch and cut approach to to efficiently solve these problems.

The contributions of this work include the introduction of a mixed integer optimization formulation for Stackelberg security games that allow for coordinated defender strategies. To address the exponential problem size we introduce equivalent compact formulations that have a polynomial number of variables but exponentially many matching constraints. Furthermore, to efficently solve these compact formulations, we adapt the [START_REF] Padberg | Odd minimum cut-sets and b-matchings[END_REF] branch and cut scheme.

To execute the optimal defender strategies, it is necessary to sample from the exponential size defender strategy space. We present both an exact, column generation based, approach to sample from the defender strategy space and an approximate method. Our computational results explore the efficiency of solving the Stackelberg game for coordinated defender strategies and the accuracy of the approximate defender strategy sampling method. An early version of this work appeared in the conference [START_REF] Bucarey | Building real stackelberg security games for border patrols[END_REF].

The structure of the paper is as follows: the notation used and problem formulations are presented in the next Section 2. In Section 3 we prove the correctness of the compact formulations showing they are equivalent to Stackelberg security games when the defender strategies require pairing of resources. Here we also outline the branch and cut algorithm used to solve these formulations.

In Section 4 we discuss methods to sample from the exponential size defender strategy space.

We present both an exact method and a computationally efficient approximate sampling method.

Section 5, presents computational experiments to evaluate the difficulty of solving the different problem formulations and of the sampling methods. Furthermore we present in this section results on using this problem formulation on a case study constructed from a realistic border patrol instance. Finally, we present our conclusions and discuss future work in Section 6.

Problem Formulation and Notation

In this section we introduce the notation used and the general framework of Stackelberg security games (SSG). Then, we present an SSG that seeks to select coordinated defender strategies given heterogeneous resources.

Stackelberg Security games

We consider a general Bayesian Stackelberg game, where a leader is facing a set K of followers, as introduced in [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF]. In this setting, the leader commits to a payoff-maximizing strategy, anticipating that every follower knows the leader's choice and responds by selecting their own payoff-maximizing strategy. The solution concept we follow in this game is the strong Stackelberg equilibrium, introduced in [START_REF] Leitman | On generalized stackelberg strategies[END_REF]. In this equilibrium followers select a best response that favors the leader when they are indifferent between several optimal strategies. In this model the leader knows the probability π k of facing follower k ∈ K. We denote by I the finite set of pure strategies for the leader and by J be the finite set of pure strategies for each Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!) of the followers. A mixed strategy for the leader consists in a vector x = (x i ) i∈I , such that x i is the probability that the leader plays pure strategy i. Analogously, a mixed strategy for follower k ∈ K is a vector q k = (q k j ) j∈J such that q k j is the probability that follower k plays pure strategy j. The payoffs are represented by the payoff matrices

(R k , C k ) k∈K , with R k , C k ∈ R |I|×|J| . The R k ij (C k ij )
entry gives the reward for the leader (k-th follower) of taking the leader action i and the k-th follower action j. With these payoff matrices, given a mixed strategy x for the leader and strategy q k for follower k, the expected utility for follower k is given by i∈I j∈J C k ij x i q k j while the expected utility for the leader is given by k∈K π k i∈I j∈J R k ij x i q k j .

The problem of finding the strong Stackelberg equilibrium can be formulated as the following bilevel bilinear problem, see [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF]:

max x,q i∈I j∈J k∈K π k R k ij x i q k j (1) s.t. x 1 = 1, x ≥ 0, (2)
q k ∈ arg max i∈I j∈J C k ij x i r k j : r k 1 = 1, r k ≥ 0 ∀k ∈ K. (3)
The first level problem-or leader's problem-optimizes the leader's expected reward in (1) by selecting the mixed strategy (2) and taking into account the optimal follower response (3). The second level problems-or follower problems-in (3) requires each follower k ∈ K to commit to a mixed strategy q k which is a best response to the leader's strategy, x, in that it maximizes follower k's payoff. Note that, since the problem in (3) is a linear optimization problem on the unit simplex, for any leader strategy x and any k ∈ K, there is a best response to follower k's problem that is a pure strategy, that is a vector q k ∈ {0, 1} |J| such that j∈J q k j = 1.

This observation has been used to propose mixed integer linear programming (MILP) formulations of Stackelberg games. For instance (D2) is formulated in [START_REF] Paruchuri | Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games[END_REF] by linearizing the objective and the optimality constraint with big M constraints:

(D2) max x,q,s,f k∈K

π k f k (4) s.t. x 1 = 1, x ≥ 0, (5)
q k 1 = 1, q k ∈ {0, 1} |J| ∀k ∈ K (6) f k ≤ i∈I R k ij x i + M (1 -q k j ) ∀j ∈ J, ∀k ∈ K, (7) 0 ≤ s k - i∈I C k ij x i ≤ M (1 -q k j ) ∀j ∈ J, ∀k ∈ K. (8)
The (MIP-G) equivalent formulation, introduced in [START_REF] Casorrán | A study of general and security stackelberg game formulations[END_REF], is constructed by using the linearizing variable h k ij = x i q k j and projecting constraints ( 7) and ( 8):

(MIP-G) max h,q i∈I j∈J k∈K

π k R k ij h k ij (9) s.t. j∈J h k ij = j∈J h 1 ij ∀i ∈ I, ∀k ∈ K (10) i∈I h k ij = q k j , h ≥ 0 ∀j ∈ J, ∀k ∈ K (11) q k 1 = 1, q k ∈ {0, 1} |J| ∀k ∈ K (12) i∈I C k ij -C k il h k ij ≥ 0 ∀j, l ∈ J, ∀k ∈ K, (13)
While (MIP-G) has more variables and constraints, [START_REF] Casorrán | A study of general and security stackelberg game formulations[END_REF] shows that it provides a tighter linear optimization relaxation. We point the reader to that work for a detailed study of the strength and efficiency of these formulations.

In addition, an SSG assumes two things: 1) that the leader (defender) has to protect n targets by deploying resources capable of protecting up to m < n of them. The follower (attacker) selects one target to attack. 2) the rewards depend only on whether the target attacked is protected or not. In this case the set of follower strategies is J = {1, . . . , n} and the strategy set for the defender consists of all feasible deployments that protect up to m targets simultaneously. That is

I ⊂ {K | K ⊂ J, |K| ≤ m}
since there might be logistical constraints that prohibit all combinations of m targets to be protected simultaneously. Let j ∈ i denote the condition that defender strategy i patrols target j. We express the rewards in SSG as follows:

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

R k ij =      D k (j|p) if j ∈ i D k (j|u) if j / ∈ i (14) C k ij =      A k (j|p) if j ∈ i A k (j|u) if j / ∈ i. (15)
Here D k (j|p) (D k (j|u)) denotes the utility of the defender when target j ∈ J is protected (unprotected) and is attacked by attacker k ∈ K. Similarly, the utility of an attacker of type k ∈ K when attacking a protected (an unprotected) target j ∈ J is denoted by

A k (j|p) (A k (j|u)).
This reward matrix structure is exploited in [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF] to build a compact representation of the problem. The approach seeks to avoid using the entire leader strategy space I by introducing for each target j ∈ J a coverage variable c j that represents the frequency of coverage for that target, that is c j = i∈I:j∈i x i the sum of probabilities over strategies that protect j.

Resource Combination in a SSG

We now formulate the SSG problem were the defender first teams up resources from different precincts to form m combined patrols and then decides where to deploy them. Let V be the set of police precincts. We let E ⊂ V × V be the set of edges representing the set of possible precinct pairings, forming an adjacency graph G = (V, E). We denote by δ(v) ⊂ E the set of edges incident to precinct v ∈ V , similarly for any U ⊂ V , δ(U ) ⊂ E denotes the edges between U and V \ U , and E(U ) ⊂ E denotes the edges between precincts in U . We can then represent the possible combinations of m precincts pairs as the set of matchings of size m, which is given by:

M m :=    y ∈ {0, 1} |E| : e∈E y e = m, e∈δ(v) y e ≤ 1 ∀v ∈ V    .
For every precinct v ∈ V , let J v be the set of targets in that precinct. Note that {J v } v∈V is a partition of the set of targets J, i.e., ∪ v∈V J v = J and J u ∩ J v = ∅ for all u = v. A defenders strategy selects m precinct pairings and also the target where each resource team is deployed. The combined patrol from the pairing of precincts u and v can only be deployed to a target in J u ∪ J v . For each edge e = (u, v) ∈ E we define J e = J u ∪ J v . It follows that the set I of defender strategies can be expressed as

I =    (y, w) ∈ {0, 1} |E|+|J| : y ∈ M m , j∈∪ v∈U Jv w j ≤ e∈E(U )∪δ(U ) y e ∀U ⊆ V, j∈J w j = m    . ( 16
)
For (y, w) ∈ I, variable y e indicates whether edge e is selected for a precinct pairing and w j indicates whether target j is patrolled. The first condition enforces that y identifies a matching of size m in V . The second bounds the coverage to a set of targets by the coverage on all incident edges to the precincts containing these targets. The last condition enforces that m targets are protected.

In this SSG, the defender selects (y, w) ∈ I and an attacker of type k ∈ K, appearing with probability π k , responds by selecting the target j ∈ J to attack. This Stackelberg game can be represented by explicitly enumerating all strategies in I and using the MILP (D2) (or (MIP-G))

to obtain the optimal strategies. Unfortunately, this approach is computationally challenging as the resulting optimization problem considers one variable x (y,w) for each (y, w) ∈ I, which is an exponential number of variables in terms of edges. Below we introduce compact MILP formulations with a polynomial number of variables and exponentially many constraints in terms of the number of edges.

The compact formulation is derived similarly to [START_REF] Kiekintveld | Computing optimal randomized resource allocations for massive security games[END_REF] and is based on the observation that if rewards are given by ( 14) and ( 15) then the utility of each player only depends on c j , the coverage at a target j ∈ J. To introduce the compact formulation, given a probability distribution x (y,w) over the defender strategies (y, w) ∈ I, in addition to c j we define z e the coverage probability on edges e ∈ E and g e,j the combined coverage over edge e and target j ∈ J e as follows:

c j = (y,w)∈I : w j =1
x (y,w) j ∈ J (17)

z e =
(y,w)∈I : ye=1

x (y,w) e ∈ E (18)

g e,j =          (y,w)∈I:ye=1,w j =1 x (y,w) if j ∈ J e 0 o/w e ∈ E, j ∈ J . ( 19
)
Given a graph G = (V, E) with V the set of precincts and E the feasible pairings between precincts, [START_REF] Bucarey | Building real stackelberg security games for border patrols[END_REF] introduce the following optimization problem as the compact version of (D2) when the set of defender strategies I is given by ( 16):

(BP)

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!) max c,z,q,s,f,g k∈K

π k f k (20) s.t. q k 1 = 1, q k ∈ {0, 1} |J| ∀k ∈ K, (21) c 1 = m, c ∈ [0, 1] |J| (22) z 1 = m, z ∈ [0, 1] |E| (23) e∈δ(v) z e ≤ 1 ∀v ∈ V, (24) e∈E(U ) z e ≤ |U | -1 2 ∀U ⊆ V, |U | ≥ 3, |U | odd (25) e∈E:j∈Je g e,j = c j ∀j ∈ J (26) j∈Je g e,j = z e ∀e ∈ E (27) f k ≤ D k (j|p)c j + D k (j|u)(1 -c j ) + (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K, (28) 0 ≤ s k -A k (j|p)c j -A k (j|u)(1 -c j ) ≤ (1 -q k j ) • M ∀j ∈ J, ∀k ∈ K (29) s, f ∈ R K , g ∈ [0, 1] |E||J| . (30)
Constraint ( 21) ensures that attacker k ∈ K attacks a single target j ∈ J. Constraints ( 22) and ( 23) indicate that the defender uses all resources and precincts are paired without exceeding the number of resources deployed. Constraint (24) indicates that a precinct's contribution to a pairing cannot exceed 1. Constraints (25) correspond to the blossom or odd set inequalities, introduced in [START_REF] Edmonds | Maximum matching and a polyhedron with 0, l-vertices[END_REF], and together with ( 23) and ( 24) enforce that the coverage probabilities on the edges belong to the convex hull of the polytope of matchings of size m. Constraints ( 26) and ( 27)

enforce the conservation between marginal coverages in nodes and edges. Finally, Constraints ( 28) and ( 29) ensure that c and q are mutual best responses. The objective function in our formulation, maximizes the defender's expected utility.

Here we present an alternative compact formulation (COMB) obtained from (MIP-G) when the set I is given by ( 16) by applying the coverage probabilities ( 17)-( 19). In this formulation we use the transformation t k jl = c j q k l and that this implies l∈J t 1 jl = c j for any vector q feasible.

(COMB) max t,z,q,g k∈K

π k D k (j|p)t k jj + D k (j|u)(q k j -t k jj ) (31)
s.t. ( 21), ( 23), ( 24), ( 25), ( 27)

l∈J t k lj = mq k j ∀j ∈ J, ∀k ∈ K (32) 0 ≤ t k lj ≤ q k j ∀l, j ∈ J, ∀k ∈ K (33) j∈J t k lj = j∈J t 1 lj ∀l ∈ J, ∀k ∈ K (34) e∈E:j∈Je g e,j = l∈J t 1 jl ∀j ∈ J (35) A k (j|p)t k jj + A k (j|u)(q k j -t k jj ) -A(l|p)t k lj -A k (l|u)(q k j -t k lj ) ≥ 0 ∀l, j ∈ J, ∀k ∈ K (36) t ∈ [0, 1] |J| 2 ×|K| , z ∈ [0, 1] |E| , g ∈ [0, 1] |E||J| , (37)

Correctness of formulations

In this section we show the correctness of formulations (BP) and (COMB) by proving they are respectively equivalent to (D2) and (MIP-G) when the set I is given by ( 16). We finish the section describing a branch and cut strategy to efficiently address the exponentially many odd set constraints in formulations (BP) and (COMB).

Equivalence of compact SSG formulations

To set the notation, we consider a combined resources SSG problem with defender action set given by ( 16) and defender and attacker utilities given by ( 14) and (15), respectively. We show that (BP) is equivalent to (D2) for a SSG with resource combination by showing that a feasible solution from one leads to a feasible solution in the other with same objective value and viceversa. We first state the following property, proved in the appendix.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Property 1 Given (y, w) ∈ I then the following holds 38)

w j = 1 ⇒ e∈E:j∈Je y e = 1 (
y e = 1 ⇒ j∈Je w j = 1. ( 39
)
Theorem 1. Let the set I be given by ( 16) and the reward matrices by ( 14) and ( 15). Then Problem (BP) given by ( 20)-( 30) is equivalent to (D2) given by ( 4)-( 8).

Proof of Theorem 1. We begin with a solution (x, q, s, f ) feasible for (D2). Given this x we 17), ( 18), and ( 19), respectively. We now show that this (c, z, q, s, f, g) is feasible for (BP) and has the same objective value. Indeed, the objective function (20) and constraints ( 21) in (BP) are the same as ( 4) and ( 6) in (D2). In addition constraints (30) are satisfied from the definition of c, z and g and the fact that x is a probability distribution.

define c ∈ [0, 1] |J| , z ∈ [0, 1] |E| and g ∈ [0, 1] |E||J| as in (
Since the utilities are given by ( 14) and ( 15), we have that x (y,w)

+ D k (j|u)   1 - (y,w)∈I:w j =1
x (y,w)

  = D k (j|p)c j + D k (j|u) (1 -c j ) .
This equality is used to conclude that ( 7) implies (28). Analogously for the attackers utility we have that ( 8) implies ( 29).

From the definition of g e,j we can write Where the next to last equality follows from (39). This shows that ( 27) is satisfied. Similarly expanding e∈E:j∈Je g e,j and now using (38) gives that ( 26 This proves that ( 23) is satisfied. Finally we observe above that the vector z ∈ [0, 1] |E| satisfies z = (y,w)∈I x (y,w) y where x is a probability distribution over I and the vectors y correspond to mmatchings in the set V . Therefore z ∈ convex hull(M m ), which implies that z satisfies constraints ( 24) and ( 25) that characterize the m-matching polytope, completing the first part of the proof.

Algorithm 1 Procedure to identify mixed strategy x given feasible vectors z, c, g

Step 1. For every edge e ∈ E consider a column of height 1. Divide this 1 × |E| rectangle in horizontal segments, one for each integer matching y ∈ M z , with each segment of width λ y . For each segment, corresponding to matching y, block out the areas corresponding to the edges that are not used in y (i.e.'NO' in Figure 1).

Step 2. For every edge e ∈ E, further subdivide the total area in its column that is not blocked out into smaller rectangles using the values of g ej for all j ∈ J e . Since j∈Je g ej = z e = y∈Mz λ y y e , from ( 27) and the decomposition of z, this partition uses all the area in the column of e that was not blocked out.

Step 3. Define x by extending each rectangle line into a horizontal line crossing all columns.

The area between two horizontal lines represents a defender strategy. This area is contained in a matching y, that identifies the paired precincts, and for each edge e in the matching (y e = 1), the area includes part of some g eje , identifying the protected target j e . Let the width of this horizontal line be x (y,w) , where w ∈ {0, 1} |J| is the indicator vector of the protected targets {j e } {e:ye=1} .

We now consider a solution (c, z, q, s, f, g) feasible for (BP) and construct a solution (x, q, s, f ) that is feasible for (D2) with the same objective function. Variables q, s and f are the same, this shows that the objective (4) and constraint ( 6) in (D2) are satisfied as they correspond to

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

(20) and ( 21) respectively. To build x we first recognize that by constraints ( 24) and ( 25), the vector z ∈ convex hull(M m ). Therefore, there is a finite set of integer m-matchings M z ⊆ M m such that we can express z = y∈Mz λ y y, where λ y ≥ 0 for all y ∈ M z and y∈Mz λ y = 1. Given this decomposition of z, we apply Algorithm 1, illustrated in Figure 1, to obtain our variable x. Construction to identify mixed strategy x given feasible vectors z, c, g. Here matching y 2 includes edges e1, e3, . . . , e |E| . A constant width horizontal line (shaded) can be identified using portions of g14, g38, . . . , g |E|11 . This shaded horizontal line corresponds to using precinct parings according to matching y 2 and protecting targets w = {4, 8 . . . , 11}, whose width we label as x (y 2 ,w)

We now show that all the (y, w) identified in Step 3 satisfy (y, w) ∈ I. First we have by construction that y ∈ M m . In addition for each edge e = {u e , v e } used in y we identify a single target j ∈ J e = J ue ∪ J ve so that w j = 1. Therefore the vector w determines exactly m different targets.

For any U ⊆ V , we have This proves that (y, w) ∈ I. Also, by construction, the horizontal lines corresponding to defender strategies cover the box completely, since the entire area of the 1 × |E| that is not blocked out is covered by some g ej > 0. Therefore Step 3 can be performed at any height of the box corresponding to a rectangle limit line. This implies that the values x (y,w) constructed in Step 3 are non-negative and sum to one, therefore they form a probability distribution over (y, w) ∈ I, i.e. the vector x constructed satisfies (5). To show that constraints ( 7) and ( 8) are satisfied we only need to show that the x constructed satisfies c j = (y,w)∈I : w j =1 x (y,w) .

Consider a target j ∈ J and e such that j ∈ J e with g ej > 0. We have from Step 2 in Algorithm 1 that the full amount of g ej is assigned to some area in the column e intersected by matchings that use that column. That area can be partitioned into many strategies (y, w) but each of them has y e = 1 and w j = 1. Therefore we have that g ej = (y,w)∈I x (y,w) w j y e . We have then x (y,w) w j .

Where the last equality comes from (38). Q.E.D.

Analogously we can establish the equivalence between (MIP-G) and (COMB). The proof is almost identical and is given in the appendix.

Theorem 2. Let the set I be given by ( 16) and the reward matrices by ( 14) and ( 15). Then Problem (COMB) given by ( 31)-( 37) is equivalent to (MIP-G) given by ( 9)-( 13).

A branch and cut solution method

Finding a solution for the compact formulations (BP) and (COMB) remains difficult since the blossom inequalities, present in both formulations in (25) are exponentially many. To face this large number of constraints we implement a branch and cut scheme where blossom inequalities are generated on the fly in a cut generation algorithm. The branch and cut scheme follows the approach introduced in Padberg and Rao (1982) and was implemented using the Lazy Constraint Callback in CPLEX 12.7.

We use the procedure introduced in Padberg and Rao (1982) that either detects whether a vector z satisfies the blossom inequality constraints or identifies the most violated one. In this procedure, the problem of detecting if a vector z satisfies all the set of blossom inequalities is reduced to a global min-cut set problem with odd cardinality in a related network. This problem can be solved in polynomial time with the Gomory-Hu algorithm. A simple implementation of the Gomory Hu algorithm, given by [START_REF] Gusfield | Very simple methods for all pairs network flow analysis[END_REF], is used in our implementation.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Recovering an implementable strategy

A strategy that can be implemented by security forces determines which pure strategy is done in each shift. In this section we describe how we use the optimal solutions to (BP) or (COMB), i.e. vectors z * , c * , to sample strategies (y, w) from I.

A first approach is to sample from I according to the optimal strategy x * . This can be achieved by constructing x * from z * , c * , which is described in the second part of Theorem 1 (see Algorithm 1). This procedure requires that a fractional m-matching z * is decomposed as a convex combination of pure matchings of size m. An algorithm to construct this decomposition is presented next. We finish this section with an alternative sampling method that uses solutions (z * , c * ) directly.

4.1. Decomposing z * in pure matchings of size m

Given a vector z * satisfying ( 23)-( 25) we want to build a set M z ⊆ M m of matchings of size m and a set of weights {λ y } y∈Mm such that the vector z * can be written as a convex combination of elements in M z . This can be achieved by using a Dantzig-Wolfe approach, [START_REF] Dantzig | Decomposition principle for linear programs[END_REF]. The master problem can be stated as:

λ y ≥ 0 ∀y ∈ M m (43) Y e , Λ ≥ 0 ∀e ∈ E, ( 44
)
where λ y is the weight of matching y. Variables Y e and Λ represent auxiliary variables to be minimized. θ ye is an indicator parameter taking value 1 when the edge e is included in the matching y. Let π e and σ be the optimal dual variable associated to constraint ( 41) and ( 42) respectively.

Then, the reduced costs of any column/matching is given by:

r θ = 0 - e∈E π e θ e -σ.
The problem of adding a new column to a restricted master problem (i.e. only consider a subset of columns M z ⊂ M m ) can be stated as a maximum weight matching of size m with weights {π e } e∈E .

If a matching θ has a weight greater than -σ it is added to M z and the restricted master is reoptimized. The algorithm stops when no new column is added (and the objective ( 40) is equal to zero), in which case z can be written as a convex combination of matchings in M z .

An approximate sampling method

Finding the convex combination decomposition of z can be computationally expensive. We now propose a computationally efficient, but approximate, two stage sampling method that generates points (y, w) ∈ I directly from z * and c * . In Section 5, we investigate how accurate this approximate sampling method is.

Given z * , we seek to select m edges that form a matching. We do this by iteratively sampling edges without replacement to build the set E and solving the maximum weight m-matching problem

Max e∈E z * e x e s.t. x ∈ M m (E) ,
where M m (E) is the set of m-matchings using only edges in E. To sample edges we consider a fixed index order for the set E. At a given iteration, let m = e∈E\E z * e be the sum of z * over edges not yet sampled and generate a number between 0 and m uniformly. We select the edge in E \ E that causes the partial sum of z * , according to the fixed order, meet or exceed the generated number for the first time. This edge is then added to E.

Solving the maximum weight m-matching problem can have two possible outcomes: the problem is either infeasible and there are no matchings of size m with edges in E or the problem returns an optimal solution. If the problem is infeasible we continue iterating and sampling more edges for the set E. If the problem returns an optimal matching we keep this as the sampled matching y.

Note that this algorithm will produce a matching in at most |E| iterations.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

We generate the targets protected by sampling according to the normalized target coverage probability, defined below, for the precincts covered by the matching y found in the previous step.

That is, we use the discrete probability

c * j = c * j k∈Je c * k ∀j ∈ J e s.t. y e = 1
to sample a single target for every e ∈ E such that y e = 1. This generates the protected targets that agree with the selected matching, giving the point (y, w) ∈ I. We refer to this method of generating solutions in I as the Approximate Sampling (AS) method.

Computational Results

In this section we evaluate the computational efficiency of the compact formulations (BP) and

(COMB). Furthermore, we study the effectiveness of the alternative sampling procedure presented in Section 4.2. Finally we present a case study based on planning border patrols in the northernmost region of Chile. The experiments were programmed in Python 3.5 using CPLEX 12.7.

Computational Performance

We compare the performance of the general Stackelberg formulations (D2) and (MIP-G) to the Stackelberg security formulations developed specifically for the combined defender patrol problem (COMB) and (BP), and their branch and cut schemes described in 3.2. We refer to the branch and cut versions as (COMB BC) and (BP BC).

We consider randomly generated connected graphs with n nodes, a set of edges with an average node degree of 3 and m security resources. Further, we consider four targets within each node and three types of attackers. The payoff values are randomly generated such that penalties for the defender and each attacker are between -5 and 0 and rewards for the defender and each attacker are between 5 and 10. We scale instances by increasing n and m.

We first focus on instances with two pairings (involving four nodes, m = 2) and n ∈ {5, 6, 7, . . . , 22}. We solve five random instances for each problem size considered and report expected results. In Figure 2, we show, on the left, the expected time (in seconds) it takes to solve the instances against the number of nodes in the graph, and on the right a performance profile, indicating the number of blossom inequalities added by the branch and cut procedure against the total percentage of instances solved. We note that the general Stackelberg formulations (MIP-G) Instances with 2 security resources in graphs of up to 22 nodes and (D2) can only solve small instances, at most with 8 and 11 nodes, respectively. We therefore do not consider formulations (MIP-G) and (D2) in the rest of our analysis. The compact formulations take less than three seconds to solve on average and the number of cuts generated by the branch and cut versions is small (at most two cuts are generated and 90% of instances require no cuts to find the optimal solution).

Our next set of experiments consider larger instances, with n ∈ {25, 30, 35, 40} and m = 4 pairings.

We present performance profile graphs for these instances in Figure 3. We observe that the branch and cut variants take less overall solution time and time to solve the LP relaxation, explore fewer nodes in the branch and bound tree and have a smaller MIP gap than (BP) and (COMB). This can be explained by the observation from Figure 2 that few blossom inequalities are required to solve these problems.

We further scale the instances to compare the efficiency of (BP BC) and (COMB BC). We consider graphs with n ∈ {30, 40, . . . , 80} and m = 10 security resources. In Figure 4, we show, on the left, the average running time of these formulations over the different size instances and, on the right, the number of cuts added by the branch and cut procedure against the percentage of

Figure 4

Instances with 10 security resources in graphs of up to 80 nodes problems solved. In Figure 5 we present the performance profile graphs for these instances. These results show that solution times are comparable for both formulations, with a slight preference for (BP BC) for larger instances. Here we observe the tradeoff between number of iterations and work per iteration. Formulation (COMB BC) has a linear relaxation that takes longer to solve but that is compensated with achieving a smaller MIP gap, thus requiring less nodes in the branch and bound tree, and less blossom inequality cuts being generated.

Performance of sampling methods

Here we evaluate the computational time and accuracy of the Approximate Sampling (AS) method presented in Section 4.2. The sampling method obtains implementable patrolling strategies (solutions (y, w) ∈ I) from the solution (z, c) provided by the compact formulation of the combined defender security problem.

In Table 1 we show the computational times required by this heuristic method and the exact sampling method based on column generation (Section 4.1). The approximate sampling method can determine an implementable strategy in less than a second, independent of problem size. On the other hand, the computational time for the exact method increases dramatically with the size of the problem.

n/m 25/3 50/3 100/3 25/10 50/10 100/10 To evaluate the accuracy of the approximate sampling method we compare the resulting empirical coverage (ẑ, ĉ) obtained by repeatedly applying AS to the coverage solution (z, c) used to execute AS. This means that after conducting N approximate samples we let ĉj = Times target j is selected N for each target j ∈ J. The value ẑe is defined analogously. It is not possible to do this comparison with the corresponding strategies x over the set of combined actions I because there are multiple such strategies for every given coverage solution (z, c). To measure the error between c and our approximate ĉ we use the infinity norm cĉ ∞ = max j∈J |c j -ĉj |.

We consider a sampling size of N = 1000 over instances with n ∈ {25, 50, 100, 250} nodes and m ∈ {3, 10} security resources. For each instance size we generate 30 estimated ĉ and plot the results as box diagrams as shown in Figure 7. First, we notice that for larger instances the distance between c and ĉ decreases and so does the variance of this distance. Second, even for the smallest instance considered the maximum error it is not bigger than 0.06. So we achieve a fast and accurate way to obtain sampled strategies very close to the optimal ones. Analogous results are obtained for the Total Variation distance between z and the approximate ẑ.

Case study for border patrols

We now show the use of this methodology on a realistic border patrol problem proposed by Carabineros de Chile, which is the Chilean national police force. In this problem, Carabineros considers three different types of crime: drug trafficking, contraband of goods or animals and the illegal entry of people. Among other activities, Carabineros conducts patrols along the border with the aim of preventing the occurrence of these border crimes.

Here we describe a problem in planning specific night patrols. Carabineros has identified a set of locations along the border that can serve as vantage points from where to conduct surveillance with technical equipment such as night goggles and heat sensors. A night shift action consists of deploying a detail to these locations. Due to the large distances and harsh landscape, the detail is stationed at these locations overnight, forcing a commitment of these resources for a long period.

The border region is divided into several police precincts. Due to the vast expanses and the lack of manpower, for the purpose of conducting night patrols, the border precincts are paired up, so each precinct that commits resources is not overburdened by this preventive patrolling action. A joint detail, combining personnel from paired precincts, conducts surveillance at one of the vantage points within the paired precincts territory. These border patrols are planned weekly.

We built an instance the border patrol problem for the Arica Parinacota Region of Chile. This region, which is Chile's northernmost region, is depicted in Figure 8. This region has international borders both with Peru and Bolivia. The border begins at the Pacific Ocean and goes to the north-east separating Chile from Peru while climbing to more than 4000 meters above the sea level. It then goes north-south in the Andean Plateau establishing the limit between Chile and Bolivia. The payoffs matrices were built using historic information of crime occurrences detailing location and a description of the crime, the patrol locations, and information on border foot paths and trails provided by police.

We also used open source information on population estimates in Chile and across the border, police precinct boundaries, commercial valuations of goods and punishment for crimes in Chile (CEPAL (2000), Aduanas de Chile ( 2016)). A detailed description of how this instance is constructed appears in [START_REF] Bucarey | Building real stackelberg security games for border patrols[END_REF]. The payoff matrices constructed were vetted by Carabineros to ensure that the game reflected the observed behavior at the border.

In Figure 8 left, we illustrate a realistic instance where possible border precincts are enumerated from 1 to 8. In the right side, we give the graph representation that identifies possible precinct pairings. In this graph the possible outposts in each precinct are denoted by letters [a] to [u].

For this instance, (COMB) with the branch and cut scheme computes the optimal coverage distribution in less than 3 seconds. Optimal coverage distribution with m = 3 and the approximate coverage is showed in Figure 9. Dark bars represent the optimal coverage strategy and yellow bars represent the distribution of the approximate sampling method. Despite the greater deviation in the coverage in the edges, this difference is much smaller in locations coverage. The optimal solution, shown in Table 2 in the appendix, only uses 16 pure strategies (y, w) ∈ I.

Figure 9

Coverage comparison in edges and targets in the realistic instance.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Conclusions and future work

In this article, we studied a special type of SSG played on a network. In this game, a defender has to combine resources to do patrol labors in a set of targets. We proposed a formulation, (COMB), that represent the set of mixed strategies in a compact form via marginal probabilities in the pairs of resources to team-up and the targets to cover. We proposed a method to retrieve an implementable strategy given the optimal marginals and we prove the validity of our formulation. To scale-up the instances that solvers are able to optimize, we used a cut generation algorithm.

We have further provided an alternative sampling method to recover an implementable defender strategy given the optimal coverage distributions. Computational tests have shown that the twostage sampling method we describe, provides implementable strategies that do not deviate much from the optimal coverage distributions.

In future work we aim to extend our model and methodology to the case where each resource can be paired up with more than one resource, taking into account different capabilities, time schedules, and other considerations. The first case is easy because the b-matching polytope it also satisfies the Total Dual Integrality property.

Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Proof of Theorem 2 . First we take a solution (h, q) feasible for (MIP-G). Note that from the definition of variables h we have that h k (y,w)l = x (y,w) q k l , then l∈J h k (y,w)l = x (y,w) for each k ∈ K.

We can then write the equivalent conditions to (17), ( 18), ( 19) and define variables (t, z, g) as:

Now we show that the variables (t, z, q, g) are feasible for (COMB) with the same objective function. Since the utilities are given by ( 14) and ( 15). we have that: x (y,w)

= D k (j|p)t k jj + D k (j|u)(q k j -t k jj ).

This expression is used to show that objective function is the same in (MIP-G) and (COMB).

Using the analogous expression for the attacker utility function, we conclude that expression (13) implies (36) with this payoff structure.

Given the variables q are the same in both models, constrain ( 21) is also satisfied in (COMB).

Given that conditions (45), ( 46) and ( 47) are equivalent to conditions (17), ( 18) and ( 19), the proof that z is in the matching polytope of fixed cardinality m is equivalent to the one showed in Theorem 1. In consequence, constrains ( 23), ( 24), (25) are satisfied. Note that c j = l∈J t 1 jl and the same argument in the proof of Theorem 1 lead us to the conclusion ( 27) and ( 35) are also satisfied. Also, constrains (10) directly imply (34). From the definition of t we have This proves (32) is satisfied. Expression ( 33) is satisfied since by definition t k jl ≥ 0 and t k jl = (y,w)∈I:w j =1 h k (y,w),l ≤ (y,w)∈I h k (y,w),l = q k j .

Now we take a solution (t, z, q, g) feasible for (COMB) and we build a feasible solution (h, q)

for (MIP-G). To do so, we compute c from variables t as before. Then, we compute variables x using Algorithm 1. Finally we can compute variables h k jl = x (y,w) q k j which are feasible to (MIP-G) because it is an equivalent formulation to (D2) (for more details, see

  w)j x (y,w) = (y,w)∈I:w j =1 R k (y,w)j x (y,w) + (y,w)∈I:w j =0 R k (y,w)j x (y,w) = D k (j|p) (y,w)∈I:w j =1

  w) ∈ I ye = 1, wj = 1 x (y,w) = j∈Je (y,w)∈I x (y,w) y e w j = (y,w)∈I x (y,w) y e j∈Je w j = (y,w)∈I x (y,w) y e = z e .

  ) is satisfied. In the same logic it follows that e∈E

  Figure 1Construction to identify mixed strategy x given feasible vectors z, c, g. Here matching y 2 includes

(

  Figure 2Instances with 2 security resources in graphs of up to 22 nodes

  Figure 3Performance profile graphs for instances with 4 security resources in graphs of up to 40 nodes

  Figure 5Performance profile graphs for instances with 10 security resources in graphs of up to 80 nodes

Figure 6

 6 Figure 6 Solution times for (BP BC) in instances with n = 100, 150, 200 and m = 5, 15, 25

Figure 7

 7 Figure 7Total variation distance between c and ĉ over instances of different size for m = 3 and m = 10 respectively.

Figure 8

 8 Figure 8Realistic instance in the context of border patrolling and its graph representation.

  w)j h k (y,w)j = (y,w)∈I:w j =1 R k (y,w)j h k (y,w)j + (y,w)∈I:w j =0 R k (y,w)j h k (y,w)j = D k (j|p) (y,w)∈I:w j =1 h k (y,w)j + D k (j|u) (y,w)∈I:w j =0 h k (y,w)j = D k (j|p)t k jj + D k(j|u)q k j (y,w)∈I:w j =0

  (y,w)∈I:w j =1 h k (y,w),l = j∈J (y,w)∈I h k (y,w),l w j = (y,w)∈I h k(y,w),l j∈J w j = q k j m.

  Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Table 1

 1 Computational time (seconds) of Approximate Sampling Method (AS) and Exact Method (EM).

	AS [s] 0.028 0.030 0.026 0.184 0.064	0.045
	EM [s] 2.222 8.345 177.133 6.426 55.008 1176.458

  Article submitted to Operations Research; manuscript no. (Please, provide the manuscript number!)

Table 2

 2 [START_REF] Casorrán | A study of general and security stackelberg game formulations[END_REF]), and they have the same objective function. Q.E.D.A3. Implementable strategies for the case study Implementable strategies in the realistic instance.

	Matching	Locations Probabilty	Matching	Locations Probabilty
	y	w	x (y,w)	y	w	x (y,w)
	{(1, 3), (2, 8), (4, 5)} {a, c, h }	0.079	{(2, 8), (3, 4), (6, 7)} {c, h, q}	0.051
	{(1, 3), (2, 8), (4, 5)} {a, c, k}	0.032	{(2, 8), (3, 4), (6, 7)} {c, i, q}	0.014
	{(1, 3), (2, 8), (4, 5)} {a, d, k}	0.080	{(1, 2), (3, 4), (7, 8)} {b, f, o}	0.111
	{(1, 3), (2, 8), (4, 5)} {a, d, l}	0.031	{(1, 2), (3, 4), (7, 8)} {b,f, p}	0.146
	{(1, 3), (2, 8), (4, 5)} {a, e, l}	0.001	{(1, 2), (3, 4), (7, 8)} {c, f, p}	0.001
	{(1, 3), (2, 8), (4, 5)} {f, e, l}	0.068	{(1, 3), (2, 8), (6, 7)} {a, c, m}	0.132
	{(2, 8), (3, 4), (6, 7)} {c, h, m}	0.112	{(1, 3), (4, 5), (6, 7)} {a, h, m}	0.026
	{(2, 8), (3, 4), (6, 7)} {c, h, n}	0.111	{(1, 3), (4, 5), (7, 8) } {a, h, o}	0.006

Appendix A1. Proof of Property 1

Property 1 Given (y, w) ∈ I then the following holds w j = 1 ⇒ e∈E:j∈Je y e = 1 ( 38)

Proof of Property 1. Since (y, w) ∈ I with w j = 1, if we denote v(j) the precinct that contains target j (i.e. j ∈ J v(j) ), we have

A2. Proof of Theorem 2

Theorem 2 Let the set I be given by ( 16) and the reward matrices by ( 14) and (15). Then Problem (COMB) given by ( 31)-( 37) is equivalent to (MIP-G) given by ( 9)-( 13).