@article {1503017,
	title = {Efficient Solutions for Joint Activity Based Security Games: Fast Algorithms, Results and a Field Experiment on a Transit System },
	journal = {Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS)},
	year = {2014},
	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{\textquoteright}s resources. Second,we present two branch-and-price algorithms, SmartO{\textemdash}an optimal algorithm,
and SmartH{\textemdash} 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.},
	author = {Francesco M. Delle Fave and Shieh, Eric and Jain, Manish and Xin Jiang, Albert and Rosoff, Heather and Tambe, Milind and John P. Sullivan}
}
