Publications

2012
Jason Tsai, Nicholas Weller, and Milind Tambe. 2012. “Analysis of Heuristic Techniques for Controlling Contagion .” In AAAI Fall Symposium.Abstract
Many strategic actions carry a ‘contagious’ component beyond the immediate locale of the effort itself. Viral marketing and peacekeeping operations have both been observed to have a spreading effect. In this work, we use counterinsurgency as our illustrative domain. Defined as the effort to block the spread of support for an insurgency, such operations lack the manpower to defend the entire population and must focus on the opinions of a subset of local leaders. As past researchers of security resource allocation have done, we propose using game theory to develop such policies and model the interconnected network of leaders as a graph. Unlike this past work in security games, actions in these domains possess a probabilistic, non-local impact. To address this new class of security games, recent research has used novel heuristic oracles in a double oracle formulation to generate mixed strategies. However, these heuristic oracles were evaluated only on runtime and quality scaling with the graph size. Given the complexity of the problem, numerous other problem features and metrics must be considered to better inform practical application of such techniques. Thus, this work provides a thorough experimental analysis including variations of the contagion probability average and standard deviation. We extend the previous analysis to also examine the size of the action set constructed in the algorithms and the final mixed strategies themselves. Our results indicate that game instances featuring smaller graphs and low contagion probabilities converge slowly while games with larger graphs and medium contagion probabilities converge most quickly.
2012_40_teamcore_fall_symposium_-_final_submission.pdf
Matthew P. Johnson, Fei Fang, Rong Yang, Milind Tambe, and Heidi Jo Albers. 2012. “Challenges in Patrolling to Maximize Pristine Forest Area (Position Paper) .” In AAAI Spring Symposium on Game Theory for Security, Sustainability and Health.Abstract
Illegal extraction of forest resources is fought, in many developing countries, by patrols through the forest that seek to deter such activity by decreasing its profitability. With limited resources for performing such patrols, a patrol strategy will seek to distribute the patrols throughout the forest, in space and time, in order to minimize the resulting amount of extraction that occurs or maximize the degree of forest protection, according to one of several potential metrics. We pose this problem as a Stackelberg game. We adopt and extend the simple, geometrically elegant model of (Robinson 2010). First, we study optimal allocations of patrol density under generalizations of this model, relaxing several of its assumptions. Second, we pose the problem of generating actual schedules whose site visit frequencies are consistent with the analytically computed optimal patrol densities.
2012_5_teamcore_forest.pdf
Rong Yang, Fernando Ordonez, and Milind Tambe. 2012. “Computing Optimal Strategy against Quantal Response in Security Games .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Abstract
To step beyond the first-generation deployments of attacker-defender security games – for LAX Police, US FAMS and others – it is critical that we relax the assumption of perfect rationality of the human adversary. Indeed, this assumption is a well-accepted limitation of classical game theory and modeling human adversaries’ bounded rationality is critical. To this end, quantal response (QR) has provided very promising results to model human bounded rationality. However, in computing optimal defender strategies in real-world security games against a QR model of attackers, we face difficulties including (1) solving a nonlinear non-convex optimization problem efficiently for massive real-world security games; and (2) addressing constraints on assigning security resources, which adds to the complexity of computing the optimal defender strategy. This paper presents two new algorithms to address these difficulties: GOSAQ can compute the globally optimal defender strategy against a QR model of attackers when there are no resource constraints and gives an efficient heuristic otherwise; PASAQ in turn provides an efficient approximation of the optimal defender strategy with or without resource constraints. These two novel algorithms are based on three key ideas: (i) use of a binary search method to solve the fractional optimization problem efficiently, (ii) construction of a convex optimization problem through a non-linear transformation, (iii) building a piecewise linear approximation of the non-linear terms in the problem. Additional contributions of this paper include proofs of approximation bounds, detailed experimental results showing the advantages of GOSAQ and PASAQ in solution quality over the benchmark algorithm (BRQR) and the efficiency of PASAQ. Given these results, PASAQ is at the heart of the PROTECT system, which is deployed for the US Coast Guard in the port of Boston, and is now headed to other ports.
2012_42_teamcore_aamas2012_paper_cameraready.pdf
Laura Klein, Jun-young Kwak, Geoffrey Kavulya, Farrokh Jazizadeh, Burcin Becerik-Gerber, Pradeep Varakantham, and Milind Tambe. 2012. “Coordinating Occupant Behavior for Building Energy and Comfort Management using Multi-Agent Systems .” Automation in Construction: An International Research Journal, 22, Pp. 525-536.Abstract
There is growing interest in reducing building energy consumption through increased sensor data and increased computational support for building controls. The goal of reduced building energy is often coupled with the desire for improved occupant comfort. Current building systems are inefficient in their energy usage for maintaining occupant comfort as they operate according to fixed schedules and maximum design occupancy assumptions, and they rely on code defined occupant comfort ranges. This paper presents and implements a multi-agent comfort and energy system (MACES) to model alternative management and control of building systems and occupants. MACES specifically improves upon previous multi-agent systems as it coordinates both building system devices and building occupants through direct changes to occupant meeting schedules using multi-objective Markov Decision Problems (MDP). MACES is implemented and tested with input from a real-world building including actual thermal zones, temperatures, occupant preferences, and occupant schedules. The operations of this building are then simulated according to three distinct control strategies involving varying levels of intelligent coordination of devices and occupants. Finally, the energy and comfort results of these three strategies are compared to the baseline and opportunities for further energy savings are assessed. A 12% reduction in energy consumption and a 5% improvement in occupant comfort are realized as compared to the baseline control. Specifically, by employing MDP meeting relocating, an additional 5% improvement in energy consumption is realized over other control strategies.
2012. “Deployed Security Games for Patrol Planning .” In Handbook on Operations Research for Homeland Security.Abstract
Nations and organizations need to secure locations of economic, military, or political importance from groups or individuals that can cause harm. The fact that there are limited security resources prevents complete security coverage, which allows adversaries to observe and exploit patterns in patrolling or monitoring, and enables them to plan attacks that avoid existing patrols. The use of randomized security policies that are more difficult for adversaries to predict and exploit can counter their surveillance capabilities and improve security. In this chapter we describe the recent development of models to assist security forces in randomizing their patrols and their deployment in real applications. The systems deployed are based on fast algorithms for solving large instances of Bayesian Stackelberg games that capture the interaction between security forces and adversaries. Here we describe a generic mathematical formulation of these models, present some of the results that have allowed these systems to be deployed in practice, and outline remaining future challenges. We discuss the deployment of these systems in two real-world security applications: 1) The police at the Los Angeles International Airport uses these models to randomize the placement of checkpoints on roads entering the airport and the routes of canine unit patrols within the airport terminals. 2) The Federal Air Marshal Service uses these models to randomize the schedules of air marshals on international flights.
2012_2_teamcore_patrollingchapter.pdf
Manish Jain, Kevin Leyton-Brown, and Milind Tambe. 2012. “The Deployment-to-Saturation Ratio in Security Games .” In Conference on Artificial Intelligence (AAAI).Abstract
Stackelberg security games form the backbone of systems like ARMOR, IRIS and PROTECT, which are in regular use by the Los Angeles International Police, US Federal Air Marshal Service and the US Coast Guard respectively. An understanding of the runtime required by algorithms that power such systems is critical to furthering the application of game theory to other real-world domains. This paper identifies the concept of the deployment-to-saturation ratio in random Stackelberg security games, and shows that problem instances for which this ratio is 0.5 are computationally harder than instances with other deployment-to-saturation ratios for a wide range of different equilibrium computation methods, including (i) previously published different MIP algorithms, and (ii) different underlying solvers and solution mechanisms. This finding has at least two important implications. First, it is important for new algorithms to be evaluated on the hardest problem instances. We show that this has often not been done in the past, and introduce a publicly available benchmark suite to facilitate such comparisons. Second, we provide evidence that this computationally hard region is also one where optimization would be of most benefit to security agencies, and thus requires significant attention from researchers in this area. Furthermore, we use the concept of phase transitions to better understand this computationally hard region. We define a decision problem related to security games, and show that the probability that this problem has a solution exhibits a phase transition as the deployment-to-saturation ratio crosses 0.5. We also demonstrate that this phase transition is invariant to changes both in the domain and the domain representation, and that the phase transition point corresponds to the computationally hardest instances.
2012_28_teamcore_jain_finalsubmission.pdf
Rong Yang, Fei Fang, Albert Xin Jiang, Karthik Rajagopal, Milind Tambe, and Rajiv Maheswaran. 2012. “Designing Better Strategies against Human Adversaries in Network Security Games: Extended Abstract .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS)(Short paper) .Abstract
In a Network Security Game (NSG), security agencies must allocate limited resources to protect targets embedded in a network, such as important buildings in a city road network. A recent line of work relaxed the perfect-rationality assumption of human adversary and showed significant advantages of incorporating the bounded rationality adversary models in non-networked security domains. Given that real-world NSG are often extremely complex and hence very difficult for humans to solve, it is critical that we address human bounded rationality when designing defender strategies. To that end, the key contributions of this paper include: (i) comprehensive experiments with human subjects using a web-based game that we designed to simulate NSGs; (ii) new behavioral models of human adversary in NSGs, which we train with the data collected from human experiments; (iii) new algorithms for computing the defender optimal strategy against the new models.
2012_15_teamcore_aamas2012_gsg.pdf
Matthew P Johnson, Fei Fang, Milind Tambe, and H. J. Albers. 2012. “Designing Patrol Strategies to Maximize Pristine Forest Area .” In Workshop on Optimization in Multiagent Systems (OPTMAS) at AAMAS .Abstract
Illegal extraction of forest resources is fought, in many developing countries, by patrols that seek to deter such activity by decreasing its profitability. With a limited budget, a patrol strategy will seek to distribute the patrols throughout the forest, in order to minimize the resulting amount of extraction that occurs or maximize the amount of “pristine” forest area. Prior work in forest economics has posed this problem as a Stackelberg game, but efficient optimal or approximation algorithms for generating leader strategies have not previously been found. Unlike previous work on Stackelberg games in the multiagent literature, much of it motivated by counter-terrorism, here we seek to protect a continuous area, as much as possible, from extraction by an indeterminate number of followers. The continuous nature of this problem setting leads to new challenges and solutions, very different in character from in the discrete Stackelberg settings previously studied. In this paper, we give an optimal patrol allocation algorithm and a guaranteed approximation algorithm, the latter of which is more efficient and yields simpler, more practical patrol allocations. In our experimental investigations, we find that these algorithms perform significantly better—yielding a larger pristine area—than naive patrol allocations.
2012_34_teamcore_forestoptmas2012_cameraready.pdf
Bostjan Kaluza, Gal Kaminka, and Milind Tambe. 2012. “Detection of Suspicious Behavior from a Sparse Set of Multiagent Interactions .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) .Abstract
In many multiagent domains, no single observation event is sufficient to determine that the behavior of individuals is suspicious. Instead, suspiciousness must be inferred from a combination of multiple events, where events refer to the individual’s interactions with other individuals. Hence, a detection system must employ a detector that combines evidence from multiple events, in contrast to most previous work, which focuses on the detection of a single, clearly suspicious event. This paper proposes a two-step detection system, where it first detects trigger events from multiagent interactions, and then combines the evidence to provide a degree of suspicion. The paper provides three key contributions: (i) proposes a novel detector that generalizes a utility-based plan recognition with arbitrary utility functions, (ii) specifies conditions that any reasonable detector should satisfy, and (iii) analyzes three detectors and compares them with the proposed approach. The results on a simulated airport domain and a dangerous-driver domain show that our new algorithm outperforms other approaches in several settings.
2012_18_teamcore_paper-aamas2012.cr_.pdf
Jason Tsai, Emma Bowring, Stacy Marsella, Wendy Wood, and Milind Tambe. 2012. “Emotional Contagion with Virtual Characters: Extended Abstract .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS)(Short paper).Abstract
In social psychology, emotional contagion describes the widely observed phenomenon of one person’s emotions mimicking surrounding people’s emotions [8]. While it has been observed in humanhuman interactions, no known studies have examined its existence in agent-human interactions. As virtual characters make their way into high-risk, high-impact applications such as psychotherapy and military training with increasing frequency, the emotional impact of the agents’ expressions must be accurately understood to avoid undesirable repercussions.
2012_16_teamcore_ec-shortpaper.pdf
Milind Tambe and Bo An. 2012. “Game Theory for Security: A Real-World Challenge Problem for Multiagent Systems and Beyond .” In AAAI Spring Symposium on Game Theory for Security, Sustainability and Health.Abstract
The goal of this paper is to introduce a real-world challenge problem for researchers in multiagent systems and beyond, where our collective efforts may have a significant impact on activities in the real-world. The challenge is in applying game theory for security: Our goal is not only to introduce the problem, but also to provide exemplars of initial successes of deployed systems in this challenge problem arena, some key open research challenges and pointers to getting started in this research.
2012_4_teamcore_aaaiss12challenge.pdf
Bo An and Milind Tambe. 2012. “Game Theory for Security: An Important Challenge for Multiagent Systems .” In European Workshop on Multiagent Systems (EUMAS) 2011 workshop (Invited) .Abstract
The goal of this paper is to introduce a real-world challenge problem for researchers in multiagent systems and beyond, where our collective efforts may have a significant impact on activities in the real-world. The challenge is in applying game theory for security: Our goal is not only to introduce the problem, but also to provide exemplars of initial successes of deployed systems in this challenge problem arena, some key open research challenges and pointers to getting started in this research.
2012_24_teamcore_eumas.pdf
Milind Tambe, Manish Jain, James Adam Pita, and Albert Xin Jiang. 2012. “Game Theory for Security: Key Algorithmic Principles, Deployed Systems, Lessons Learned.” In 50th Annual Allerton Conference on Communication, Control, and Computing .Abstract
Security is a critical concern around the world. In many security domains, limited security resources prevent full security coverage at all times; instead, these limited resources must be scheduled, avoiding schedule predictability, while simultaneously taking into account different target priorities, the responses of the adversaries to the security posture and potential uncertainty over adversary types. Computational game theory can help design such unpredictable security schedules. Indeed, casting the problem as a Bayesian Stackelberg game, we have developed new algorithms that are now deployed over multiple years in multiple applications for security scheduling. These applications are leading to real-world use-inspired research in the emerging research area of “security games”; specifically, the research challenges posed by these applications include scaling up security games to largescale problems, handling significant adversarial uncertainty, dealing with bounded rationality of human adversaries, and other interdisciplinary challenges.
2012_43_teamcore_allerton.pdf
Ondrej Vanek, Zhengyu Yin, Manish Jain, Branislav Bosansky, Milind Tambe, and Michal Pechoucek. 2012. “Game-theoretic Resource Allocation for Malicious Packet Detection in Computer Networks .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) .Abstract
We study the problem of optimal resource allocation for packet selection and inspection to detect potential threats in large computer networks with multiple valuable computers of differing importance. An attacker tries to harm these targets by sending malicious packets from multiple entry points of the network; the defender thus needs to optimally allocate his resources to maximize the probability of malicious packet detection under network latency constraints. We formulate the problem as a graph-based security game with multiple resources of heterogeneous capabilities and propose a mathematical program for finding optimal solutions. Due to the very limited scalability caused by the large attacker’s strategy space and non-linearity of the program, we investigate solutions with approximated utility function and propose Grande, a novel polynomial approximate algorithm utilizing submodularity of the problem able to find solutions with a bounded error on problem of a realistic size.
2012_14_teamcore_gt-approach-to-net-sec.pdf
Jason Tsai, Thanh H. Nguyen, and Milind Tambe. 2012. “Game-Theoretic Target Selection in Contagion-based Domains .” In Workshop on Optimization in Multiagent Systems (OPTMAS) at AAMAS .Abstract
Many strategic actions carry a ‘contagious’ component beyond the immediate locale of the effort itself. Viral marketing and peacekeeping operations have both been observed to have a spreading effect. In this work, we use counterinsurgency as our illustrative domain. Defined as the effort to block the spread of support for an insurgency, such operations lack the manpower to defend the entire population and must focus on the opinions of a subset of local leaders. As past researchers of security resource allocation have done, we propose using game theory to develop such policies and model the interconnected network of leaders as a graph. Unlike this past work in security games, actions in these domains possess a probabilistic, non-local impact. To address this new class of security games, we combine recent research in influence blocking maximization with a double oracle approach and create novel heuristic oracles to generate mixed strategies for a real-world leadership network from Afghanistan, synthetic leadership networks, and scale-free graphs. We find that leadership networks that exhibit highly interconnected clusters can be solved equally well by our heuristic methods, but our more sophisticated heuristics outperform simpler ones in less interconnected scale-free graphs.
2012_33_teamcore_infblock2.pdf
James Pita. 2012. “The Human Element: Addressing Human Adversaries in Security Domains ”.Abstract
Recently, game theory has been shown to be useful for reasoning about real-world security settings where security forces must protect critical assets from potential adversaries. In fact, there have been a number of deployed real-world applications of game theory for security (e.g., ARMOR at Los Angeles International Airport and IRIS for the Federal Air Marshals Service). Here, the objective is for the security force to utilize its limited resources to best defend their critical assets. An important factor in these real-world security settings is that the adversaries involved are humans who may not behave according to the standard assumptions of game-theoretic models. There are two key shortcomings of the approaches currently employed in these recent applications. First, human adversaries may not make the predicted rational decision. In such situations, where the security force has optimized against a perfectly rational opponent, a deviation by the human adversary can lead to adverse affects on the security force’s predicted outcome. Second, human adversaries are naturally creative and security domains are highly dynamic, making enumeration of all potential threats a practically impossible task and solving the resulting game, with current leading approaches, would be intractable. My thesis contributes to a very new area that combines algorithmic and experimental gametheory. Indeed, it examines a critical problem in applying game-theoretic techniques to situations where perfectly rational solvers must address human adversaries. In doing so it advances the study and reach of game theory to domains where software agents and humans may interact. More specifically, to address the first shortcoming, my thesis presents two separate algorithms to address potential deviations from the predicted rational decision by human adversaries. Experimental results, from a simulation that is motivated by a real-world security domain at Los Angeles International airport, demonstrated that both of my approaches outperform the currently deployed optimal algorithms which utilize standard game-theoretic assumptions and additional alternative algorithms against humans. In fact, one of my approaches is currently under evaluation in a real-world application to aid in resource allocation decisions for the United States Coast Guard. Towards addressing the second shortcoming of enumeration of a large number of potential adversary threat capabilities, I introduce a new game-theoretic model for efficiency, which additionally generalizes the previously accepted model for security domains. This new game-theoretic model for addressing human threat capabilities has seen real-world deployment and is under evaluation to aid the United States Transportation Security Administration in their resource allocation challenges.
2012_44_teamcore_james_phd_thesis.pdf
Farrokh Jazizadeha, Geoffrey Kavulyaa, Jun-young Kwak, Burcin Becerik-Gerber, Milind Tambe, and Wendy Wood. 2012. “Human-Building Interaction for Energy Conservation in Office Buildings.” In Construction Research Congress .Abstract
Buildings are one of the major consumers of energy in the U.S. Both commercial and residential buildings account for about 42% of the national U.S. energy consumption. The majority of commercial buildings energy consumption is attributed to lighting (25%), space heating and cooling (25%), and ventilation (7%). Several research studies and industrial developments have focused on energy management based on maximum occupancy. However, fewer studies, with the objective of energy savings, have considered human preferences. This research focuses on office buildings’ occupants’ preferences and their contribution to the building energy conservation. Accordingly, occupants of selected university campus offices were asked to reduce lighting levels in their offices during work hours. Different types of information regarding their energy consumption were provided to the occupants. Email messages were used to communicate with the occupants. To monitor behavioral changes during the study, the test bed offices were equipped with wireless light sensors. The deployed light sensors were capable of detecting variations in light intensity, which was correlated with energy consumption. The impact of different types of information on occupant’s energy related behavior is presented.
2012_36_teamcore_crc_final_paper.pdf
Rong Yang, Fei Fang, Albert Xin Jiang, Karthik Rajagopal, Milind Tambe, and Rajiv Maheswaran. 2012. “Modeling Human Bounded Rationality to Improve Defender Strategies in Network Security Games .” In Workshop on Human-Agent Interaction Design and Models (HAIDM) at AAMAS .Abstract
In a Network Security Game (NSG), security agencies must allocate limited resources to protect targets embedded in a network, such as important buildings in a city road network. A recent line of work relaxed the perfectrationality assumption of human adversary and showed significant advantages of incorporating the bounded rationality adversary models in non-networked security domains. Given that real-world NSG are often extremely complex and hence very difficult for humans to solve, it is critical that we address human bounded rationality when designing defender strategies. To that end, the key contributions of this paper include: (i) comprehensive experiments with human subjects using a web-based game that we designed to simulate NSGs; (ii) new behavioral models of human adversary in NSGs, which we train with the data collected from human experiments; (iii) new algorithms for computing the defender optimal strategy against the new models.
2012_32_teamcore_paper_6_haidm.pdf
Matthew Brown, Bo An, Christopher Kiekintveld, Fernando Ordonez, and Milind Tambe. 2012. “Multi-Objective Optimization for Security Games .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) .Abstract
The burgeoning area of security games has focused on real-world domains where security agencies protect critical infrastructure from a diverse set of adaptive adversaries. There are security domains where the payoffs for preventing the different types of adversaries may take different forms (seized money, reduced crime, saved lives, etc) which are not readily comparable. Thus, it can be difficult to know how to weigh the different payoffs when deciding on a security strategy. To address the challenges of these domains, we propose a fundamentally different solution concept, multi-objective security games (MOSG), which combines security games and multiobjective optimization. Instead of a single optimal solution, MOSGs have a set of Pareto optimal (non-dominated) solutions referred to as the Pareto frontier. The Pareto frontier can be generated by solving a sequence of constrained single-objective optimization problems (CSOP), where one objective is selected to be maximized while lower bounds are specified for the other objectives. Our contributions include: (i) an algorithm, Iterative -Constraints, for generating the sequence of CSOPs; (ii) an exact approach for solving an MILP formulation of a CSOP (which also applies to multi-objective optimization in more general Stackelberg games); (iii) heuristics that achieve speedup by exploiting the structure of security games to further constrain a CSOP; (iv) an approximate approach for solving an algorithmic formulation of a CSOP, increasing the scalability of our approach with quality guarantees. Additional contributions of this paper include proofs on the level of approximation and detailed experimental evaluation of the proposed approaches.
2012_19_teamcore_aamas2012multi_camerareadyfinal3.pdf
Matthew Brown, Bo An, Christopher Kiekintveld, Fernando Ordonez, and Milind Tambe. 2012. “Multi-Objective Optimization for Security Games .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) .Abstract
The burgeoning area of security games has focused on real-world domains where security agencies protect critical infrastructure from a diverse set of adaptive adversaries. There are security domains where the payoffs for preventing the different types of adversaries may take different forms (seized money, reduced crime, saved lives, etc) which are not readily comparable. Thus, it can be difficult to know how to weigh the different payoffs when deciding on a security strategy. To address the challenges of these domains, we propose a fundamentally different solution concept, multi-objective security games (MOSG), which combines security games and multiobjective optimization. Instead of a single optimal solution, MOSGs have a set of Pareto optimal (non-dominated) solutions referred to as the Pareto frontier. The Pareto frontier can be generated by solving a sequence of constrained single-objective optimization problems (CSOP), where one objective is selected to be maximized while lower bounds are specified for the other objectives. Our contributions include: (i) an algorithm, Iterative -Constraints, for generating the sequence of CSOPs; (ii) an exact approach for solving an MILP formulation of a CSOP (which also applies to multi-objective optimization in more general Stackelberg games); (iii) heuristics that achieve speedup by exploiting the structure of security games to further constrain a CSOP; (iv) an approximate approach for solving an algorithmic formulation of a CSOP, increasing the scalability of our approach with quality guarantees. Additional contributions of this paper include proofs on the level of approximation and detailed experimental evaluation of the proposed approaches.
2012_17_teamcore_aamas2012multifinal2.pdf

Pages