caa a22 4500 605514860 CHVBK 20210128100706.0 cr unu---uuuuu 210128e20150901xx s 000 0 eng 10.1007/s10458-014-9270-4 doi (NATIONALLICENCE)springer-10.1007/s10458-014-9270-4 Efficient solutions for joint activity based security games: fast algorithms, results and a field experiment on a transit system [Elektronische Daten] [Francesco Delle Fave, Eric Shieh, Manish Jain, Albert Jiang, Heather Rosoff, Milind Tambe, John Sullivan] 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, $$S\textsc {mart}_{\textsc {O}}\,$$ S M A R T O —an optimal algorithm, and $$S\textsc {mart}_{\textsc {H}}\,$$ S M A R T H —a heuristic approach, to solve Smartinstances. 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 $$S\textsc {mart}_{\textsc {O}}\,$$ S M A R T O and $$S\textsc {mart}_{\textsc {H}}\,$$ S M A R T H . Fourth, we describe a large scale real-world experiment whereby we run the first head-to-head comparison between game-theoretic schedules generated using $$S\textsc {mart}_{\textsc {H}}\,$$ S M A R T H 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. The Author(s), 2014 Game theory nationallicence Security nationallicence Stackelberg games nationallicence Simulations nationallicence Field evaluation nationallicence Delle Fave Francesco University of Southern California, 90089, Los Angeles, CA, USA aut Shieh Eric University of Southern California, 90089, Los Angeles, CA, USA aut Jain Manish University of Southern California, 90089, Los Angeles, CA, USA aut Jiang Albert University of Southern California, 90089, Los Angeles, CA, USA aut Rosoff Heather University of Southern California, 90089, Los Angeles, CA, USA aut Tambe Milind University of Southern California, 90089, Los Angeles, CA, USA aut Sullivan John Los Angeles County Sheriff's Department, Los Angeles, CA, USA aut Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/5(2015-09-01), 787-820 1387-2532 29:5<787 2015 29 10458 https://doi.org/10.1007/s10458-014-9270-4 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10458-014-9270-4 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Delle Fave Francesco University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Shieh Eric University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Jain Manish University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Jiang Albert University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Rosoff Heather University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Tambe Milind University of Southern California, 90089, Los Angeles, CA, USA aut NATIONALLICENCE 700 1- Sullivan John Los Angeles County Sheriff's Department, Los Angeles, CA, USA aut NATIONALLICENCE 773 0- Autonomous Agents and Multi-Agent Systems Springer US; http://www.springer-ny.com 29/5(2015-09-01), 787-820 1387-2532 29:5<787 2015 29 10458