Edward A. Cranford, Cleotilde Gonzalez, Palvi Aggarwal, Sarah Cooney, Milind Tambe, and Christian Lebiere. 2019. “Towards Personalized Deceptive Signaling for Cyber Defense Using Cognitive Models .” In International Conference on Cognitive Modeling (ICCM), 2019.Abstract
Recent research in cybersecurity has begun to develop active defense strategies using game-theoretic optimization of the allocation of limited defenses combined with deceptive signaling. While effective, the algorithms are optimized against perfectly rational adversaries. In a laboratory experiment, we pit humans against the defense algorithm in an online game designed to simulate an insider attack scenario. Humans attack far more often than predicted under perfect rationality. Optimizing against human bounded rationality is vitally important. We propose a cognitive model based on instancebased learning theory and built in ACT-R that accurately predicts human performance and biases in the game. We show that the algorithm does not defend well, largely due to its static nature and lack of adaptation to the particular individual’s actions. Thus, we propose an adaptive method of signaling that uses the cognitive model to trace an individual’s experience in real time, in order to optimize defenses. We discuss the results and implications of personalized defense. Keywords: cyber deception; cognitive models; instance-based learning; knowledge-tracing; model-tracing
Elizabeth Bondi, Hoon Oh, Haifeng Xu, Fei Fang, Bistra Dilkina, and Milind Tambe. 2019. “Using Game Theory in Real Time in the Real World: A Conservation Case Study (Demonstration) .” In International Conference on Autonomous Agents and Multiagent Systems (Demonstration) (AAMAS-19).Abstract
In the real world, real-time data are now widely available, especially in security domains. Security cameras, aerial imagery, and even social media keep defenders informed when protecting important events, locations, and people. Further, advances in artificial intelligence have led to tools that can interpret these data automatically. Game theoretic models, for example, have shown great success in security. However, most of them ignore real-time information. In this paper, we demonstrate the potential to use real-time information from imagery to better inform our decisions in game theoretic models for security. As a concrete example, a conservation group called Air Shepherd uses conservation drones equipped with thermal infrared cameras to locate poachers at night and alert park rangers. They have also used lights aboard the drones, or signaled, to warn poachers of their presence, which often deters the poachers. We propose a system that (i) allocates drones and humans strategically throughout a protected area, (ii) detects poachers in the thermal infrared videos recorded by the conservation drones flying through the protected area in the predetermined location, and (iii) recommends moving to the location and/or signaling to the poacher that a patroller is nearby depending on real-time detections. View the demonstration.
Kai Wang, Aditya Mate, Bryan Wilder, Andrew Perrault, and Milind Tambe. 2019. “Using Graph Convolutional Networks to Learn Interdiction Games .” In AI for Social Good workshop (AI4SG) at International Joint Conference on Artificial Intelligence (IJCAI) 2019.Abstract
Illegal smuggling is one of the most important issues across countries, where more than $10 billion a year of illegal wildlife trafficking is conducted within transnational criminal networks. Governments have tried to deploy inspections at checkpoints to stop illegal smuggling, though the effect is quite limited due to vast protection areas but limited human resources. We study these problems from the perspective of network interdiction games with a boundedly rational attacker. In this paper, we aim to improve the efficiency of the limited number of checkpoints. The problem involves two main stages: i) a predictive stage to predict the attacker’s behavior based on the historical interdiction; ii) a prescriptive stage to optimally allocate limited checkpoints to interdict the attacker. In this paper, we propose a novel boundedly rational model which resolves the issue of exponentially many attacker strategies by making memoryless assumption about the attacker’s behavior. We show that the attacker’s behavior can be reduced to an absorbing Markov chain, where the success probability of reaching any target can be computed analytically, thus optimized via any gradient-based optimization technique. We incorporate graph convolutional neural networks with K-hops look-ahead to model the attacker’s reasoning. Our proposed model provides a new perspective to study the boundedly rationality in traditional interdiction games with graph structure. This novel model possesses nice analytical properties and scales up very well by avoiding enumerating all paths in the graph.
Elizabeth Bondi. 2019. “Visionary Security: Using Uncertain Real-Time Information in Signaling Games .” In International Joint Conference on Artificial Intelligence (IJCAI) 2019 (Doctoral Consortium).Abstract
In important domains from natural resource conservation to public safety, real-time information is becoming increasingly important. Strategic deployment of security cameras and mobile sensors such as drones can provide real-time updates on illegal activities. To help plan for such strategic deployments of sensors and human patrollers, as well as warning signals to ward off adversaries, the defender-attacker security games framework can be used. [Zhang et al., 2019] has shown that real-time data (e.g., human view from a helicopter) may be used in conjunction with security game models to interdict criminals. Other recent work relies on real-time information from sensors that can notify the patroller when an opponent is detected [Basilico et al., 2017; Xu et al., 2018]. Despite considering real-time information in all cases, these works do not consider the combined situation of uncertainty in real-time information in addition to strategically signaling to adversaries. In this thesis, we will not only address this gap, but also improve the overall security result by considering security game models and computer vision algorithms together. A major aspect of this work is in applying it to real-world challenges, such as conservation. Although it applies to many environmental challenges, such as protecting forests and avoiding illegal mining, we will focus particularly on reducing poaching of endangered wildlife as an example. To reduce poaching, human patrollers typically search for snares and poaching activity as they patrol, as well as intervene if poaching activity is found. Drones are useful patrolling aids due to their ability to cover additional ground, but they must interpret their environments, notify nearby human patrollers for intervention, and send potentially deceptive signals to the adversary to deter poaching. Rather than treating these as separate tasks, models must coordinate to handle challenges found in real-world conservation scenarios (Fig. 1). We will determine the success of this work both in simulated experiments and through work with conservation agencies such as Air Shepherd to implement the system in the real world.
Sarah Cooney, Phebe Vayanos, Thanh H. Nguyen, Cleotilde Gonzalez, Christian Lebiere, Edward A. Cranford, and Milind Tambe. 2019. “Warning Time: Optimizing Strategic Signaling for Security Against Boundedly Rational Adversaries.” In International Conference on Autonomous Agents and Multiagent Systems (Extended Abstract) (AAMAS-19).Abstract
Defender-attacker Stackelberg security games (SSGs) have been
applied for solving many real-world security problems. Recent work
in SSGs has incorporated a deceptive signaling scheme into the
SSG model, where the defender strategically reveals information
about her defensive strategy to the attacker, in order to inuence
the attacker’s decision making for the defender’s own benet. In
this work, we study the problem of signaling in security games
against a boundedly rational attacker.
Han-Ching Ou, Arunesh Sinha, Sze-Chuan Suen, Andrew Perrault, and Milind Tambe. 2019. “Who and When to Screen: Multi-Round Active Screening for Recurrent Infectious Diseases Under Uncertainty .” In Joint Workshop on Autonomous Agents for Social Good (AASG) at International Conference on Autonomous Agents and Multiagent Systems (AAMAS-19).Abstract
Controlling recurrent infectious diseases is a vital yet complicated problem. In this paper, we propose a novel active screening
model (ACTS) and algorithms to facilitate active screening for recurrent diseases (no permanent immunity) under infection uncertainty. Our
contributions are: (1) A new approach to modeling multi-round networkbased screening/contact tracing under uncertainty, which is a common
real-life practice in a variety of diseases [10, 30]; (2) Two novel algorithms,
Full- and Fast-REMEDY. Full-REMEDY considers the effect of future actions and finds a policy that provides high solution quality, where
Fast-REMEDY scales linearly in the size of the network; (3) We evaluate
Full- and Fast-REMEDY on several real-world datasets which emulate human contact and find that they control diseases better than the
baselines. To the best of our knowledge, this is the first work on multiround active screening with uncertainty for diseases with no permanent
Bryan Wilder, Eric Ewing, Bistra Dilkina, and Milind Tambe. 2019. “End to End Learning and Optimization on Graphs.” In Advances in Neural and Information Processing Systems (NeurIPS-19), 2019.Abstract
Real-world applications often combine learning and optimization problems on graphs. For instance, our objective may be to cluster the graph in order to detect meaningful communities (or solve other common graph optimization problems such as facility location, maxcut, and so on). However, graphs or related attributes are often only partially observed, introducing learning problems such as link prediction which must be solved prior to optimization. Standard approaches treat learning and optimization entirely separately, while recent machine learning work aims to predict the optimal solution directly from the inputs. Here, we propose an alternative decision-focused learning approach that integrates a differentiable proxy for common graph optimization problems as a layer in learned systems. The main idea is to learn a representation that maps the original optimization problem onto a simpler proxy problem that can be efficiently differentiated through. Experimental results show that our CLUSTERNET system outperforms both pure end-to-end approaches (that directly predict the optimal solution) and standard approaches that entirely separate learning and optimization. Code for our system is available at
Aida Rahmattalabi, Phebe Vayanos, Anthony Fulginiti, Eric Rice, Bryan Wilder, Amulya Yadav, and Milind Tambe. 2019. “Exploring Algorithmic Fairness in Robust Graph Covering Problems.” In . Advances in Neural and Information Processing Systems (NeurIPS-19), 2019.Abstract
Fueled by algorithmic advances, AI algorithms are increasingly being deployed in
settings subject to unanticipated challenges with complex social effects. Motivated
by real-world deployment of AI driven, social-network based suicide prevention
and landslide risk management interventions, this paper focuses on robust graph
covering problems subject to group fairness constraints. We show that, in the
absence of fairness constraints, state-of-the-art algorithms for the robust graph covering problem result in biased node coverage: they tend to discriminate individuals
(nodes) based on membership in traditionally marginalized groups. To mitigate
this issue, we propose a novel formulation of the robust graph covering problem
with group fairness constraints and a tractable approximation scheme applicable to
real-world instances. We provide a formal analysis of the price of group fairness
(PoF) for this problem, where we show that uncertainty can lead to greater PoF. We
demonstrate the effectiveness of our approach on several real-world social networks.
Our method yields competitive node coverage while significantly improving group
fairness relative to state-of-the-art methods.
Aida Rahmattalabi, Anamika Barman Adhikari, Phebe Vayanos, Milind Tambe, Eric Rice, and Robin Baker. 2019. “Social Network Based Substance Abuse Prevention via Network Modification (A Preliminary Study).” In Strategic Reasoning for Societal Challenges (SRSC) Workshop at International Conference on Autonomous Agents and Multiagent Systems (AAMAS-19).Abstract
Substance use and abuse is a significant public health problem in the
United States. Group-based intervention programs offer a promising
means of preventing and reducing substance abuse. While effective,
unfortunately, inappropriate intervention groups can result in an
increase in deviant behaviors among participants, a process known
as deviancy training. This paper investigates the problem of optimizing the social influence related to the deviant behavior via careful
construction of the intervention groups. We propose a Mixed Integer Optimization formulation that decides on the intervention
groups to be formed, captures the impact of the intervention groups
on the structure of the social network, and models the impact of
these changes on behavior propagation. In addition, we propose
a scalable hybrid meta-heuristic algorithm that combines Mixed
Integer Programming and Large Neighborhood Search to find nearoptimal network partitions. Our algorithm is packaged in the form
of GUIDE, an AI-based decision aid that recommends intervention groups. Being the first quantitative decision aid of this kind,
GUIDE is able to assist practitioners, in particular social workers, in
three key areas: (a) GUIDE proposes near-optimal solutions that are
shown, via extensive simulations, to significantly improve over the
traditional qualitative practices for forming intervention groups;
(b) GUIDE is able to identify circumstances when an intervention
will lead to deviancy training, thus saving time, money, and effort;
(c) GUIDE can evaluate current strategies of group formation and
discard strategies that will lead to deviancy training. In developing
GUIDE, we are primarily interested in substance use interventions
among homeless youth as a high risk and vulnerable population.
GUIDE is developed in collaboration with Urban Peak, a homelessyouth serving organization in Denver, CO, and is under preparation
for deployment.
Xinrun Wang, Milind Tambe, Branislav Boˇsansky ́, and Bo An. 2019. “When Players Affect Target Values: Modeling and Solving Dynamic Partially Observable Security Games.” In . Conference on Decision and Game Theory for Security, 2019.Abstract
Most of the current security models assume that the values of targets/areas are static or the changes (if any) are scheduled and
known to the defender. Unfortunately, such models are not sufficient
for many domains, where actions of the players modify the values of
the targets. Examples include wildlife scenarios, where the attacker can
increase value of targets by secretly building supporting facilities. To address such security game domains with player-affected values, we first
propose DPOS3G, a novel partially observable stochastic Stackelberg
game where target values are determined by the players’ actions; the defender can only partially observe these targets’ values, while the attacker
can fully observe the targets’ values and the defender’s strategy. Second,
we propose RITA (Reduced game Iterative Transfer Algorithm), which
is based on the heuristic search value iteration algorithm for partially observable stochastic game (PG-HSVI) and introduces three key novelties:
(a) building a reduced game with only key states (derived from partitioning the state space) to reduce the numbers of states and transitions
considered when solving the game; (b) incrementally adding defender’s
actions to further reduce the number of transitions of the game; (c) providing novel heuristics for lower bound initialization of the algorithm.
Third, we conduct extensive experimental evaluations of the algorithms
and the results show that RITA significantly outperforms the baseline
PG-HSVI algorithm on scalability while allowing for trade off in scalability and solution quality.
Aaron Schlenker. 8/2018. “Game Theoretic Deception and Threat Screening for Cyber Security ”.Abstract

Protecting an organization’s cyber assets from intrusions and breaches due to attacks by malicious actors is an increasingly challenging and complex problem. Companies and organizations (hereon referred to as the defender) who operate enterprise networks employ the use of numerous protection measures to intercept these attacks, such as Intrusion and Detection Systems (IDS) and along with dedicated Cyber Emergency Readiness Teams (CERT) composed of cyber analysts tasked with the general protection of an organization’s cyber assets. In order to optimize the use of the defender’s limited resources and protection mechanisms, we can look to game theory which has been successfully used to handle complex resource allocation problems and has several deployed real-world applications in physical security domains. Applying previous research on security games to cybersecurity domains introduce several novel challenges which I address in my thesis to create models that deceive cyber adversaries and provide the defender with an alert prioritization strategy for IDS. My thesis provides three main contributions to the emerging body of research in using game theory for cyber and physical security , namely (i) the first game theoretic framework for cyber deception of a defender’s network, (ii) the first gametheoretic framework for cyber alert allocation and (iii) algorithms for extending these frameworks to general-sum domains.

In regards to the first contribution, I introduce a novel game model called the Cyber Deception Game (CDG) model which captures the interaction between the defender and adversary during the recon phase of a network attack. The CDG model provides the first game-theoretic framework for deception in cybersecurity and allows the defender to devise deceptive strategies that deceptively alters system responses on the network. I study two different models of cyber adversaries and provide algorithms to solve CDGs that handle the computational complexities stemming from the adversary’s static view of the defender’s network and the varying differences between adversary models. The second major contribution of my thesis is the first game theoretic model for cyber alert prioritization for a network defender. This model, the Cyber-alert Allocation Game, provides an approach which balances intrinsic characteristics of incoming alerts from an IDS with the defender’s analysts that are available to resolve alerts. Additionally, the aforementioned works assume the games are zero-sum which is not true in many real-world domains. As such, the third contribution in my thesis extends CAGs to general-sum domains. I provide scalable algorithms that have additional applicability to other physical screening domains (e.g., container screening, airport passenger screening).

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