Publications

2011
Manish Jain, Dmytro Korzhyk, Ondrej Vanek, Vincent Conitzer, Michal Pechoucek, and Milind Tambe. 2011. “A Double Oracle Algorithm for Zero-Sum Security Games on Graphs .” In International Conference on Autonomous Agents and Multiagent Systems.Abstract
In response to the Mumbai attacks of 2008, the Mumbai police have started to schedule a limited number of inspection checkpoints on the road network throughout the city. Algorithms for similar security-related scheduling problems have been proposed in recent literature, but security scheduling in networked domains when targets have varying importance remains an open problem at large. In this paper, we cast the network security problem as an attackerdefender zero-sum game. The strategy spaces for both players are exponentially large, so this requires the development of novel, scalable techniques. We first show that existing algorithms for approximate solutions can be arbitrarily bad in general settings. We present RUGGED (Randomization in Urban Graphs by Generating strategies for Enemy and Defender), the first scalable optimal solution technique for such network security games. Our technique is based on a double oracle approach and thus does not require the enumeration of the entire strategy space for either of the players. It scales up to realistic problem sizes, as is shown by our evaluation of maps of southern Mumbai obtained from GIS data.
2011_7_teamcore_666_jain2011b.pdf
Jason Tsai, Emma Bowring, Stacy Marsella, and Milind Tambe. 2011. “Empirical Evaluation of Computational Emotional Contagion Models .” In International Conference on Intelligent Virtual Agents (IVA).Abstract
In social psychology, emotional contagion describes the widely observed phenomenon of one person’s emotions being influenced by surrounding people’s emotions. While the overall effect is agreed upon, the underlying mechanism of the spread of emotions has seen little quantification and application to computational agents despite extensive evidence of its impacts in everyday life. In this paper, we examine computational models of emotional contagion by implementing two models ([2] and [8]) that draw from two separate lines of contagion research: thermodynamics-based and epidemiological-based. We first perform sensitivity tests on each model in an evacuation simulation, ESCAPES, showing both models to be reasonably robust to parameter variations with certain exceptions. We then compare their ability to reproduce a real crowd panic scene in simulation, showing that the thermodynamics-style model ([2]) produces superior results due to the ill-suited contagion mechanism at the core of epidemiological models. We also identify that a graduated effect of fear and proximity-based contagion effects are key to producing the superior results. We then reproduce the methodology on a second video, showing that the same results hold, implying generality of the conclusions reached in the first scene.
2011_33_teamcore_tsai_iva.pdf
Jason Tsai, Natalie Fridman, Emma Bowring, Matthew Brown, Shira Epstein, Gal Kaminka, Stacy Marsella, Andrew Ogden, Inbal Rika, Ankur Sheel, Matthew Taylor, Xuezhi Wang, Avishay Zilka, and Milind Tambe. 2011. “ESCAPES - Evacuation Simulation with Children, Authorities, Parents, Emotions, and Social comparison .” In International Conference on Autonomous Agents and Multiagent Systems.Abstract
In creating an evacuation simulation for training and planning, realistic agents that reproduce known phenomenon are required. Evacuation simulation in the airport domain requires additional features beyond most simulations, including the unique behaviors of firsttime visitors who have incomplete knowledge of the area and families that do not necessarily adhere to often-assumed pedestrian behaviors. Evacuation simulations not customized for the airport domain do not incorporate the factors important to it, leading to inaccuracies when applied to it. In this paper, we describe ESCAPES, a multiagent evacuation simulation tool that incorporates four key features: (i) different agent types; (ii) emotional interactions; (iii) informational interactions; (iv) behavioral interactions. Our simulator reproduces phenomena observed in existing studies on evacuation scenarios and the features we incorporate substantially impact escape time. We use ESCAPES to model the International Terminal at Los Angeles International Airport (LAX) and receive high praise from security officials.
2011_11_teamcore_aamas11_tsai.pdf
Rong Yang, Milind Tambe, Manish Jain, Jun-young Kwak, James Pita, and Zhengyu Yin. 2011. “Game Theory and Human Behavior: Challenges in Security and Sustainability .” In Algorithmic Decision Theory (ADT) .Abstract
Security and sustainability are two critical global challenges that involve the interaction of many intelligent actors. Game theory provides a sound mathematical framework to model such interactions, and computational game theory in particular has a promising role to play in helping to address key aspects of these challenges. Indeed, in the domain of security, we have already taken some encouraging steps by successfully applying game-theoretic algorithms to real-world security problems: our algorithms are in use by agencies such as the US coast guard, the Federal Air Marshals Service, the LAX police and the Transportation Security Administration. While these applications of game-theoretic algorithms have advanced the state of the art, this paper lays out some key challenges as we continue to expand the use of these algorithms in real-world domains. One such challenge in particular is that classical game theory makes a set of assumptions of the players, which may not be consistent with real-world scenarios, especially when humans are involved. To actually model human behavior within game-theoretic framework, it is important to address the new challenges that arise due to the presence of human players: (i) human bounded rationality; (ii) limited observations and imperfect strategy execution; (iii) large action spaces. We present initial solutions to these challenges in context of security games. For sustainability, we lay out our initial efforts and plans, and key challenges related to human behavior in the loop.
2011_35_teamcore_adt11_camera_ready.pdf
James Pita, Milind Tambe, Chris Kiekintveld, Shane Cullen, and Erin Steigerwald. 2011. “GUARDS - Game Theoretic Security Allocation on a National Scale.” In International Conference on Autonomous Agents and Multiagent Systems .Abstract
Building on research previously reported at AAMAS conferences, this paper describes an innovative application of a novel gametheoretic approach for a national scale security deployment. Working with the United States Transportation Security Administration (TSA), we have developed a new application called GUARDS to assist in resource allocation tasks for airport protection at over 400 United States airports. In contrast with previous efforts such as ARMOR and IRIS, which focused on one-off tailored applications and one security activity (e.g. canine patrol or checkpoints) per application, GUARDS faces three key issues: (i) reasoning about hundreds of heterogeneous security activities; (ii) reasoning over diverse potential threats; (iii) developing a system designed for hundreds of end-users. Since a national deployment precludes tailoring to specific airports, our key ideas are: (i) creating a new game-theoretic framework that allows for heterogeneous defender activities and compact modeling of a large number of threats; (ii) developing an efficient solution technique based on general purpose Stackelberg game solvers; (iii) taking a partially centralized approach for knowledge acquisition and development of the system. In doing so we develop a software scheduling assistant, GUARDS, designed to reason over two agents — the TSA and a potential adversary — and allocate the TSA’s limited resources across hundreds of security activities in order to provide protection within airports. The scheduling assistant has been delivered to the TSA and is currently under evaluation and testing for scheduling practices at an undisclosed airport. If successful, the TSA intends to incorporate the system into their unpredictable scheduling practices nationwide. In this paper we discuss the design choices and challenges encountered during the implementation of GUARDS. GUARDS represents promising potential for transitioning years of academic research into a nationally deployed system.
2011_8_teamcore_guards_ind.pdf
James Pita, Milind Tambe, Christopher Kiekintveld, Shane Cullen, and Erin Steigerwald. 2011. “GUARDS - Innovative Application of Game Theory for National Airport Security .” In International Joint Conference on Artificial Intelligence (IJCAI).Abstract
We describe an innovative application of a novel game-theoretic approach for a national scale security deployment. Working with the United States Transportation Security Administration (TSA), we have developed a new application called GUARDS to allocate the TSA’s limited resources across hundreds of security activities to provide protection at over 400 United States airports. Similar security applications (e.g., ARMOR and IRIS) have focused on one-off tailored applications and one security activity (e.g. checkpoints) per application, GUARDS on the other hand faces three new key issues: (i) reasoning about hundreds of heterogeneous security activities; (ii) reasoning over diverse potential threats; (iii) developing a system designed for hundreds of end-users. Since a national deployment precludes tailoring to specific airports, our key ideas are: (i) creating a new game-theoretic framework that allows for heterogeneous defender activities and compact modeling of a large number of threats; (ii) developing an efficient solution technique based on general purpose Stackelberg game solvers; (iii) taking a partially centralized approach for knowledge acquisition. The scheduling assistant has been delivered to the TSA and is currently undergoing evaluation for scheduling practices at an undisclosed airport. If successful, the TSA intends to incorporate the system into their unpredictable scheduling practices nationwide.
2011_22_teamcore_guards_ind2.pdf
Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe, and Richard John. 2011. “Improved Computational Models of Human Behavior in Security Games.” In International Conference on Autonomous Agents and Multiagent Systems (Extended Abstract).Abstract
Security games refer to a special class of attacker-defender Stackelberg games. In these non zero-sum games, the attacker’s utility of attacking a target decreases as the defender allocates more resources to protect it (and vice versa for the defender). The defender (leader) first commits to a mixed strategy, assuming the attacker (follower) decides on a pure strategy after observing the defender’s strategy. This models the situation where an attacker conducts surveillance to learn the defender’s mixed strategy and then launches an attack on a single target. Given that the defender has limited resources, she must design her mixed-strategy optimally against the adversaries’ response to maximize effectiveness. One leading family of algorithms to compute such mixed strategies are DOBSS and its successors [3, 5], which are used in the deployed ARMOR [5] and IRIS [8] applications. One key set of assumptions these systems make is about how attackers choose strategies based on their knowledge of the security strategy. Typically, such systems apply the standard game-theoretic assumption that attackers are perfectly rational. This is a reasonable proxy for the worst case of a highly intelligent attacker, but it can lead to a defense strategy that is not robust against attackers using different decision procedures, and it fails to exploit known weaknesses in human decision-making. Indeed, it is widely accepted that standard game-theoretic assumptions of perfect rationality are not ideal for predicting the behavior of humans in multi-agent decision problems [1]. Thus, integrating more realistic models of human decision-making has become necessary in solving real-world security problems. The current leading contender that accounts for human behavior in security games is COBRA [6], which assumes that adversaries can deviate to −optimal strategies and that they have an anchoring bias when interpreting a probability distribution. It remains an open question whether other models yield better solutions than COBRA against human adversaries. The literature has introduced a multitude of candidate models, but there is an important empirical question of which model best represents the salient features of human behavior in applied security contexts. We address these open questions by developing three new algorithms to generate defender strategies in security games, based on using two fundamental theories of human behavior to predict an attacker’s decision: Prospect Theory (PT) [2] and Quantal Response Equilibrium (QRE) [4]. PT is a noble-prize-winning theory, which describes human decision making as a process of maximizing ‘prospect’. ‘Prospect’ is defined as the weighted sum of the benefit of all possible outcomes for each action. QRE suggests that instead of strictly maximizing utility, individuals respond stochastically in games: the chance of selecting a non-optimal strategy increases as the cost of such an error decreases.
2011_5_teamcore_aamas2011_yang.pdf
Rong Yang, Christopher Kiekintveld, Fernando Ordonez, Milind Tambe, and Richard John. 2011. “Improving Resource Allocation Strategy Against Human Adversaries in Security Games .” In International Joint Conference on Artificial Intelligence (IJCAI) .Abstract
Recent real-world deployments of Stackelberg security games make it critical that we address human adversaries’ bounded rationality in computing optimal strategies. To that end, this paper provides three key contributions: (i) new efficient algorithms for computing optimal strategic solutions using Prospect Theory and Quantal Response Equilibrium; (ii) the most comprehensive experiment to date studying the effectiveness of different models against human subjects for security games; and (iii) new techniques for generating representative payoff structures for behavioral experiments in generic classes of games. Our results with human subjects show that our new techniques outperform the leading contender for modeling human behavior in security games.
2011_23_teamcore_ijcai11_paper148_cameraready.pdf
Marcos A. M. Vieira, Matthew E. Taylor, Prateek Tandon Manish Jain, Ramesh Govindan, Gaurav S. Sukhatme, and Milind Tambe. 2011. “Mitigating Multi-path Fading in a Mobile Mesh Network.” In Ad-Hoc Networks.Abstract
By using robots as routers, a team of networked robots can provide a communication substrate to establish a wireless mesh network. The mobile mesh network can autonomously optimize its configuration, increasing performance. One of the main sources of radio signal fading in such a network is multi-path propagation, which can be mitigated by moving the senders or the receivers on the distance of the order of a wavelength. In this paper, we measure the performance gain when robots are allowed to make such small movements and find that it may be as much as 270%. Our main contribution is the design of a system that allows robots to cooperate and improve the real-world network throughput via a practical solution. We model the problem of which robots to move as a distributed constraint optimization problem (DCOP). Our study includes four local metrics to estimate global throughput.
2011_13_teamcore_adhoc_dcee.pdf
Bo An, Manish Jain, Milind Tambe, and Christopher Kiekintveld. 2011. “Mixed-Initiative Optimization in Security Games: A Preliminary Report.” In AAAI Spring Symposium on Help me help you:Bridging the Gaps in Human-Agent Collaboration.Abstract
Stackelberg games have been widely used to model patrolling or monitoring problems in security. In a Stackelberg security game, the defender commits to a strategy and the adversary makes its decision with knowledge of the leader’s commitment. Algorithms for computing the defender’s optimal strategy are used in deployed decision-support tools in use by the Los Angeles International Airport (LAX), the Federal Air Marshals Service, and the Transportation Security Administration (TSA). Those algorithms take into account various resource usage constraints defined by human users. However, those constraints may lead to poor (even infeasible) solutions due to users’ insufficient information and bounded rationality. A mixed-initiative approach, in which human users and software assistants (agents) collaborate to make security decisions, is needed. Efficient human-agent interaction process leads to models with higher overall solution quality. This paper preliminarily analyzes the needs and challenges for such a mixed-initiative approach.
2011_2_teamcore_aaaiss_boa.pdf
Jason Tsai, Emma Bowring, Stacy Marsella, and Milind Tambe. 2011. “Modeling Emotional Contagion .” In MABS Multiagent-based Simulation Workshop at AAMAS 2011 .Abstract
In social psychology, emotional contagion describes the widely observed phenomenon of one person’s emotions being influenced by surrounding people’s emotions. While the overall effect is agreed upon, the underlying mechanism of the spread of emotions has seen little quantification and application to computational agents. In this paper, we explore computational models of emotional contagion by implementing two models (Bosse et al., Durupinar et al.) and augmenting them to better model real world observations. Our additions include examining the impact of physical proximity and authority figures. We show that these additions provide substantial improvements to the qualitative trends of emotion spreading, more in line with expectations than either of the two previous models. We also evaluate their impact on evacuation safety in an evacuation simulation, ESCAPES, showing substantial differences in predicted safety based on the contagion model.
2011_15_teamcore_mabs2011.pdf
Meritxell Vinyals, Eric Shieh, Jesus Cerquides, Juan Antonio Rodriguez-Aguilar, Zhengyu Yin, Milind Tambe, and Emma Bowring. 2011. “Quality guarantees for region optimal DCOP algorithms .” In International Conference on Autonomous Agents and Multiagent Systems .Abstract
k- and t-optimality algorithms [9, 6] provide solutions to DCOPs that are optimal in regions characterized by its size and distance respectively. Moreover, they provide quality guarantees on their solutions. Here we generalise the k- and t-optimal framework to introduce C-optimality, a flexible framework that provides reward-independent quality guarantees for optima in regions characterised by any arbitrary criterion. Therefore, C-optimality allows us to explore the space of criteria (beyond size and distance) looking for those that lead to better solution qualities. We benefit from this larger space of criteria to propose a new criterion, the socalled size-bounded-distance criterion, which outperforms kand t-optimality.
2011_10_teamcore_aamas_2011_coptimality_bounds.pdf
Manish Jain, Milind Tambe, and Christopher Kiekintveld. 2011. “Quality-bounded Solutions for Finite Bayesian Stackelberg Games: Scaling up .” In International Conference on Autonomous Agents and Multiagent Systems.Abstract
The fastest known algorithm for solving General Bayesian Stackelberg games with a finite set of follower (adversary) types have seen direct practical use at the LAX airport for over 3 years; and currently, an (albeit non-Bayesian) algorithm for solving these games is also being used for scheduling air marshals on limited sectors of international flights by the US Federal Air Marshals Service. These algorithms find optimal randomized security schedules to allocate limited security resources to protect targets. As we scale up to larger domains, including the full set of flights covered by the Federal Air Marshals, it is critical to develop newer algorithms that scale-up significantly beyond the limits of the current state-of-theart of Bayesian Stackelberg solvers. In this paper, we present a novel technique based on a hierarchical decomposition and branch and bound search over the follower type space, which may be applied to different Stackelberg game solvers. We have applied this technique to different solvers, resulting in: (i) A new exact algorithm called HBGS that is orders of magnitude faster than the best known previous Bayesian solver for general Stackelberg games; (ii) A new exact algorithm called HBSA which extends the fastest known previous security game solver towards the Bayesian case; and (iii) Approximation versions of HBGS and HBSA that show significant improvements over these newer algorithms with only 1- 2% sacrifice in the practical solution quality.
2011_4_teamcore_jain2011a.pdf
Bo An, Milind Tambe, Fernando Ordonez, Eric Shieh, and Christopher Kiekintveld. 2011. “Refinement of Strong Stackelberg Equilibria in Security Games .” In Conference on Artificial Intelligence (AAAI).Abstract
Given the real-world deployments of attacker-defender Stackelberg security games, robustness to deviations from expected attacker behaviors has now emerged as a critically important issue. This paper provides four key contributions in this context. First, it identifies a fundamentally problematic aspect of current algorithms for security games. It shows that there are many situations where these algorithms face multiple equilibria, and they arbitrarily select one that may hand the defender a significant disadvantage, particularly if the attacker deviates from its equilibrium strategies due to unknown constraints. Second, for important subclasses of security games, it identifies situations where we will face such multiple equilibria. Third, to address these problematic situations, it presents two equilibrium refinement algorithms that can optimize the defender’s utility if the attacker deviates from equilibrium strategies. Finally, it experimentally illustrates that the refinement approach achieved significant robustness in consideration of attackers’ deviation due to unknown constraints.
2011_25_teamcore_aaai11_yin.pdf
Meritxell Vinyals, Eric Shieh, Jesus Cerquides, Juan Antonio Rodriguez-Aguilar, Zhengyu Yin, Milind Tambe, and Emma Bowring. 2011. “Reward-based region optimal quality guarantees.” In Workshop on Optimisation in Multiagent Systems (OPTMAS) at AAMAS 2011 .Abstract
Distributed constraint optimization (DCOP) is a promising approach to coordination, scheduling and task allocation in multi agent networks. DCOP is NP- hard [6], so an important line of work focuses on developing fast incomplete solution algorithms that can provide guarantees on the quality of their local optimal solutions. Region optimality [11] is a promising approach along this line: it provides quality guarantees for region optimal solutions, namely solutions that are optimal in a specific region of the DCOP. Region optimality generalises k- and t-optimality [7, 4] by allowing to explore the space of criteria that define regions to look for solutions with better quality guarantees. Unfortunately, previous work in region-optimal quality guarantees fail to exploit any a-priori knowledge of the reward structure of the problem. This paper addresses this shortcoming by defining reward-dependent region optimal quality guarantees that exploit two different levels of knowledge about rewards, namely: (i) a ratio between the least minimum reward to the maximum reward among relations; and (ii) the minimum and maximum rewards per relation.
2011_17_teamcore_optmas2011_coptimality.pdf
Zhengyu Yin, Manish Jain, Milind Tambe, and Fernando Ordonez. 2011. “Risk-Averse Strategies for Security Games with Execution and Observational Uncertainty .” In Conference on Artificial Intelligence (AAAI).Abstract
Attacker-defender Stackelberg games have become a popular game-theoretic approach for security with deployments for LAX Police, the FAMS and the TSA. Unfortunately, most of the existing solution approaches do not model two key uncertainties of the real-world: there may be noise in the defender’s execution of the suggested mixed strategy and/or the observations made by an attacker can be noisy. In this paper, we provide a framework to model these uncertainties, and demonstrate that previous strategies perform poorly in such uncertain settings. We also provide RECON, a novel algorithm that computes strategies for the defender that are robust to such uncertainties, and provide heuristics that further improve RECON’s efficiency
2011_26_teamcore_aaai11_yin.pdf
Jun-young Kwak, Rong Yang, Zhengyu Yin, Matthew E. Taylor, and Milind Tambe. 2011. “Robust Execution-time Coordination in DEC-POMDPs Under Model Uncertainty.” In Workshop on Multiagent Sequential Decision Making in Uncertain Domains(MSDM) at AAMAS 2011 .Abstract
Despite their worst-case NEXP-complete planning complexity, DEC-POMDPs remain a popular framework for multiagent teamwork. This paper introduces effective teamwork under model uncertainty (i.e., potentially inaccurate transition and observation functions) as a novel challenge for DEC-POMDPs and presents MODERN, the first execution-centric framework for DEC-POMDPs explicitly motivated by addressing such model uncertainty. MODERN’s shift of coordination reasoning from planning-time to execution-time avoids the high cost of computing optimal plans whose promised quality may not be realized in practice. There are three key ideas in MODERN: (i) it maintains an exponentially smaller model of other agents’ beliefs and actions than in previous work and then further reduces the computationtime and space expense of this model via bounded pruning; (ii) it reduces execution-time computation by exploiting BDI theories of teamwork, and limits communication to key trigger points; and (iii) it limits its decision-theoretic reasoning about communication to trigger points and uses a systematic markup to encourage extra communication at these points – thus reducing uncertainty among team members at trigger points. We empirically show that MODERN is substantially faster than existing DEC-POMDP executioncentric methods while achieving significantly higher reward.
2011_18_teamcore_modern_aamas11_msdm.pdf
Milind Tambe. 2011. “Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned .” Cambridge University Press.Abstract
Global threats of terrorism, drug-smuggling and other crimes have led to a significant increase in research on game theory for security. Game theory provides a sound mathematical approach to deploy limited security resources to maximize their effectiveness. A typical approach is to randomize security schedules to avoid predictability, with the randomization using artificial intelligence techniques to take into account the importance of different targets and potential adversary reactions. This book distills the forefront of this research to provide the first and only study of long-term deployed applications of game theory for security for key organizations such as the Los Angeles International Airport police and the US Federal Air Marshals Service. The author and his research group draw from their extensive experience working with security officials to intelligently allocate limited security resources to protect targets, outlining the applications of these algorithms in research and the real world.
2011_34_teamcore_tambebook.pdf
Zhengyu Yin, Kanna Rajan, and Milind Tambe. 2011. “Solving Continuous-Time Transition-Independent DEC-MDP with Temporal Constraints .” In AAMAS Workshop on Multiagent Sequential Decision Making in Uncertain Domains (MSDM).Abstract
Despite the impact of DEC-MDPs over the past decade, scaling to large problem domains has been difficult to achieve. The scale-up problem is exacerbated in DEC-MDPs with continuous states, which are critical in domains involving time; the latest algorithm (M-DPFP) does not scale-up beyond two agents and a handful of unordered tasks per agent. This paper is focused on meeting this challenge in continuous resource DEC-MDPs with two predominant contributions. First, it introduces a novel continuous time model for multi-agent planning problems that exploits transition independence in domains with graphical agent dependencies and temporal constraints. More importantly, it presents a new, iterative, locally optimal algorithm called SPAC that is a combination of the following key ideas: (1) defining a novel augmented CT-MDP such that solving this singleagent continuous time MDP provably provides an automatic best response to neighboring agents’ policies; (2) fast convolution to efficiently generate such augmented MDPs; (3) new enhanced lazy approximation algorithm to solve these augmented MDPs; (4) intelligent seeding of initial policies in the iterative process; (5) exploiting graph structure of reward dependencies to exploit local interactions for scalability. Our experiments show SPAC not only finds solutions substantially faster than M-DPFP with comparable quality, but also scales well to large teams of agents.
2011_21_teamcore_msdm11_mctmdp.pdf
Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe. 2011. “Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness .” Journal of AI Research (JAIR), 41, Pp. 297-327.Abstract
There has been significant recent interest in game theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model; for example, these games are at the heart of major applications such as the ARMOR program deployed for security at the LAX airport since 2007 and the IRIS program in use by the US Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy. Yet, in many situations, the followers may act without observation of the leader’s strategy, essentially converting the game into a simultaneous-move game model. Previous work fails to address how a leader should compute her strategy given this fundamental uncertainty about the type of game faced. Focusing on the complex games that are directly inspired by real-world security applications, the paper provides four contributions in the context of a general class of security games. First, exploiting the structure of these security games, the paper shows that the Nash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, resolving the leader’s dilemma, it shows that under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibrium strategy; and furthermore, the solution is unique in a class of security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, many of these properties no longer hold. Fourth, we show experimentally that in most (but not all) games where the restriction does not hold, the Stackelberg strategy is still a Nash equilibrium strategy, but this is no longer true when the attacker can attack multiple targets. These contributions have major implications for the real-world applications. As a possible direction for future research on cases where the Stackelberg strategy is not a Nash equilibrium strategy, we propose an extensive-form game model that makes the defender’s uncertainty about the attacker’s ability to observe explicit.
2011_27_teamcore_jair3269_final_version.pdf

Pages