DIMACS/CCICADA Workshop on Adversarial Decision Making

September 30 - October 1, 2010
DIMACS Center, CoRE Building, Rutgers University

David Banks, Duke University, banks at stat.duke.edu
Janusz Marecki, IBM T.J. Watson Research, marecki at us.ibm.com
Bonnie Ray, IBM T.J. Watson Research, bonnier at us.ibm.com
Milind Tambe, University of Southern California, tambe at usc.edu
Presented under the auspices of the Special Focus on Algorithmic Decision Theory and The Homeland Security Center for Command, Control, and Interoperability Center for Advanced Data Analysis (CCICADA).


David Banks, Duke University

Title: Bayesian Borel Games

To perform adversarial risk analysis, we use Bayesian methods to mirror the decision processes of an opponent. This talk describes the analysis of La Relance, a simple gambling scenario invened by Emil Borel that has long been studied in classical game theory. We find interestingly different results from standard methods, and note the mathematics is easier and more generalizable than can be obtained in using traditional solution concepts.

Vicki Bier, University of Wisconsin

Title: Quantifying unobserved attributes in expert elicitation of terrorist preferences

We discuss how to construct a reasonable defender prior distribution over possible terrorist preferences, by explicitly modeling the defender's uncertainty about unobserved attributes (i.e., target attributes that may be important to the terrorist, but are unknown or unobserved by the defender). In particular, in our proposed model, a centralized decision maker assumes that the terrorist evaluates target attractiveness according to a multi-attribute utility function, with an error term representing the effect of any unobserved attributes. The ratings of the various targets on the unobserved attributes are modeled as independent, identically distributed (IID) random variables, since the decision maker presumably has no basis for anticipating which targets would be considered more attractive on the unobserved attributes. The importance assigned by the decision maker to the unobserved attributes can be represented by a multiplier or weight (which could itself be treated as a random variable), and/or by the breadth of the distributions of the IID random variables; for example, if the known attributes account for only a small fraction of the variability in target attractiveness, that could be represented either by a large multiplier, or by broad distributions for the target ratings on the unobserved attributes. To estimate the parameters of this model, multiple experts are asked to rank the set of potential targets in terms of their attractiveness to the terrorist. The decision maker can then make inferences both about the weights of the various known attributes, and about the importance of the unobserved attributes, using either probabilistic inversion or Bayesian density estimation. This process not only gives rise to reasonable prior distributions for terrorist attribute weights (as assessed, for example, using pre-posterior analysis), even in the face of conflicting or inconsistent expert opinions, but can also be used as a basis for inferences about what some of the unobserved attributes might be. For example, if Los Angeles, Las Vegas, and Orlando are all rated more highly by many experts than their known attribute values would suggest, that might indicate that presence of a large entertainment industry could be one of the terrorist's unknown attributes.

Matt Carlyle, Naval Postgraduate School

Title: Game-Theoretic Models and Solution Algorithms for Critical Infrastructure Protection

We present zero-sum max-min and min-max-min formulations of critical infrastructure protection games in which an infrastructure system operator (the defender) wishes to protect his system from deliberate attacks from an intelligent adversary. We then discuss solution algorithms based on Benders decomposition for solving these complex optimization models, and discuss how they perform on models of real-world infrastructure systems including the San Francisco Bay Area bridges and highway system and electrical power distribution systems. We find that these algorithms scale well with the size of the infrastructure system being studied, but that increasing the number of discrete simultaneous attacks that can be mounted (or discrete components that can be defended) leads to very complex decision problems.

Nicolas Christin, Carnegie Mellon University

Title: Secure or Insure? A Game-Theoretic Analysis of Information Security Games

Security interactions in networked systems, and the associated user choices, due to their complexity, are notoriously difficult to predict, and sometimes even harder to rationalize. We argue that users often underestimate the strong mutual dependence between their security strategies and the economic environment (e.g., threat model) in which these choices are made and evaluated. This misunderstanding weakens the effectiveness of users' security investments. We study how economic agents invest into security in different economic environments, which are characteristic of different threat models. We notably explore Nash equilibrium predictions for the environments considered, contrast them with social optima, and discuss the impact of limited information on the outcome of these games.

Vincent Conitzer, Duke University

Title: Finding Optimal Mixed Strategies to Commit to in Security Games

Game theory considers how a rational agent should act in the presence of other rational agents. This is tricky because the optimal action for each agent in general depends on what the other agents do. Various algorithms have been developed for computing game-theoretic solutions, and in recent years such algorithms have started to find new applications in real-world security domains, such as the random placement of checkpoints at LAX. I will focus on computing optimal mixed strategies to commit to (Stackelberg strategies), both in unrestricted games and in security games specifically.

Seth Guikema, The John Hopkins University

Title: Resource Allocation for Homeland Defense: Dealing With the Team Effect

The federal government's allocation of resources for defence against potential attacks generally involves depending on a multi-tiered organization consisting of federal, state, and local agencies for information on the risks faced in their jurisdictions and the costs and benefits of defensive actions they may take. These agencies then receive resources based on the collectively reported risks and resource needs. With private information about local risks and defensive actions and limited resources at the federal level, there are ample opportunities for agencies to take advantage of such a system for their benefit. This yields a sub-optimal allocation of limited defensive resources. In this paper we describe this allocation problem formally as a game between a single principle (Congress) and an agent representing a more local agency. This differs substantially from the treatment of the attacker-defender problem in the literature where the defender is treated as a single, united decision-maker. We show that ignoring the within team defender interactions in modeling the attacker-defender game leads to a sub-optimal resource allocation. Existing results from agency theory are applied to this problem together with new results and insights into the interactions between an attacker and a multi-level defender.

Christopher Kiekintveld, Milend Tambe, and Janusz Marecki, University of Southern California and IBM Research

Title: Game Theory for Homeland Security Applications

In this talk I will present recent work on game-theoretic models and algorithms for scheduling limited security resources to protect critical infrastructure. A key challenge is to make the schedule unpredictable so that adversaries cannot exploit patterns in the deployment, without sacrificing the level of protection provided by the schedule. I will focus on algorithms for finding optimal scheduling policies using game-theoretic models of the security domain, including factors such as differing target values and scheduling constraints. Unfortunately, existing solution methods are severely limited and can only solve small instances of these security games. I will present new algorithms that are able to solve dramatically larger and more complex problem instances. In addition to scalable algorithms, my work also encompasses modeling improvements such as payoff uncertainty and varying assumptions about the attacker's surveillance capabilities. This research is driven by the requirements of two real-world software systems (IRIS and GUARDS) developed for the Federal Air Marshals Service (FAMS) and Transportation Security Administration (TSA). IRIS is designed to schedule air marshals on flights, and has been used by FAMS to schedule a limited number of flights since October 2009. The GUARDS system randomizes a wide variety of TSA operations in airports, and is currently being evaluated by the Pittsburgh and Los Angeles airports for nationwide deployment.

Jason Merrick, Operations Research Dept., Virginia Commonwealth University

Title: A Comparative Analysis of PRA and Intelligent Adversary Methods for Counterterrorism Risk Management

In counter-terrorism risk management decisions, the analyst can choose to represent terrorist decisions as defender uncertainties or as attacker decisions. We perform a comparative analysis of probabilistic risk analysis (PRA) methods including event trees, influence diagrams, Bayesian networks, decision trees, game theory, and combined methods on the same illustrative examples (container screening for radiological materials) to get insights into the significant differences in assumptions and results. A key tenant of PRA and decision analysis is the use of subjective probability to assess the likelihood of possible outcomes. For each technique, we compare the assumptions, probability assessment requirements, risk levels, and potential insights for risk managers. We conclude with insights for risk assessment, risk communications, and risk management.

Laura Pontiggia, University of the Sciences, Philadelphia

Title: Two-Person and n-Person Red and Black Games

I consider a class of games introduced by Dubins and Savage (1976). Imagine there are players who are engaged in a game played in stages, where they all aim to reach a goal fortune g by betting at each stage an integral amount not greater than their current fortune. The player's probability of winning at each stage is a function of the players' bets. The problem for each player is to decide how many units of his current fortune should be staked at each stage in order to maximize his probability of reaching the goal g. I will show the Nash Equilibrium for several versions of two-person and n-person red-and-black games and for some of them I will prove uniqueness. In this class of games the payoff function for each player is given by an indicator function, which takes value 1 if the player reaches his goal and 0 otherwise. Hence, this family of games can be considered as a particular instance of the more general class of "reaching-a-set" games for which, at this time, there are no general results about the existence of Nash Equilibria. I also discuss Bayesian methods for this problem.

Jesus Rios, University of Manchester and IBM Research

Title: Adversarial Risk Analysis for Counterterrorism Modeling

Recent large scale terrorist attacks have raised interest in counterterrorism models. A unifying theme in this research area is the need to develop methods for the analysis of decisions when there are intelligent adversaries aiming at increasing our risks. Most of the approaches have a clear game theoretic flavor, although there are also some decision analytic based approaches. Based on a recently introduced framework for adversarial risk analysis, aimed at dealing with decision making problems with intelligent opponents and uncertain outcomes, I explore in the talk how this framework may cope with several standard counterterrorism models: simultaneous defend-attack models, defend-attack-defend models and sequential defend-attack models with private information. I will also explore how these basic models may be used as basic building blocks for more complex counterterrorism problems.

Erroll Southers, University of Southern California

Title: The Emerging Threat; Ten years ago, al-Qaeda said this is where they wanted to be.

There are a growing number of Americans who grow up experiencing the benefits of freedom, yet choose to become radical Islamists bent on destroying property, killing Americans and if necessary, dying in the process. This particular brand of terrorist poses unique threats. They are U.S. citizens. They are harder to identify. They represent the nightmare threat scenario. Recent terrorism events have magnified a critical question. How can we do a more effective job of identifying and capturing these terrorists before they strike? This presentation will illustrate our increasing understanding of the social networking aspects of terrorist planning and how to exploit opportunities for disruption. How does this evolve and what are the associated suspicious activities? Our ability to identify and connect the dots is critical to reducing the transnational threat of terrorism Recent successful operations abroad would suggest something in the intelligence community is clearly working. Is it possible to facilitate even greater success, as it relates to locating these elusive, high-value Americans living among us? Can we improve our ability to connect the dots and what is your role in responding to this emerging threat?

Mudhakar Srivatsa, IBM Research

Title: Trust-based Decision-Making with Uncertain Information

Decision makers (humans or software agents alike) are faced with the challenge of examining large volumes of information originating from heterogeneous sources with the goal of ascertaining trust in various pieces of information. In this paper we argue (using examples) that traditional trust models are limited in their data model by assuming a pair-wise numeric rating between two entities (e.g., eBay recommendations, Netflix movie rating, etc). We present a novel trust computational model for rich, complex and uncertain information encoded using Bayesian Description Logics. We present security and scalability tradeoffs that arise in the new model, and the results of an evaluation of the first prototype implementation under a variety attack scenarios.

Previous: Program
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on July 22, 2010.