Efficient Solutions for Joint Activity Based Security Games: Fast Algorithms, Results and a Field Experiment on a Transit System

Abstract:

In recent years, several security agencies have been deploying scheduling systems based on algorithmic advances in Stackelberg security games (SSGs). Unfortunately, none of the existing algorithms can scale up to domains where benefits are accrued from multiple defender resources performing jointly coordinated activities. Yet in many domains, including port patrolling where SSGs are in use, enabling multiple defender resources to perform jointly coordinated activities would significantly enhance the effectiveness of the patrols. To address this challenge, this paper presents four contributions. First, we present Smart (Security games with Multiple coordinated Activities and Resources that are Time-dependent), a novel SSG model that explicitly represents jointly coordinated activities between defender’s resources. Second,we present two branch-and-price algorithms, SmartO—an optimal algorithm, and SmartH— a heuristic approach, to solve Smart instances. The two algorithms present three novel features: (i) a novel approach to generate individual defender strategies by ordering the search space during column generation using insights from the Traveling Salesman Problem(TSP); (ii) exploitation of iterative modification of rewards of multiple defender resources to generate coordinated strategies and (iii) generation of tight upper bounds for pruning using the structure of the problem. Third, we present an extensive empirical and theoretical analysis of both SmartO and SmartH. Fourth, we describe a large scale real-world experiment whereby we run the first head-to-head comparison between game-theoretic schedules generated using SmartH against schedules generated by humans on a one-day patrol exercise over one train line of the Los Angeles Metro System. Our results show that game-theoretic schedules were evaluated to be superior to ones generated by humans.