Publications

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.

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 function computation. 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 buildings.

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 large groups.

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.