Police departments worldwide are eager to develop better patrolling methods to manage the complex and evolving crime landscape.
Surprisingly, the problem of spatial police patrol allocation to optimize
expected crime response time has not been systematically addressed in
prior research. We develop a bi-level optimization framework to address
this problem. Our framework includes novel linear programming patrol response formulations. Bender’s decomposition is then utilized to solve the
underlying optimization problem. A key challenge we encounter is that
criminals may respond to police patrols, thereby shifting the distribution
of crime in space and time. To address this, we develop a novel iterative Bender’s decomposition approach. Our validation involves a novel
spatio-temporal continuous-time model of crime based on survival analysis, which we learn using real crime and police patrol data for Nashville,
TN. We demonstrate that our model is more accurate, and much faster,
than state-of-the-art alternatives. Using this model in the bi-level optimization framework, we demonstrate that our decision theoretic approach
outperforms alternatives, including actual police patrol policies.
This paper investigates repeated security games with unknown (to
the defender) game payoffs and attacker behaviors. As existing
work assumes prior knowledge about either the game payoffs or the
attacker’s behaviors, they are not suitable for tackling our problem.
Given this, we propose the first efficient defender strategy, based on
an adversarial online learning framework, that can provably achieve
good performance guarantees without any prior knowledge. In particular, we prove that our algorithm can achieve low performance
loss against the best fixed strategy on hindsight (i.e., having full
knowledge of the attacker’s moves). In addition, we prove that our
algorithm can achieve an efficient competitive ratio against the optimal adaptive defender strategy. We also show that for zero-sum
security games, our algorithm achieves efficient results in approximating a number of solution concepts, such as algorithmic equilibria and the minimax value. Finally, our extensive numerical results
demonstrate that, without having any prior information, our algorithm still achieves good performance, compared to state-of-the-art
algorithms from the literature on security games, such as SUQR
, which require significant amount of prior knowledge.
Leather is an integral part of the world economy and a substantial income source for developing countries. Despite government regulations on leather tannery waste emissions, inspection agencies lack adequate enforcement resources, and tanneries’ toxic wastewaters wreak
havoc on surrounding ecosystems and communities. Previous works in
this domain stop short of generating executable solutions for inspection
agencies. We introduce NECTAR - the first security game application
to generate environmental compliance inspection schedules. NECTAR’s
game model addresses many important real-world constraints: a lack of
defender resources is alleviated via a secondary inspection type; imperfect inspections are modeled via a heterogeneous failure rate; and uncertainty, in traveling through a road network and in conducting inspections,
is addressed via a Markov Decision Process. To evaluate our model, we
conduct a series of simulations and analyze their policy implications.
The success of Stackelberg Security Games (SSGs) in counterterrorism domains has inspired researchers’ interest in applying
game-theoretic models to other security domains with frequent interactions between defenders and attackers, e.g., wildlife protection. Previous research optimizes defenders’ strategies by modeling this problem as a repeated Stackelberg game, capturing the
special property in this domain — frequent interactions between
defenders and attackers. However, this research fails to handle
exploration-exploitation tradeoff in this domain caused by the fact
that defenders only have knowledge of attack activities at targets
they protect. This paper addresses this shortcoming and provides
the following contributions: (i) We formulate the problem as a
restless multi-armed bandit (RMAB) model to address this challenge. (ii) To use Whittle index policy to plan for patrol strategies
in the RMAB, we provide two sufficient conditions for indexability
and an algorithm to numerically evaluate indexability. (iii) Given
indexability, we propose a binary search based algorithm to find
Whittle index policy efficiently.
Algorithms for solving Stackelberg games are used in an evergrowing variety of real-world domains. Previous work has extended this framework to allow the leader to commit not only to
a distribution over actions, but also to a scheme for stochastically
signaling information about these actions to the follower. This can
result in higher utility for the leader. In this paper, we extend this
methodology to Bayesian games, in which either the leader or the
follower has payoff-relevant private information or both. This leads
to novel variants of the model, for example by imposing an incentive compatibility constraint for each type to listen to the signal
intended for it. We show that, in contrast to previous hardness
results for the case without signaling [5, 16], we can solve unrestricted games in time polynomial in their natural representation.
For security games, we obtain hardness results as well as efficient
algorithms, depending on the settings. We show the benefits of our
approach in experimental evaluations of our algorithms.
Influence Maximization is an active topic, but it was
always assumed full knowledge of the social network
graph. However, the graph may actually be unknown
beforehand. For example, when selecting a subset of a
homeless population to attend interventions concerning
health, we deal with a network that is not fully known.
Hence, we introduce the novel problem of simultaneously influencing and mapping (i.e., learning) the graph.
We study a class of algorithms, where we show that: (i)
traditional algorithms may have arbitrarily low performance; (ii) we can effectively influence and map when
the independence of objectives hypothesis holds; (iii)
when it does not hold, the upper bound for the influence
loss converges to 0. We run extensive experiments over
four real-life social networks, where we study two alternative models, and obtain significantly better results in
both than traditional approaches.
Several models have been proposed for Stackelberg security
games (SSGs) and protection against perfectly rational and
bounded rational adversaries; however, none of these existing models addressed the destructive cooperation mechanism between adversaries. SPECTRE (Strategic Patrol
planner to Extinguish Collusive ThREats) takes into account the synergistic destructive collusion among two groups
of adversaries in security games. This framework is designed for the purpose of efficient patrol scheduling for security agents in security games in presence of collusion and
is mainly build up on game theoretic approaches, optimization techniques, machine learning methods and theories for
human decision making under risk. The major advantage of
SPECTRE is involving real world data from human subject
experiments with participants on Amazon Mechanical Turk
State-of-the-art applications of Stackelberg security games — including wildlife protection — offer a wealth of data, which can be used to learn
the behavior of the adversary. But existing approaches either make strong assumptions about the
structure of the data, or gather new data through
online algorithms that are likely to play severely
suboptimal strategies. We develop a new approach
to learning the parameters of the behavioral model
of a bounded rational attacker (thereby pinpointing
a near optimal strategy), by observing how the attacker responds to only three defender strategies.
We also validate our approach using experiments
on real and synthetic data.
Thanh H. Nguyen, Debarun Kar, Matthew Brown, Arunesh Sinha, Albert Xin Jiang, and Milind Tambe. 2016. “Towards a Science of Security Games .” In New Frontiers of Multidisciplinary Research in STEAM-H (Book chapter) (edited by B Toni).Abstract
Security is a critical concern around the world. In many domains from counter-terrorism to sustainability, limited security resources prevent complete security coverage at all times. Instead, these limited resources must be scheduled (or allocated or deployed), while simultaneously taking into account the importance of different targets, the responses of the adversaries to the security posture, and the potential uncertainties in adversary payoffs and observations, etc. Computational game theory can help generate such security schedules. Indeed, casting the problem as a Stackelberg game, we have developed new algorithms that are now deployed over multiple years in multiple applications for scheduling of security resources. These applications are leading to real-world use-inspired research in the emerging research area of “security games”. The research challenges posed by these applications include scaling up security games to real-world sized problems, handling multiple types of uncertainty, and dealing with bounded rationality of human adversaries.
Game theory has been successfully used to handle complex resource allocation and patrolling
problems in security and sustainability domains. More specifically, real-world applications have
been deployed for different domains based on the framework of security games, where the defender (e.g., security agency) has a limited number of resources to protect a set of targets from
an adversary (e.g., terrorist). Whereas the first generation of security games research provided
algorithms for optimizing security resources in mostly static settings, my thesis advances the
state-of-the-art to a new generation of security games, handling massive games with complex
spatio-temporal settings and leading to real-world applications that have fundamentally altered
current practices of security resource allocation. Indeed, in many real-world domains, players act
in a geographical space over time, and my thesis is then to expand the frontiers of security games
and to deal with challenges in domains with spatio-temporal dynamics. My thesis provides the
first algorithms and models for advancing key aspects of spatio-temporal challenges in security
games, including (i) continuous time; (ii) continuous space; (iii) frequent and repeated attacks;
(iv) complex spatial constraints.
First, focusing on games where actions are taken over continuous time (for example games
with moving targets such as ferries and refugee supply lines), I propose a new game model that
accurately models the continuous strategy space for the attacker. Based on this model, I provide an efficient algorithm to calculate the defender’s optimal strategy using a compact representation
for both the defender and the attacker’s strategy space. Second, for games where actions are taken
over continuous space (for example games with forest land as a target), I provide an algorithm
computing the optimal distribution of patrol effort. Third, my work addresses challenges with one
key dimension of complexity – frequent and repeated attacks. Motivated by the repeated interaction of players in domains such as preventing poaching and illegal fishing, I introduce a novel
game model that deals with frequent defender-adversary interactions and provide algorithms to
plan effective sequential defender strategies. Furthermore, I handle complex spatial constraints
that arise from the problem of designing optimal patrol strategy given detailed topographical
My thesis work has led to two applications which have been deployed in the real world and
have fundamentally altered previously used tactics, including one used by the US Coast Guard
for protecting the Staten Island Ferry in New York City and another deployed in a protected area
in Southeast Asia to combat poaching.
Wildlife poaching presents a serious extinction threat to many animal species. Agencies (“defenders”) focused on protecting such animals need tools that help analyze, model and predict poacher activities, so they can more effectively combat such poaching; such tools could also assist in planning effective defender patrols, building on the previous security games research. To that end, we have built a new predictive anti-poaching tool, CAPTURE (Comprehensive Anti-Poaching tool with Temporal and observation Uncertainty REasoning). CAPTURE provides four main contributions. First, CAPTURE’s modeling of poachers provides significant advances over previous models from behavioral game theory and conservation biology. This accounts for: (i) the defender’s imperfect detection of poaching signs; (ii) complex temporal dependencies in the poacher’s behaviors; (iii) lack of knowledge of numbers of poachers. Second, we provide two new heuristics: parameter separation and target abstraction to reduce the computational complexity in learning the poacher models. Third, we present a new game-theoretic algorithm for computing the defender’s optimal patrolling given the complex poacher model. Finally, we present detailed models and analysis of realworld poaching data collected over 12 years in Queen Elizabeth National Park in Uganda to evaluate our new model’s prediction accuracy. This paper thus presents the largest dataset of real-world defender-adversary interactions analyzed in the security games literature. CAPTURE will be tested in Uganda in early 2016.
Poaching is a serious threat to the conservation of key species and whole ecosystems. While conducting foot patrols is the most commonly used approach in many countries to prevent poaching, such patrols often do not make the best use of limited patrolling resources. To remedy this situation, prior work introduced a novel emerging application called PAWS (Protection Assistant for Wildlife Security); PAWS was proposed as a game-theoretic (“security games”) decision aid to optimize the use of patrolling resources. This paper reports on PAWS’s significant evolution from a proposed decision aid to a regularly deployed application, reporting on the lessons from the first tests in Africa in Spring 2014, through its continued evolution since then, to current regular use in Southeast Asia and plans for future worldwide deployment. In this process, we have worked closely with two NGOs (Panthera and Rimba) and incorporated extensive feedback from professional patrolling teams. We outline key technical advances that lead to PAWS’s regular deployment: (i) incorporating complex topographic features, e.g., ridgelines, in generating patrol routes; (ii) handling uncertainties in species distribution (game theoretic payoffs); (iii) ensuring scalability for patrolling large-scale conservation areas with fine-grained guidance; and (iv) handling complex patrol scheduling constraints.
Adaptive software agents like HEALER have been proposed in the literature recently to recommend intervention plans to homeless shelter officials. However, generating networks for HEALER’s input is challenging. Moreover, HEALER’s solutions are often counter-intuitive to people. This demo paper makes two contributions. First, we demonstrate HEALER’s Facebook application, which parses the Facebook contact lists in order to construct an approximate social network for HEALER. Second, we present a software interface to run human subject experiments (HSE) to understand human biases in recommendation of intervention plans. We plan to use data collected from these HSEs to build an explanation system for HEALER’s solutions.
This paper looks at challenges faced during the ongoing deployment of HEALER, a POMDP based software agent that recommends sequential intervention plans for use by homeless shelters, who organize these interventions to raise awareness about HIV among homeless youth. HEALER’s sequential plans (built using knowledge of social networks of homeless youth) choose intervention participants strategically to maximize influence spread, while reasoning about uncertainties in the network. In order to compute its plans, HEALER (i) casts this influence maximization problem as a POMDP and solves it using a novel planner which scales up to previously unsolvable real-world sizes; (ii) and constructs social networks of homeless youth at low cost, using a Facebook application. HEALER is currently being deployed in the real world in collaboration with a homeless shelter. Initial feedback from the shelter officials has been positive but they were surprised by the solutions generated by HEALER as these solutions are very counterintuitive. Therefore, there is a need to justify HEALER’s solutions in a way that mirrors the officials’ intuition. In this paper, we report on progress made towards HEALER’s deployment and detail first steps taken to tackle the issue of explaining HEALER’s solutions.
Green security – protection of forests, fish and wildlife – is a critical problem in environmental sustainability. We focus on the problem of optimizing the defense of forests against illegal logging, where often we are faced with the challenge of teaming up many different groups, from national police to forest guards to NGOs, each with differing capabilities and costs. This paper introduces a new, yet fundamental problem: Simultaneous Optimization of Resource Teams and Tactics (SORT). SORT contrasts with most previous game-theoretic research for green security – in particular based on security games – that has solely focused on optimizing patrolling tactics, without consideration of team formation or coordination. We develop new models and scalable algorithms to apply SORT towards illegal logging in large forest areas. We evaluate our methods on a variety of synthetic examples, as well as a real-world case study using data from our on-going collaboration in Madagascar.
Influencing a social network is an important technique, with potential to positively impact society, as we can modify the behavior of a community. For example, we can increase the overall health of a population; Yadav et al. (2015) , for instance, spread information about HIV prevention in homeless populations. However, although influence maximization has been extensively studied [2, 1], their main motivation is viral marketing, and hence they assume that the social network graph is fully known, generally taken from some social media network. However, the graphs recorded in social media do not really represent all the people and all the connections of a population. Most critically, when performing interventions in real life, we deal with large degrees of lack of knowledge. Normally the social agencies have to perform several interviews in order to learn the social network graph . These highly unknown networks, however, are exactly the ones we need to influence in order to have a positive impact in the real world, beyond product advertisement. Additionally, learning a social network graph is very valuable per se. Agencies need data about a population, in order to perform future actions to enhance their well-being, and better actuate in their practices . As mentioned, however, the works in influence maximization are currently ignoring this problem. Each person in a social network actually knows other people, including the ones she cannot directly influence. When we select someone for an intervention (to spread influence), we also have an opportunity to obtain knowledge. Therefore, in this work we present for the first time the problem of simultaneously influencing and mapping a social network. We study the performance of the classical influence maximization algorithm in this context, and show that it can be arbitrarily low. Hence, we study a class of algorithms for this problem, performing an experimentation using four real life networks of homeless populations. We show that our algorithm is competitive with previous approaches in terms of influence, and is significantly better in terms of mapping.
Security agencies including the US Coast Guard, the Federal Air Marshal Service and the Los Angeles Airport police are several major domains that have been deploying Stackelberg security games and related algorithms to protect against a single adversary or multiple, independent adversaries strategically. However, there are a variety of real-world security domains where adversaries may benefit from colluding in their actions against the defender. Given the potential negative effect of these collusive actions, the defender has an incentive to break up collusion by playing off the self-interest of individual adversaries. This paper deals with problem of collusive security games for rational and bounded rational adversaries. The theoretical results verified with human subject experiments showed that behavior model which optimizes against bounded rational adversaries provides demonstrably better performing defender strategies against human subjects.
In this paper, we aim to deter urban crime by recommending optimal police patrol strategies against opportunistic criminals in large scale urban problems. While previous work has tried to learn criminals’ behavior from real world data and generate patrol strategies against opportunistic crimes, it cannot scale up to large-scale urban problems. Our first contribution is a game abstraction framework that can handle opportunistic crimes in large-scale urban areas. In this game abstraction framework, we model the interaction between officers and opportunistic criminals as a game with discrete targets. By merging similar targets, we obtain an abstract game with fewer total targets. We use real world data to learn and plan against opportunistic criminals in this abstract game, and then propagate the results of this abstract game back to the original game. Our second contribution is the layer-generating algorithm used to merge targets as described in the framework above. This algorithm applies a mixed integer linear program (MILP) to merge similar and geographically neighboring targets in the large scale problem. As our third contribution, we propose a planning algorithm that recommends a mixed strategy against opportunistic criminals. Finally, our fourth contribution is a heuristic propagation model to handle the problem of limited data we occasionally encounter in largescale problems. As part of our collaboration with local police departments, we apply our model in two large scale urban problems: a university campus and a city. Our approach provides high prediction accuracy in the real datasets; furthermore, we project significant crime rate reduction using our planning strategy compared to current police strategy.
This paper presents HEALER, a software agent that recommends sequential intervention plans for use by homeless shelters, who organize these interventions to raise awareness about HIV among homeless youth. HEALER’s sequential plans (built using knowledge of social networks of homeless youth) choose intervention participants strategically to maximize influence spread, while reasoning about uncertainties in the network. While previous work presents influence maximizing techniques to choose intervention participants, they do not address three real-world issues: (i) they completely fail to scale up to real-world sizes; (ii) they do not handle deviations in execution of intervention plans; (iii) constructing real-world social networks is an expensive process. HEALER handles these issues via four major contributions: (i) HEALER casts this influence maximization problem as a POMDP and solves it using a novel planner which scales up to previously unsolvable realworld sizes; (ii) HEALER allows shelter officials to modify its recommendations, and updates its future plans in a deviation-tolerant manner; (iii) HEALER constructs social networks of homeless youth at low cost, using a Facebook application. Finally, (iv) we show hardness results for the problem that HEALER solves. HEALER will be deployed in the real world in early Spring 2016 and is currently undergoing testing at a homeless shelter.
Security is a critical concern around the world. In many domains from cybersecurity to sustainability, limited security resources prevent complete security coverage at all times. Instead, these limited resources must be scheduled (or allocated or deployed), while simultaneously taking into account the importance of different targets, the responses of the adversaries to the security posture, and the potential uncertainties in adversary payoffs and observations, etc. Computational game theory can help generate such security schedules. Indeed, casting the problem as a Stackelberg game, we have developed new algorithms that are now deployed over multiple years in multiple applications for scheduling of security resources. These applications are leading to realworld use-inspired research in the emerging research area of “security games.” The research challenges posed by these applications include scaling up security games to real-world-sized problems, handling multiple types of uncertainty, and dealing with bounded rationality of human adversaries. In cybersecurity domain, the interaction between the defender and adversary is quite complicated with high degree of incomplete information and uncertainty. While solutions have been proposed for parts of the problem space in cybersecurity, the need of the hour is a comprehensive understanding of the whole space including the interaction with the adversary. We highlight the innovations in security games that could be used to tackle the game problem in cybersecurity.