Publications

The potential of Artificial Intelligence (AI) to tackle challenging problems that afflict society is enormous, particularly in the areas of healthcare, conservation and public safety and security. Many problems in these domains involve harnessing social networks of under-served communities to enable positive change, e.g., using social networks of homeless youth to raise awareness about Human Immunodeficiency Virus (HIV) and other STDs. Unfortunately, most of these realworld problems are characterized by uncertainties about social network structure and influence models, and previous research in AI fails to sufficiently address these uncertainties, as they make several unrealistic simplifying assumptions for these domains. This thesis addresses these shortcomings by advancing the state-of-the-art to a new generation of algorithms for interventions in social networks. In particular, this thesis describes the design and development of new influence maximization algorithms which can handle various uncertainties that commonly exist in real-world social networks (e.g., uncertainty in social network structure, evolving network state, and availability of nodes to get influenced). These algorithms utilize techniques from sequential planning problems and social network theory to develop new kinds of AI algorithms. Further, this thesis also demonstrates the real-world impact of these algorithms by describing their deployment in three pilot studies to spread awareness about HIV among actual homeless youth in Los Angeles. This represents one of the first-ever deployments of computer science based influence maximization algorithms in this domain. Our results show that our AI algorithms improved upon the state-of-the-art by ∼ 160% in the real-world. We discuss research and implementation challenges faced in deploying these algorithms, and lessons that can be gleaned for future deployment of such algorithms. The positive results from these deployments illustrate the enormous potential of AI in addressing societally relevant problems.

Conservation of our planet’s natural resources is of the utmost importance and requires constant innovation. This project focuses on innovation for one aspect of conservation: the reduction of wildlife poaching. Park rangers patrol parks to decrease poaching by searching for poachers and animal snares left by poachers. Multiple strategies exist to aid in these patrols, including adversary behavior prediction and planning optimal ranger patrol strategies. These research efforts suffer from a key shortcoming: they fail to integrate real-time data, and rely on historical data collected during ranger patrols. Recent advances in unmanned aerial vehicle (UAV) technology have made UAVs viable tools to aid in park ranger patrols. There is now an opportunity to augment the input for these strategies in real time using computer vision, by (i) automatically detecting both animals and poachers in UAV videos, (ii) using these detections to learn future poaching locations and to plan UAV patrol routes in real time, and (iii) using poaching location predictions to determine where to fly for the next patrol. In other words, detection is done on realtime data captured aboard a UAV. Detection will then be used to learn adversaries’ behaviors, or where poaching may occur in the future, in future work. This will then be used to plan where to fly in the long term, such as the next mission. Finally, planning where to fly next during the current flight will depend on the long term plan and the real-time detections. This proposed system directly improves wildlife security. Through our collaboration with Air Shepherd, a program of the Charles A. and Anne Morrow Lindbergh Foundation, we have already begun deploying poacher detection prototypes in Africa and will deploy further advances there in the future (Fig. 1). Furthermore, this also applies to similar surveillance tasks, such as locating people after natural disasters.

Election control considers the problem of an adversary who attempts to tamper with a voting process, in order to either ensure that their favored candidate wins (constructive control) or another candidate loses (destructive control). As online social networks have become significant sources of information for potential voters, a new tool in an attacker’s arsenal is to effect control by harnessing social influence, for example, by spreading fake news and other forms of misinformation through online social media. We consider the computational problem of election control via social influence, studying the conditions under which finding good adversarial strategies is computationally feasible. We consider two objectives for the adversary in both the constructive and destructive control settings: probability and margin of victory (POV and MOV, respectively). We present several strong negative results, showing, for example, that the problem of maximizing POV is inapproximable for any constant factor. On the other hand, we present approximation algorithms which provide somewhat weaker approximation guarantees, such as bicriteria approximations for the POV objective and constant-factor approximations for MOV. Finally, we present mixed integer programming formulations for these problems. Experimental results show that our approximation algorithms often find near-optimal control strategies, indicating that election control through social influence is a salient threat to election integrity.

An important way cyber adversaries find vulnerabilities in modern networks is through reconnaissance, in which they attempt to identify configuration specifics of network hosts. To increase uncertainty of adversarial reconnaissance, the network administrator (henceforth, defender) can introduce deception into responses to network scans, such as obscuring certain system characteristics. We introduce a novel game-theoretic model of deceptive interactions of this kind between a defender and a cyber attacker, which we call the Cyber Deception Game. We consider both a powerful (rational) attacker, who is aware of the defender’s exact deception strategy, and a naive attacker who is not. We show that computing the optimal deception strategy is NP-hard for both types of attackers. For the case with a powerful attacker, we provide a mixed-integer linear program solution as well as a fast and effective greedy algorithm. Similarly, we provide complexity results and propose exact and heuristic approaches when the attacker is naive. Our extensive experimental analysis demonstrates the effectiveness of our approaches.

We consider the problem of designing fair, efficient, and interpretable policies for prioritizing heterogeneous homeless youth on a waiting list for scarce housing resources of different types. We focus on point-based policies that use features of the housing resources (e.g., permanent supportive housing, rapid rehousing) and the youth (e.g., age, history of substance use) to maximize the probability that the youth will have a safe and stable exit from the housing program. The policies can be used to prioritize waitlisted youth each time a housing resource is procured. Our framework provides the policy-maker the flexibility to select both their desired structure for the policy and their desired fairness requirements. Our approach can thus explicitly trade-off interpretability and efficiency while ensuring that fairness constraints are met. We propose a flexible data-driven mixed-integer optimization formulation for designing the policy, along with an approximate formulation which can be solved efficiently for broad classes of interpretable policies using Bender’s decomposition. We evaluate our framework using real-world data from the United States homeless youth housing system. We show that our framework results in policies that are more fair than the current policy in place and than classical interpretable machine learning approaches while achieving a similar (or higher) level of overall efficiency.

We define a class of zero-sum games with combinatorial structure, where the best response problem of one player is to maximize a submodular function. For example, this class includes security games played on networks, as well as the problem of robustly optimizing a submodular function over the worst case from a set of scenarios. The challenge in computing equilibria is that both players’ strategy spaces can be exponentially large. Accordingly, previous algorithms have worst-case exponential runtime and indeed fail to scale up on practical instances. We provide a pseudopolynomial-time algorithm which obtains a guaranteed (1 − 1/e) 2 -approximate mixed strategy for the maximizing player. Our algorithm only requires access to a weakened version of a best response oracle for the minimizing player which runs in polynomial time. Experimental results for network security games and a robust budget allocation problem confirm that our algorithm delivers near-optimal solutions and scales to much larger instances than was previously possible.

Significant research effort in security games has focused in devising strategies that perform well even when the attacker deviates from optimal (rational) behavior. In most of these frameworks, a price needs to be paid to ensure robustness against this unpredictability. However, equilibrium refinement is an attractive alternative to boost solution robustness at no cost even though it has not received as much attention in security game literature. In this framework, resources are strategically allocated to secure an optimal outcome against a rational adversary while simultaneously protecting other targets to ensure good outcomes against boundedly rational or constrained attackers. Unfortunately, existing approaches for equilibrium refinement in security games cannot effectively address scheduling constraints that arise frequently in real-world applications. In this paper, we aim to fill this gap and make several key contributions. First, we show that existing approaches for equilibrium refinement can fail in the presence of scheduling constraints. Second, we investigate the properties of the best response of the attacker. Third, we leverage these properties to devise novel iterative algorithms to compute the optimally refined equilibrium, with polynomially many calls to an LP oracle for zero-sum games. Finally, we conduct extensive experimental evaluations that showcase i) the superior performance of our approach in the face of a boundedly rational attacker and ii) the attractive scalability properties of our algorithm that can solve realistic-sized instances.

There are nearly 2 million homeless youth in the United States each year. Coordinated entry systems are being used to provide homeless youth with housing assistance across the nation. Despite these efforts, the number of youth still homeless or unstably housed remains very high. Motivated by this fact, we initiate a first study to understand and analyze the current governmental housing systems for homeless youth. In this paper, we aim to provide answers to the following questions: (1) What is the current governmental housing system for assigning homeless youth to different housing assistance? (2) Can we infer the current assignment guidelines of the local housing communities? (3) What is the result and outcome of the current assignment process? (4) Can we predict whether the youth will be homeless after receiving the housing assistance? To answer these questions, we first provide an overview of the current housing systems. Next, we use simple and interpretable machine learning tools to infer the decision rules of the local communities and evaluate the outcomes of such assignment. We then determine whether the vulnerability features/rubrics can be used to predict youth’s homelessness status after receiving housing assistance. Finally, we discuss the policy recommendations from our study for the local co

Colluding adversaries is a crucial challenge for defenders in many real-world applications. Previous literature has provided Collusive Security Games (COSG) to model colluding adversaries, and provided models and algorithms to generate defender strategies to counter colluding adversaries, often by devising strategies that inhibit collusion [6]. Unfortunately, this previous work focused exclusively on situations with perfectly matched adversaries, i.e., where their rewards were symmetrically distributed. In the real world, however, defenders often face adversaries where their rewards are asymmetrically distributed. Such inherent asymmetry raises a question as to whether human adversaries would attempt to collude in such situations, and whether defender strategies to counter such collusion should focus on inhibiting collusion. To address these open questions, this paper: (i) explores and theoretically analyzes Imbalanced Collusive Security Games (ICOSG) where defenders face adversaries with asymmetrically distributed rewards; (ii) conducts extensive experiments of three different adversary models involving 1800 real human subjects and (iii) derives novel analysis of the reason behind why bounded rational attackers models outperform perfectly rational attackers models. The key principle discovered as the result of our experiments is that: careful modeling of human bounded rationality reveals a key difference (when compared to a model using perfect rationality) in defender strategies for handling colluding adversaries which face symmetric vs asymmetric rewards. Whereas a model based on perfect rationality always attempts to break collusion among adversaries, a bounded rationality model acknowledges the inherent difficulty of breaking such collusion in symmetric situations and focuses only on breaking collusion in asymmetric situation, and only on damage control from collusion in the symmetric situation.

Strong Stackelberg equilibrium (SSE) is the standard solution concept of Stackelberg security games. The SSE assumes that the follower breaks ties in favor of the leader and this is widely acknowledged and justified by the assertion that the defender can often induce the attacker to choose a preferred action by making an infinitesimal adjustment to her strategy. Unfortunately, in security games with resource assignment constraints, the assertion might not be valid. To overcome this issue, inspired by the notion of inducibility and the pessimistic Stackelberg equilibrium [20, 21], this paper presents the inducible Stackelberg equilibrium (ISE), which is guaranteed to exist and avoids overoptimism as the outcome can always be induced with infinitesimal strategy deviation. Experimental evaluation unveils the significant overoptimism and sub-optimality of SSE and thus, verifies the advantage of the ISE as an alternative solution concept.

To improve cyber defense, researchers have developed algorithms to allocate limited defense resources optimally. Through signaling theory, we have learned that it is possible to trick the human mind when using deceptive signals. The present work is an initial step towards developing a psychological theory of cyber deception. We use simulations to investigate how humans might make decisions under various conditions of deceptive signals in cyber-attack scenarios. We created an Instance-Based Learning (IBL) model of the attacker decisions using the ACT-R cognitive architecture. We ran simulations against the optimal deceptive signaling algorithm and against four alternative deceptive signal schemes. Our results show that the optimal deceptive algorithm is more effective at reducing the probability of attack and protecting assets compared to other signaling conditions, but it is not perfect. These results shed some light on the expected effectiveness of deceptive signals for defense. The implications of these findings are discussed.

Youth homelessness has reached a concerning level of prevalence in the United States. Many communities have attempted to address this problem by creating coordinated community responses, typically referred to as Coordinated Entry Systems (CES). In such systems, agencies within a community pool their housing resources in a centralized system. Youth seeking housing are first assessed for eligibility and vulnerability and then linked to appropriate housing resources. The most widely adopted tool for assessing youth vulnerability is the Transition Age Youth-Vulnerability Index-Service Prioritization Decision Assistance Tool (TAY-VI-SPDAT): Next Step Tool (NST) for homeless youth. To date, no evidence has been amassed to support the value of using this tool or its proposed scoring schematic to prioritize housing resources. Similarly, there is little evidence on the outcomes of youth whose placements are determined by the tool. This article presents the first comprehensive and rigorous evaluation of the connection between vulnerability scores, housing placements, and stability of housing outcomes using data from the Homeless Management Information System (HMIS) collected between 2015 and 2017 from 16 communities across the United States. The two primary aims are (1) to investigate the degree to which communities are using the tool’s recommendations when placing youth into housing programs, and (2) to examine how effectively NST scores distinguish between youth in greater need of formal housing interventions from youth who may be able to self-resolve or return to family successfully. High vulnerability scores at intake were associated with higher odds of continued homelessness without housing intervention, suggesting the tool performs well in predicting youth that need to be prioritized for housing services in the context of limited resources. The majority of low scoring youth appear to return home or self-resolve and remain stably exited from homelessness. Youth placed in permanent supportive housing (PSH) had low recorded returns to homelessness, regardless of their NST score. Youth with vulnerability scores up to 10 who were placed in rapid rehousing (RRH) also had low returns to homelessness, but success was much more variable for higher-scoring youth.

The unrelenting threat of poaching has led to increased development of new technologies to combat it. One such example is the use of thermal infrared cameras mounted on unmanned aerial vehicles (UAVs or drones) to spot poachers at night and report them to park rangers before they are able to harm any animals. However, monitoring the live video stream from these conservation UAVs all night is an arduous task. Therefore, we discuss SPOT (Systematic POacher deTector), a novel application that augments conservation drones with the ability to automatically detect poachers and animals in near real time [Bondi et al., 2018b]. SPOT illustrates the feasibility of building upon state-of-the-art AI techniques, such as Faster RCNN, to address the challenges of automatically detecting animals and poachers in infrared images. This paper reports (i) the design of SPOT, (ii) efficient processing techniques to ensure usability in the field, (iii) evaluation of SPOT based on historical videos and a real-world test run by the end-users, Air Shepherd, in the field, and (iv) the use of AirSim for live demonstration of SPOT. The promising results from a field test have led to a plan for larger-scale deployment in a national park in southern Africa. While SPOT is developed for conservation drones, its design and novel techniques have wider application for automated detection from UAV videos.

More than 1 million homicides, robberies, and aggravated assaults occur in the United States each year. These crimes are often further classified into different types based on the circumstances surrounding the crime (e.g., domestic violence, gang-related). Despite recent technological advances in AI and machine learning, these additional classification tasks are still done manually by specially trained police officers. In this paper, we provide the first attempt to develop a more automatic system for classifying crimes. In particular, we study the question of classifying whether a given violent crime is gang-related. We introduce a novel Partially Generative Neural Networks (PGNN) that is able to accurately classify gang-related crimes both when full information is available and when there is only partial information. Our PGNN is the first generative-classification model that enables to work when some features of the test examples are missing. Using a crime event dataset from Los Angeles covering 2014-2016, we experimentally show that our PGNN outperforms all other typically used classifiers for the problem of classifying gangrelated violent crimes.

A wealth of algorithms centered around (integer) linear programming have been proposed to compute equilibrium strategies in security games with discrete states and actions. However, in practice many domains possess continuous state and action spaces. In this paper, we consider a continuous space security game model with infinite-size action sets for players and present a novel deep learning based approach to extend the existing toolkit for solving security games. Specifically, we present (i) OptGradFP, a novel and general algorithm that searches for the optimal defender strategy in a parameterized continuous search space, and can also be used to learn policies over multiple game states simultaneously; (ii) OptGradFP-NN, a convolutional neural network based implementation of OptGradFP for continuous space security games. We demonstrate the potential to predict good defender strategies via experiments and analysis of OptGradFP and OptGradFP-NN on discrete and continuous game settings.

Treatable infectious diseases are a critical challenge for public health. Outreach campaigns can encourage undiagnosed patients to seek treatment but must be carefully targeted to make the most efficient use of limited resources. We present an algorithm to optimally allocate limited outreach resources among demographic groups in the population. The algorithm uses a novel multiagent model of disease spread which both captures the underlying population dynamics and is amenable to optimization. Our algorithm extends, with provable guarantees, to a stochastic setting where we have only a distribution over parameters such as the contact pattern between agents. We evaluate our algorithm on two instances where this distribution is inferred from real world data: tuberculosis in India and gonorrhea in the United States. Our algorithm produces a policy which is predicted to avert an average of least 8,000 person-years of tuberculosis and 20,000 personyears of gonorrhea annually compared to current policy.

We consider the problem of allocating scarce security resources among heterogeneous targets to thwart a possible attack. It is well known that deterministic solutions to this problem being highly predictable are severely suboptimal. To mitigate this predictability, the game-theoretic security game model was proposed which randomizes over pure (deterministic) strategies, causing confusion in the adversary. Unfortunately, such mixed strategies typically randomize over a large number of strategies, requiring security personnel to be familiar with numerous protocols, making them hard to operationalize. Motivated by these practical considerations, we propose an easy to use approach for computing strategies that are easy to operationalize and that bridge the gap between the static solution and the optimal mixed strategy. These strategies only randomize over an optimally chosen subset of pure strategies whose cardinality is selected by the defender, enabling them to conveniently tune the trade-off between ease of operationalization and efficiency using a single design parameter. We show that the problem of computing such operationalizable strategies is NP-hard, formulate it as a mixedinteger optimization problem, provide an algorithm for computing ✏-optimal equilibria, and an efficient heuristic. We evaluate the performance of our approach on the problem of screening for threats at airport checkpoints and show that the Price of Usability, i.e., the loss in optimality to obtain a strategy that is easier to operationalize, is typically not high.

The conditional value at risk (CVaR) is a popular risk measure which enables risk-averse decision making under uncertainty. We consider maximizing the CVaR of a continuous submodular function, an extension of submodular set functions to a continuous domain. One example application is allocating a continuous amount of energy to each sensor in a network, with the goal of detecting intrusion or contamination. Previous work allows maximization of the CVaR of a linear or concave function. Continuous submodularity represents a natural set of nonconcave functions with diminishing returns, to which existing techniques do not apply. We give a (1 − 1/e)-approximation algorithm for maximizing the CVaR of a monotone continuous submodular function. This also yields an algorithm for submodular set functions which produces a distribution over feasible sets with guaranteed CVaR. Experimental results in two sensor placement domains confirm that our algorithm substantially outperforms competitive baselines.

We consider the problem of monitoring a set of targets, using scarce monitoring resources (e.g., sensors) that are subject to adversarial attacks. In particular, we propose a constant-sum Stackelberg game in which a defender (leader) chooses among possible monitoring locations, each covering a subset of targets, while taking into account the monitor failures induced by a resource-constrained attacker (follower). In contrast to the previous Stackelberg security models in which the defender uses mixed strategies, here, the defender must commit to pure strategies. This problem is highly intractable as both players’ strategy sets are exponentially large. Thus, we propose a solution methodology that automatically partitions the set of adversary’s strategies and maps each subset to a coverage policy. These policies are such that they do not overestimate the defender’s payoff. We show that the partitioning problem can be reformulated exactly as a mixed-integer linear program (MILP) of moderate size which can be solved with off-the-shelf solvers. We demonstrate the effectiveness of our proposed approach in various settings. In particular, we illustrate that even with few policies, we are able to closely approximate the optimal solution and outperform the heuristic solutions.

Stackelberg Security Games (SSGs) have been adopted widely for modeling adversarial interactions, wherein scalability of equilibrium computation is an important research problem. While prior research has made progress with regards to scalability, many real world problems cannot be solved satisfactorily yet as per current requirements; these include the deployed federal air marshals (FAMS) application and the threat screening (TSG) problem at airports. We initiate a principled study of approximations in zero-sum SSGs. Our contribution includes the following: (1) a unified model of SSGs called adversarial randomized allocation (ARA) games, (2) hardness of approximation for zero-sum ARA, as well as for the FAMS and TSG sub-problems, (3) an approximation framework for zero-sum ARA with instantiations for FAMS and TSG using intelligent heuristics, and (4) experiments demonstrating the significant 1000x improvement in runtime with an acceptable loss.