Publications

2018
Haifeng Xu. 8/2018. “Information as a Double-Edged Sword in Strategic Interactions ”.Abstract
This thesis considers the following question: in systems with self-interested agents (a.k.a.,
games), how does information — i.e., what each agent knows about their environment and other
agents’ preferences — affect their decision making? The study of the role of information in
games has a rich history, and in fact forms the celebrated field of information economics. However, different from previous descriptive study, this thesis takes a prescriptive approach and examines computational questions pertaining to the role of information. In particular, it illustrates
the double-edged role of information through two threads of research: (1) how to utilize information to one’s own advantage in strategic interactions; (2) how to mitigate losses resulting from
information leakage to an adversary. In each part, we study the algorithmic foundation of basic
models and also develop efficient solutions to real-world problems arising from physical security
domains. Besides pushing the research frontier, the work of this thesis is also directly impacting
several real-world applications, resulting in delivered software for improving the scheduling of
US federal air marshals and the design of patrolling routes for wildlife conservation.
More concretely, the first part of this thesis studies an intrinsic phenomenon in human endeavors termed persuasion — i.e., the act of exploiting an informational advantage in order to
influence the decisions of others. We start with two real-world motivating examples, illustrating
how security agencies can utilize an informational advantage to influence adversaries’ decisions
and deter potential attacks. Afterwards, we provide a systematic algorithmic study for the foundational economic models underlying these examples. Our analysis not only fully resolves the
complexity of these models, but also leads to new economic insights. We then leverage the insights and algorithmic ideas from our theoretical analysis to develop new models and solutions
for concrete real-world security problems.
The second part of this thesis studies the other side of the double-edged sword, namely, how
to deal with disadvantages due to information leakage. We also start with real-world motivating
examples to illustrate how classified information about security measures may leak to the adversary and cause significant loss to security agencies. We then propose different models to capture
information leakage based on how much the security agency is aware of the leakage situation,
and provide thorough algorithmic analysis for these models. Finally, we return to the real-world
problems and design computationally efficient algorithms tailored to each security domain.
Sara Marie Mc Carthy. 8/2018. “Hierarchical Planning in Security Games; A Game Theoretic Approach to Strategic, Tactical and Operational Decision Making”.Abstract
In the presence of an intelligent adversary, game theoretic models such as security games, have proven to be effective tools for mitigating risks from exploitable gaps in protection and security protocols, as they model the strategic interaction between an adversary and defender, and allow the defender to plan the use of scarce or limited resources in the face of such an adversary. However, standard security game models have limited expressivity in the types of planning they allow the defender to perform, as they look only at the deployment and allocation of a fixed set of security resources. This ignores two very important planning problems which concern the strategic design of the security system and resources to deploy as well as the usability and implementation of the security protocols. When these problems appear in real world systems, significant losses in utility and efficiency of security protocols can occur if they are not dealt with in a principled way. To address these limitations, in this thesis I introduce a new hierarchical structure of planning problems for security games, dividing the problem into three levels of planning (i) Strategic Planning, which considers long term planning horizons, and decisions related to game design which constrain the possible defender strategies, (ii) Tactical Planning, which considers shorter term horizons, dealing with the deployment of resources, and selection of defender strategies subject to strategic level constraints and (iii) Operational Planning, dealing with implementation of strategies in real world setting. First, focusing on Strategic Planning, I address the design problem of selecting a set of resource and schedule types. I introduce a new yet fundamental problem, the Simultaneous Optimization of Resource Teams and Tactics (SORT) which models the coupled problem of both strategic and tactical planning, optimizing over both game design with respect to selection of resource types, as well as their deployment actual in the field. I provide algorithms for efficiently solving the SORT problem, which use hierarchical relaxations of the optimization problem to compute these strategic level investment decisions. I show that this more expressive model allows the defender to perform more fine grained decision making that results in significant gains in utility. Second, motivated by the relevance and hardness of security games with resource heterogeneity, I also address challenges in tactical planning by providing a framework for computing adaptive strategies with heterogeneous resources. Lastly, I look at the problem of operational planning, which has never been formally studied in the security game literature. I propose a new solution concept of operationalizable strategies, which randomize over an optimally chosen subset of pure strategies whose cardinality is selected by the defender. I show hardness of computing such operationalizable strategies and provide an algorithm for computing -optimal equilibria which are operationalizable. In all of these problems, I am motivated by real world challenges, and developing solution methods that are usable in the real world. As such, much of this work has been in collaboration with organizations such as Panthera, WWF and other non-governmental organizations (NGOs), to help protect the national parks and wildlife against deforestation and poaching, and the TSA, to protect critical infrastructure such as our airports from terrorist attacks. Because of this, in addressing these three levels of planning, I develop solutions which are not only novel and academically interesting, but also deployable with a real world impact.
2018_3_teamcore_sara_thesis.pdf
Elizabeth Bondi, Debadeepta Dey, Ashish Kapoor, Jim Piavis, Shital Shah, Fei Fang, Bistra Dilkina, Robert Hannaford, Arvind Iyer, Lucas Joppa, and Milind Tambe. 6/20/2018. “AirSim-W: A Simulation Environment for Wildlife Conservation with UAVs.” In In COMPASS ’18: ACM SIGCAS Conference on Computing and Sustainable Societies (COMPASS), June 20–22, 2018, . Menlo Park and San Jose, CA, USA. ACM, New York, NY, USA.Abstract
Increases in poaching levels have led to the use of unmanned aerial vehicles (UAVs or drones) to count animals, locate animals in parks, and even find poachers. Finding poachers is often done at night through the use of long wave thermal infrared cameras mounted on these UAVs. Unfortunately, monitoring the live video stream from the conservation UAVs all night is an arduous task. In order to assist in this monitoring task, new techniques in computer vision have been developed. This work is based on a dataset which took approximately six months to label. However, further improvement in detection and future testing of autonomous flight require not only more labeled training data, but also an environment where algorithms can be safely tested. In order to meet both goals efficiently, we present AirSim-W, a simulation environment that has been designed specifically for the domain of wildlife conservation. This includes (i) creation of an African savanna environment in Unreal Engine, (ii) integration of a new thermal infrared model based on radiometry, (iii) API code expansions to follow objects of interest or fly in zig-zag patterns to generate simulated training data, and (iv) demonstrated detection improvement using simulated data generated by AirSim-W. With these additional simulation features, AirSim-W will be directly useful for wildlife conservation research.
2018_15_teamcore_bondi_camera_ready_airsim_w.pdf
Amulya Yadav. 4/2018. “Artificial Intelligence for Low-Resource Communities: Influence Maximization in an Uncertain World ”.Abstract
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.
2018_16_teamcore_amulya_thesis.pdf
Elizabeth Bondi. 2018. “AI for Conservation: Aerial Monitoring to Learn and Plan Against Illegal Actors .” In International Joint Conference on Artificial Intelligence (IJCAI-18) (Doctoral Consortium).Abstract
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.
2018_10-5_teamcore_0825.pdf
Bryan Wilder and Yevgeniy Vorobeychik. 2018. “Controlling Elections through Social Influence.” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS-18).Abstract
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.
2018_24_teamcore_aamas_elections_final.pdf
Aaron Schlenker, Omkar Thakoor, Haifeng Xu, Fei Fang, Milind Tambe, Long Tran-Thanh, Phebe Vayanos, and Yevgeniy Vorobeychik. 2018. “Deceiving Cyber Adversaries: A Game Theoretic Approach .” In .Abstract
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.
2018_22_teamcore_deceiving_cyber_adversaries.pdf
Mohammad Javad Azizi, Phebe Vayanos, Bryan Wilder, Eric Rice, and Milind Tambe. 2018. “Designing Fair, Efficient, and Interpretable Policies for Prioritizing Homeless Youth for Housing Resources.” In International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research.Abstract
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.
2018_19_teamcore_cpaior_final_designing.pdf
Bryan Wilder. 2018. “Equilibrium Computation and Robust Optimization in Zero Sum Games with Submodular Structure .” In AAAI conference on Artificial Intelligence (AAAI-18).Abstract
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.
2018_31_teamcore_aaai_submodular_games_final.pdf
Kai Wang, Qingyu Guo, Phebe Vayanos, Milind Tambe, and Bo An. 2018. “Equilibrium Refinement in Security Games with Arbitrary Scheduling Constraints .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS-18).Abstract
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.
2018_25_teamcore_equilibrium_refinement_security_0128.pdf
Hau Chan, Eric Rice, Phebe Vayanos, Milind Tambe, and Matthew Morton. 2018. “From Empirical Analysis to Public Policy: Evaluating Housing Systems for Homeless Youth .” In European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD).Abstract
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
2018_7_teamcore_homelessyouthml_ecmlpkdd18.pdf
Han-Ching Ou, Milind Tambe, Bistra Dilkina, and Phebe Vayanos. 2018. “Imbalanced Collusive Security Games .” In Conference on Decision and Game Theory for Security (GameSec).Abstract
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.
2018_6_teamcore_imbalanced_collusive_security_game_cameraready.pdf
Qingyu Guo, Jiarui Gan, Fei Fang, Long Tran-Thanh, Milind Tambe, and Bo An. 2018. “Inducible Equilibrium for Security Games (Extended Abstract) .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS-18) [short paper].Abstract
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.
2018_17_teamcore_inducible_equilibrium_security.pdf
Edward A. Cranford, Christian Lebiere, Cleotilde Gonzalez, Sarah Cooney, Phebe Vayanos, and Milind Tambe. 2018. “Learning about Cyber Deception through Simulations: Predictions of Human Decision Making with Deceptive Signals in Stackelberg Security Games .” In Annual meeting of the Cognitive Science Society (CogSci).Abstract
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.
2018_12_teamcore_cranford_5_14.pdf
Eric Rice, Monique Holguin, Hsun-Ta Hsu, Matthew Morton, Phebe Vayanos, Milind Tambe, and Hau Chan. 2018. “Linking Homelessness Vulnerability Assessments to Housing Placements and Outcomes for Youth .” Cityscape: A Journal of Policy Development and Research, Volume 20, Number 3, 20, 3.Abstract
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.
2018_2_teamcore_ch3.pdf
Elizabeth Bondi, Ashish Kapoor, Debadeepta Dey, James Piavis, Shital Shah, Robert Hannaford, Arvind Iyer, Lucas Joppa, and Milind Tambe. 2018. “Near Real-Time Detection of Poachers from Drones in AirSim .” In International Joint Conference on Artificial Intelligence (IJCAI-18).Abstract
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.
2018_10_teamcore_0847.pdf
Sungyong Seo, Hau Chan, P. Jeffrey Brantingham, Jorja Leap, Phebe Vayanos, Milind Tambe, and Yan Liu. 2018. “Partially Generative Neural Networks for Gang Crime Classification with Partial Information.” In International Conference on AAAI ACM conference on AI, Ethics and Society (AIES).Abstract
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.
2018_20_teamcore_aies_2018_paper_93.pdf
Nitin Kamra, Umang Gupta, Fei Fang, Yan Liu, and Milind Tambe. 2018. “Policy Learning for Continuous Space Security Games using Neural Networks .” In AAAI conference on Artificial Intelligence (AAAI-18).Abstract
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.
2018_34_teamcore_aaai_2018_optgradfp.pdf
Bryan Wilder, Sze-Chuan Suen, and Milind Tambe. 2018. “Preventing Infectious Disease in Dynamic Populations Under Uncertainty .” In AAAI conference on Artificial Intelligence (AAAI-18).Abstract
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.
2018_29_teamcore_aaai_tb_final.pdf
Sara Marie Mc Carthy, Corine M. Laan, Kai Wang, Phebe Vayanos, Arunesh Sinha, and Milind Tambe. 2018. “The Price of Usability: Designing Operationalizable Strategies for Security Games .” In 27th International Joint Conference on Artificial Intelligence (IJCAI).Abstract
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.
2018_13_teamcore_price-of-usability.pdf

Pages