Among the many deployment areas of Stackelberg Security games, a major area involves games played out in
space and time, which includes applications in multiple
mobile defender resources protecting multiple mobile
targets. Previous algorithms for such spatio-temporal
security games fail to scale-up and little is known of
the computational complexity properties of these problems. This paper provides a novel oracle-based algorithmic framework for a systematic study of different problem variants of computing optimal (minimax) strategies
in spatio-temporal security games. Our framework enables efficient computation of a minimax strategy when
the problem admits a polynomial-time oracle. Furthermore, for the cases in which efficient oracles are difficult to find, we propose approximations or prove hardness results.
To dissuade reckless driving and mitigate accidents,
cities deploy resources to patrol roads. In this paper, we
present STREETS, an application developed for the city
of Singapore, which models the problem of computing randomized traffic patrol strategies as a defenderattacker Stackelberg game. Previous work on Stackelberg security games has focused extensively on counterterrorism settings. STREETS moves beyond counterterrorism and represents the first use of Stackelberg
games for traffic patrolling, in the process providing a
novel algorithm for solving such games that addresses
three major challenges in modeling and scale-up. First,
there exists a high degree of unpredictability in travel
times through road networks, which we capture using
a Markov Decision Process for planning the patrols of
the defender (the police) in the game. Second, modeling all possible police patrols and their interactions
with a large number of adversaries (drivers) introduces
a significant scalability challenge. To address this challenge we apply a compact game representation in a
novel fashion combined with adversary and state sampling. Third, patrol strategies must balance exploitation
(minimizing violations) with exploration (maximizing
omnipresence), a tradeoff we model by solving a biobjective optimization problem. We present experimental results using real-world traffic data from Singapore.
This work is done in collaboration with the Singapore
Ministry of Home Affairs and is currently being evaluated by the Singapore Police Force.
L. S. Marcolino, H. Xu, A.X. Jiang, M. Tambe, and E. Bowring. 2014. “Team Formation in Large Action Spaces .” In In 17th International Workshop on Coordination, Organizations, Institutions and Norms (COIN 2014). Paris, France.Abstract
Recent work has shown that diverse teams can outperform
a uniform team made of copies of the best agent. However, there are
fundamental questions that were not asked before. When should we use
diverse or uniform teams? How does the performance change as the action
space or the teams get larger? Hence, we present a new model of diversity
for teams, that is more general than previous models. We prove that
the performance of a diverse team improves as the size of the action
space gets larger. Concerning the size of the diverse team, we show that
the performance converges exponentially fast to the optimal one as we
increase the number of agents. We present synthetic experiments that
allow us to gain further insights: even though a diverse team outperforms
a uniform team when the size of the action space increases, the uniform
team will eventually again play better than the diverse team for a large
enough action space. We verify our predictions in a system of Go playing
agents, where we show a diverse team that improves in performance as
the board size increases, and eventually overcomes a uniform team.
This paper presents TESLA, an agent for optimizing energy usage in commercial buildings. TESLA’s key insight is that adding flexibility to event/meeting
schedules can lead to significant energy savings. This paper provides four key contributions: (i) online scheduling algorithms, which are at the heart of TESLA, to solve
a stochastic mixed integer linear program (SMILP) for energy-efficient scheduling of
incrementally/dynamically arriving meetings and events; (ii) an algorithm to effectively identify key meetings that lead to significant energy savings by adjusting their
flexibility; (iii) an extensive analysis on energy savings achieved by TESLA; and (iv)
surveys of real users which indicate that TESLA’s assumptions of user flexibility hold
in practice. TESLA was evaluated on data gathered from over 110,000 meetings held
at nine campus buildings during an eight month period in 2011–2012 at the University of Southern California (USC) and the Singapore Management University (SMU).
These results and analysis show that, compared to the current systems, TESLA can
substantially reduce overall energy consumption.
In urban transportation networks, crime diffuses as criminals travel
through the networks and look for illicit opportunities. It is important to first model this diffusion in order to recommend actions
or patrol policies to control the diffusion of such crime. Previously,
game theory has been used for such patrol policy recommendations,
but these applications of game theory for security have not modeled
the diffusion of crime that comes about due to criminals seeking
opportunities; instead the focus has been on highly strategic adversaries that plan attacks in advance. To overcome this limitation of
previous work, this paper provides the following key contributions.
First, we provide a model of crime diffusion based on a quantal
biased random movement (QBRM) of criminals opportunistically
and repeatedly seeking targets. Within this model, criminals react
to real-time information, rather than strategically planning their attack in advance. Second, we provide a game-theoretic approach to
generate randomized patrol policies for controlling such diffusion.
Multiagent teamwork and defender-attacker security games are
two areas that are currently receiving significant attention within
multiagent systems research. Unfortunately, despite the need for effective teamwork among multiple defenders, little has been done to
harness the teamwork research in security games. This paper is the
first to remedy this situation by integrating the powerful teamwork
mechanisms offered by Dec-MDPs into security games. We offer the
following novel contributions in this paper: (i) New models of security games where a defender team’s pure strategy is defined as a DecMDP policy for addressing coordination under uncertainty; (ii) New
algorithms based on column generation that enable efficient generation of mixed strategies given this new model; (iii) Handling global
events during defender execution for effective teamwork; (iv) Exploration of the robustness of randomized pure strategies. The paper
opens the door to a potentially new area combining computational
game theory and multiagent teamwork.
Illegal poaching is an international problem that leads to the extinction of species and the destruction of ecosystems. As evidenced by dangerously dwindling populations of endangered species, existing anti-poaching mechanisms are insufficient. This paper introduces the Protection Assistant for Wildlife Security (PAWS) application - a joint deployment effort done with researchers at Uganda’s Queen Elizabeth National Park (QENP) with the goal of improving wildlife ranger patrols. While previous works have deployed applications with a game-theoretic approach (specifically Stackelberg Games) for counter-terrorism, wildlife crime is an important domain that promotes a wide range of new deployments. Additionally, this domain presents new research challenges and opportunities related to learning behavioral models from collected poaching data. In addressing these challenges, our first contribution is a behavioral model extension that captures the heterogeneity of poachers’ decision making processes. Second, we provide a novel framework, PAWS-Learn, that incrementally improves the behavioral model of the poacher population with more data. Third, we develop a new algorithm, PAWS-Adapt, that adaptively improves the resource allocation strategy against the learned model of poachers. Fourth, we demonstrate PAWS’s potential effectiveness when applied to patrols in QENP, where PAWS will be deployed.
Given the real-world applications of Stackelberg security games (SSGs), addressing uncertainties in these games is a major challenge. Unfortunately, we lack any unified computational framework for handling uncertainties in SSGs. Current state-of-the-art has provided only compartmentalized robust algorithms that handle uncertainty exclusively either in the defender’s strategy or in adversary’s payoff or in the adversary’s rationality, leading to potential failures in real-world scenarios where a defender often faces multiple types of uncertainties. Furthermore, insights for improving performance are not leveraged across the compartments, leading to significant losses in quality or efficiency. In this paper, we provide the following main contributions: 1) we present the first unified framework for handling the uncertainties explored in SSGs; 2) based on this unified framework, we propose the first set of “unified” robust algorithms to address combinations of these uncertainties; 3) we introduce approximate scalable robust algorithms for handling these uncertainties that leverage insights across compartments; 4) we present experiments demonstrating solution quality and runtime advantages of our algorithms.
Agent-based systems for energy conservation are now a growing area of research in multiagent
systems, with applications ranging from energy management and control on the smart grid, to
energy conservation in residential buildings, to energy generation and dynamic negotiations in
distributed rural communities. Contributing to this area, my thesis presents new agent-based
models and algorithms aiming to conserve energy in commercial buildings.
More specifically, my thesis provides three sets of algorithmic contributions. First, I provide
online predictive scheduling algorithms to handle massive numbers of meeting/event scheduling
requests considering flexibility, which is a novel concept for capturing generic user constraints
while optimizing the desired objective. Second, I present a novel BM-MDP (Bounded-parameter
Multi-objective Markov Decision Problem) model and robust algorithms for multi-objective
optimization under uncertainty both at the planning and execution time. The BM-MDP model
and its robust algorithms are useful in (re)scheduling events to achieve energy efficiency in the
presence of uncertainty over user’s preferences. Third, when multiple users contribute to energy
savings, fair division of credit for such savings to incentivize users for their energy saving activities
arises as an important question. I appeal to cooperative game theory and specifically to the concept
of Shapley value for this fair division. Unfortunately, scaling up this Shapley value computation is
a major hindrance in practice. Therefore, I present novel approximation algorithms to efficiently compute the Shapley value based on sampling and partitions and to speed up the characteristic
These new models have not only advanced the state of the art in multiagent algorithms, but
have actually been successfully integrated within agents dedicated to energy efficiency: SAVES,
TESLA and THINC. SAVES focuses on the day-to-day energy consumption of individuals and
groups in commercial buildings by reactively suggesting energy conserving alternatives. TESLA
takes a long-range planning perspective and optimizes overall energy consumption of a large
number of group events or meetings together. THINC provides an end-to-end integration within
a single agent of energy efficient scheduling, rescheduling and credit allocation. While SAVES,
TESLA and THINC thus differ in their scope and applicability, they demonstrate the utility of
agent-based systems in actually reducing energy consumption in commercial buildings.
I evaluate my algorithms and agents using extensive analysis on data from over 110,000 real
meetings/events at multiple educational buildings including the main libraries at the University
of Southern California. I also provide results on simulations and real-world experiments, clearly
demonstrating the power of agent technology to assist human users in saving energy in commercial
Recently, there has been significant research interest in using game-theoretic approaches to allocate limited security resources to protect physical infrastructure including ports, airports, transit systems, and other critical national infrastructure as well as natural resources such as forests,
tigers, fish, and so on. Indeed, the leader-follower Stackelberg game model is at the heart of many
deployed applications. In these applications, the game model provides a randomized strategy for
the leader (security forces), under the assumption that the adversary will conduct surveillance
before launching an attack. Inevitably, the security forces are faced with the problem of uncertainty. For example, a security officer may be forced to execute a different patrol strategy from the
planned one due to unexpected events. Also, there may be significant uncertainty regarding the
amount of surveillance conducted by an adversary. While Bayesian Stackelberg games for modeling discrete uncertainty have been successfully used in deployed applications, they are NP-hard
problems and existing methods perform poorly in scaling up the number of types: inadequate for
complex real world problems. Furthermore, Bayesian Stackelberg games have not been applied
to model execution and observation uncertainty and finally, they require the availability of full
distributional information of the uncertainty. To overcome these difficulties, my thesis presents four major contributions. First, I provide
a novel algorithm Hunter for Bayesian Stackelberg games to scale up the number of types. Exploiting the efficiency of Hunter, I show preference, execution and observation uncertainty can
be addressed in a unified framework. Second, to address execution and observation uncertainty
(where distribution may be difficult to estimate), I provide a robust optimization formulation to
compute the optimal risk-averse leader strategy in Stackelberg games. Third, addressing the uncertainty of the adversary’s capability of conducting surveillance, I show that for a class of Stackelberg games motivated by real security applications, the leader is always best-responding with a
Stackelberg equilibrium strategy regardless of whether the adversary conducts surveillance or not.
As the final contribution, I provide TRUSTS, a novel game-theoretic formulation for scheduling
randomized patrols in public transit domains where timing is a crucial component. TRUSTS
addresses dynamic execution uncertainty in such spatiotemporal domains by integrating Markov
Decision Processes into the game-theoretic model. Simulation results as well as real-world trials
of TRUSTS in the Los Angeles Metro Rail system provide validations of my approach.
Recent deployments of Stackelberg security games (SSG)
have led to two competing approaches to handle boundedly
rational human adversaries: (1) integrating models of human (adversary) decision-making into the game-theoretic algorithms, and (2) applying robust optimization techniques
that avoid adversary modeling. A recent algorithm (MATCH)
based on the second approach was shown to outperform the
leading modeling-based algorithm even in the presence of
significant amount of data. Is there then any value in using human behavior models in solving SSGs? Through extensive experiments with 547 human subjects playing 11102
games in total, we emphatically answer the question in the
affirmative, while providing the following key contributions:
(i) we show that our algorithm, SU-BRQR, based on a novel
integration of human behavior model with the subjective utility function, significantly outperforms both MATCH and its
improvements; (ii) we are the first to present experimental
results with security intelligence experts, and find that even
though the experts are more rational than the Amazon Turk
workers, SU-BRQR still outperforms an approach assuming
perfect rationality (and to a more limited extent MATCH);
(iii) we show the advantage of SU-BRQR in a new, large
game setting and demonstrate that sufficient data enables it
to improve its performance over MATCH.
Influence blocking games have been used to model
adversarial domains with a social component, such as counterinsurgency. In these games, a mitigator attempts to minimize the
efforts of an influencer to spread his agenda across a social
network. Previous work has assumed that the influence graph
structure is known with certainty by both players. However, in
reality, there is often significant information asymmetry between
the mitigator and the influencer. We introduce a model of this
information asymmetry as a two-player zero-sum Bayesian game.
Nearly all past work in influence maximization and social network
analysis suggests that graph structure is fundamental in strategy
generation, leading to an expectation that solving the Bayesian
game exactly is crucial. Surprisingly, we show through extensive
experimentation on synthetic and real-world social networks that
many common forms of uncertainty can be addressed nearoptimally by ignoring the vast majority of it and simply solving an
abstracted game with a few randomly chosen types. This suggests
that optimal strategies of games that do not model the full range
of uncertainty in influence blocking games are typically robust
to uncertainty about the influence graph structure.
Influence blocking games have been used to model adversarial domains with a social component, such as counterinsurgency. In these
games, a mitigator attempts to minimize the efforts of an influencer
to spread his agenda across a social network which is modeled as a
graph. Previous work has assumed that the influence graph structure is known with certainty by both players. However, in reality,
there is often significant information asymmetry between the mitigator and the influencer. We introduce a model of this information
asymmetry as a two-player zero-sum Bayesian game. Nearly all
past work in influence maximization and social network analysis
suggests that graph structure is fundamental in strategy generation,
leading to an expectation that solving the Bayesian game exactly
would be vastly superior to any technique that does not account
for uncertainty about the network structure. Surprisingly, we show
through extensive experimentation on synthetic and real-world social networks that many common forms of uncertainty can be addressed near-optimally by ignoring the vast majority of it and simply solving an abstracted game with a few randomly chosen types.
This suggests that optimal strategies of games that do not model
the full range of uncertainty in influence blocking games are in
many cases robust to uncertainty about the structure of the influence graph.
Influence blocking games have been used to model adversarial domains with a social component, such as counterinsurgency. In these games, a mitigator attempts to minimize the efforts of an influencer to spread his agenda across a social network. Previous work has assumed that the influence graph structure is known with certainty by both players. However, in reality, there is often significant information asymmetry between the mitigator and the influencer. We introduce a model of this information asymmetry as a two-player zero-sum Bayesian game. Nearly all past work in influence maximization and social network analysis suggests that graph structure is fundamental in strategy generation, leading to an expectation that solving the Bayesian game exactly is crucial. Surprisingly, we show through extensive experimentation on synthetic and real-world social networks that many common forms of uncertainty can be addressed near-optimally by ignoring the vast majority of it and simply solving an abstracted game with a few randomly chosen types. This suggests that optimal strategies of games that do not model the full range of uncertainty in influence blocking games are typically robust to uncertainty about the influence graph structure.
Computational models of moral cognition will be critical to the creation of agents
and robots that operate autonomously in morally sensitive and complex domains. We
propose a framework for developing computational models of moral cognition based on
behavioral and neurobiological experimental results and field observations. Specifically,
we discuss the following critical issues in building such models: 1. Managing conflicts
between different moral concerns; 2. The role of moral perceptions in moral judgments;
3. Mechanisms and consequences of moral emotions; 4. Learning and adjusting moral
behavior. Moreover, we discuss computational architectures for building and exploring
models of moral cognition at different levels of analysis: individual, small groups and
We study security games with multiple defenders.
To achieve maximum security, defenders must perfectly synchronize their randomized allocations of
resources. However, in real-life scenarios (such as
protection of the port of Boston) this is not the case.
Our goal is to quantify the loss incurred by miscoordination between defenders, both theoretically
and empirically. We introduce two notions that
capture this loss under different assumptions: the
price of miscoordination, and the price of sequential commitment. Generally speaking, our theoretical bounds indicate that the loss may be extremely
high in the worst case, while our simulations establish a smaller yet significant loss in practice.
In this paper we describe the model, theory developed and deployment of PROTECT, a game-theoretic system in use by the United States Coast Guard (USCG) in the Port of Boston for scheduling patrols. The USCG evaluated the deployment of PROTECT in the Port of Boston as a success and is currently evaluating the system in the Port of New York, with the potential for nationwide deployment. The PROTECT system is premised on an attacker-defender Stackelberg game model but its development and implementation required both theoretical contributions and detailed evaluations. In this paper we describe the work required in the deployment which we group into five key innovations. First, we propose a compact representation of the defender’s strategy space, by exploiting equivalence and dominance, that makes PROTECT efficient enough to solve real world sized problems. Second, this system does not assume that adversaries are perfectly rational, a regular assumption in previous game theoretic models for security. Instead, PROTECT relies on a quantal response (QR) model of the adversary’s behavior — to the best of our knowledge, this is the first real-world deployment of a QR model. Third, we develop specialized solution algorithms that are able to solve this problem for real-world instances and give theoretical guarantees. Fourth, our experimental results illustrate that PROTECT’s QR model handles real-world uncertainties more robustly than a perfect rationality model. Finally, this paper presents real-world evaluation of PROTECT by: (i) a comparison of human-generated vs PROTECT security schedules, and (ii) results from an Adversarial Perspective Team’s (human mock attackers) analysis.
Previous work on Stackelberg Security Games for scheduling security resources has mostly assumed that the targets are stationary relative to the
defender and the attacker, leading to discrete game models with finite numbers of
pure strategies. This paper in contrast focuses on protecting mobile targets that
lead to a continuous set of strategies for the players. The problem is motivated
by several real-world domains including protecting ferries with escorts and protecting refugee supply lines. Our contributions include: (i) a new game model for
multiple mobile defender resources and moving targets with a discretized strategy space for the defender and a continuous strategy space for the attacker; (ii)
an efficient linear-program-based solution that uses a compact representation for
the defender’s mixed strategy, while accurately modeling the attacker’s continuous strategy using a novel sub-interval analysis method; (iii) a heuristic method
of equilibrium refinement for improved robustness and (iv) detailed experimental
analysis in the ferry protection domain.
Team formation is a critical step in deploying a multi-agent team.
In some scenarios, agents coordinate by voting continuously. When
forming such teams, should we focus on the diversity of the team or
on the strength of each member? Can a team of diverse (and weak)
agents outperform a uniform team of strong agents? In this demo,
the user will be able to explore these questions by playing one of
the most challenging board games: Go.
Despite recent successful real-world deployments
of Stackelberg Security Games (SSGs), scale-up remains a fundamental challenge in this field. The
latest techniques do not scale-up to domains where
multiple defenders must coordinate time-dependent
joint activities. To address this challenge, this paper
presents two branch-and-price algorithms for solving SSGs, SMARTO and SMARTH, with three novel
features: (i) a column-generation approach that
uses an ordered network of nodes (determined by
solving the traveling salesman problem) to generate individual defender strategies; (ii) exploitation
of iterative reward shaping of multiple coordinating
defender units to generate coordinated strategies;
(iii) generation of tighter upper-bounds for pruning by solving security games that only abide by
key scheduling constraints. We provide extensive
experimental results and formal analyses.