2013
Jason Tsai. 2013. “
Protecting Networks Against Diffusive Attacks: Game-Theoretic Resource Allocation for Contagion Mitigation ”.
AbstractMany real-world situations involve attempts to spread influence through a social network. For
example, viral marketing is when a marketer selects a few people to receive some initial advertisement in the hopes that these ‘seeds’ will spread the news. Even peacekeeping operations
in one area have been shown to have a contagious effect on the neighboring vicinity. Each of
these domains also features multiple parties seeking to maximize or mitigate a contagious effect
by spreading its own influence among a select few seeds, naturally yielding an adversarial resource allocation problem. My work models the interconnected network of people as a graph and
develops algorithms to optimize resource allocation in these networked competitive contagion
scenarios.
Game-theoretic resource allocation in the past has not considered domains with both a networked structure and contagion effects, rendering them unusable in critical domains such as rumor control, counterinsurgency, and crowd management. Networked domains without contagion
effects already present computational challenges due to the large scale of the action space. To
address this issue, my first contribution proposed efficient game-theoretic allocation algorithms
for the graph-based urban road network domain. This work still provides the only polynomialtime algorithm for allocating vehicle checkpoints through a city, giving law enforcement officers
an efficient tool to combat terrorists making their way to potential points of attack. Second, I have provided the first game-theoretic treatment for contagion mitigation in social networks and
given practitioners the first principled techniques for such vital concerns as rumor control and
counterinsurgency. Finally, I extended my work on game-theoretic contagion mitigation to address uncertainty about the network structure to find that, contrary to what evidence and intuition
suggest, heuristic sampling approaches provide near-optimal solutions across a wide range of
generative graph models and uncertainty models. Thus, despite extreme practical challenges in
attaining accurate social network information, my techniques remain near-optimal across numerous forms of uncertainty in multiple synthetic and real-world graph structures.
Beyond optimization of resource allocation, I have further studied contagion effects to understand the effectiveness of such resources. First, I created an evacuation simulation, ESCAPES,
to explore the interaction of pedestrian fear contagion and authority fear mitigation during an
evacuation. Second, using this simulator, I have advanced the frontier in contagion modeling
by developing empirical evaluation methods for comparing and calibrating computational contagion models that are critical in crowd simulations and evacuation modeling. Finally, I have
also conducted an examination of agent-human emotional contagion to inform the rising use of
simulations for personnel training in emotionally-charged situations.
2013_24_teamcore_jasontsai-dissertation.pdf Nupul Kukreja, William G. J. Halfond, and Milind Tambe. 2013. “
Randomizing Regression Tests using Game Theory .” In International conference on Automated Software Engineering (ASE).
AbstractAs software evolves, the number of test-cases in the
regression test suites continues to increase, requiring testers to
prioritize their execution. Usually only a subset of the test cases
is executed due to limited testing resources. This subset is often
known to the developers who may try to “game” the system by
committing insufficiently tested code for parts of the software
that will not be tested. In this new ideas paper, we propose a
novel approach for randomizing regression test scheduling, based
on Stackelberg games for deployment of scarce resources. We
apply this approach to randomizing test cases in such a way
as to maximize the testers’ expected payoff when executing the
test cases. Our approach accounts for resource limitations (e.g.,
number of testers) and provides a probabilistic distribution for
scheduling test cases. We provide an example application of our
approach showcasing the idea of using Stackelberg games for
randomized regression test scheduling.
2013_32_teamcore_ase.pdf Rong Yang, Albert Xin Jiang, Milind Tambe, and Fernando Ordo´nez. 2013. “
Scaling-up Security Games with Boundedly Rational Adversaries: A Cutting-plane Approach .” In International Joint Conference on Artificial Intelligence (IJCAI).
AbstractTo improve the current real-world deployments of
Stackelberg security games (SSGs), it is critical
now to efficiently incorporate models of adversary
bounded rationality in large-scale SSGs. Unfortunately, previously proposed branch-and-price approaches fail to scale-up given the non-convexity of
such models, as we show with a realization called
COCOMO. Therefore, we next present a novel
cutting-plane algorithm called BLADE to scale-up
SSGs with complex adversary models,with three
key novelties: (i) an efficient scalable separation oracle to generate deep cuts; (ii) a heuristic that uses
gradient to further improve the cuts; (iii) techniques
for quality-efficiency tradeoff.
2013_19_teamcore_ijcai13_yang.pdf Jason Tsai, Yundi Qian, Yevgeniy Vorobeychik, Christopher Kiekintveld, and Milind Tambe. 2013. “
Security Games with Contagion: Handling Asymmetric Information .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) [SHORT PAPER].
AbstractCounterinsurgency, which is the effort to mitigate support for an
opposing organization, is one such domain that has been studied
recently and past work has modeled the problem as an influence
blocking maximization that features an influencer and a mitigator.
While past work has introduced scalable heuristic techniques for
generating effective strategies using a double oracle algorithm, it
has not addressed the issue of uncertainty and asymmetric information, which is the topic of this paper.
2013_3_teamcore_aamas13_camera_readyv3.pdf Bo An, Matthew Brown, Yevgeniy Vorobeychik, and Milind Tambe. 2013. “
Security Games with Surveillance Cost and Optimal Timing of Attack Execution.” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractStackelberg games have been used in several deployed applications
to allocate limited resources for critical infrastructure protection.
These resource allocation strategies are randomized to prevent a
strategic attacker from using surveillance to learn and exploit patterns in the allocation. Past work has typically assumed that the
attacker has perfect knowledge of the defender’s randomized strategy or can learn the defender’s strategy after conducting a fixed
period of surveillance. In consideration of surveillance cost, these
assumptions are clearly simplistic since attackers may act with partial knowledge of the defender’s strategies and may dynamically
decide whether to attack or conduct more surveillance. In this
paper, we propose a natural model of limited surveillance in which
the attacker dynamically determine a place to stop surveillance in
consideration of his updated belief based on observed actions and
surveillance cost. We show an upper bound on the maximum number of observations the attacker can make and show that the attacker’s optimal stopping problem can be formulated as a finite state
space MDP. We give mathematical programs to compute optimal
attacker and defender strategies. We compare our approaches with
the best known previous solutions and experimental results show
that the defender can achieve significant improvement in expected
utility by taking the attacker’s optimal stopping decision into account, validating the motivation of our work.
2013_2_teamcore_sglsc.pdf Jun-young Kwak, Pradeep Varakantham, Rajiv Maheswaran, Yu-Han Chang, Milind Tambe, Burcin Becerik-Gerber, and Wendy Wood. 2013. “
TESLA: An Energy-saving Agent that Leverages Schedule Flexibility .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractThis innovative application paper presents TESLA, an agent-based
application for optimizing the energy use in commercial buildings.
TESLA’s key insight is that adding flexibility to event/meeting
schedules can lead to significant energy savings. TESLA provides three key contributions: (i) three online scheduling algorithms that consider flexibility of people’s preferences for energyefficient scheduling of incrementally/dynamically arriving meetings and events; (ii) an algorithm to effectively identify key meetings that lead to significant energy savings by adjusting their flexibility; and (iii) surveys of real users that indicate that TESLA’s
assumptions exist in practice. TESLA was evaluated on data of
over 110,000 meetings held at nine campus buildings during eight
months in 2011–2012 at USC and SMU. These results show that,
compared to the current systems, TESLA can substantially reduce
overall energy consumption.
2013_4_teamcore_aamas13-tesla-camera-ready-finalv2.pdf Manish Jain. 2013. “
Thwarting Adversaries with Unpredictability: Massive-scale Game-Theoretic Algorithms for Real-world Security Deployments ”.
AbstractProtecting critical infrastructure and targets such as airports, transportation networks, power
generation facilities as well as critical natural resources and endangered species is an important
task for police and security agencies worldwide. Securing such potential targets using limited
resources against intelligent adversaries in the presence of the uncertainty and complexities of
the real-world is a major challenge. My research uses a game-theoretic framework to model the
strategic interaction between a defender (or security forces) and an attacker (or terrorist adversary)
in security domains.
Game theory provides a sound mathematical approach for deploying limited security resources
to maximize their effectiveness. While game theory has always been popular in the arena of
security, unfortunately, the state of the art algorithms either fail to scale or to provide a correct
solution for large problems with arbitrary scheduling constraints. For example, US carriers fly over
27,000 domestic and 2,000 international flights daily, presenting a massive scheduling challenge
for Federal Air Marshal Service (FAMS).
My thesis contributes to a very new area that solves game-theoretic problems using insights
from large-scale optimization literature towards addressing the computational challenge posed by
real-world domains. I have developed new models and algorithms that compute optimal strategies
for scheduling defender resources is large real-world domains. My thesis makes the following contributions. First, it presents new algorithms that can solve for trillions of actions for both
the defender and the attacker. Second, it presents a hierarchical framework that provides orders
of magnitude scale-up in attacker types for Bayesian Stackelberg games. Third, it provides an
analysis and detection of a phase-transition that identifies properties that makes security games
hard to solve.
These new models have not only advanced the state of the art in computational game-theory,
but have actually been successfully deployed in the real-world. My work represents a successful
transition from game-theoretic advancements to real-world applications that are already in use, and
it has opened exciting new avenues to greatly expand the reach of game theory. For instance, my
algorithms are used in the IRIS system: IRIS has been in use by the Federal Air Marshals Service
(FAMS) to schedule air marshals on board international commercial flights since October 2009.
2013_25_teamcore_manish_thesis.pdf Jun-young Kwak, Pradeep Varakantham, Rajiv Maheswaran, Yu-Han Chang, Milind Tambe, Burcin Becerik-Gerber, and Wendy Wood. 2013. “
Why TESLA Works: Innovative Agent-based Application Leveraging Schedule Flexibility for Conserving Energy .” In Workshop on Multiagent-based Societal Systems (MASS) at AAMAS.
AbstractThis paper presents TESLA, an agent-based application for optimizing the energy use in commercial buildings. TESLA’s key insight is that adding flexibility to event/meeting schedules can lead
to significant energy savings. TESLA provides two key contributions: (i) three online scheduling algorithms that consider flexibility of people’s preferences for energy-efficient scheduling of incrementally/dynamically arriving meetings and events; and (ii) an
algorithm to effectively identify key meetings that lead to significant energy savings by adjusting their flexibility. TESLA was
evaluated on data of over 110,000 meetings held at nine campus
buildings during eight months in 2011–2012 at the University of
Southern California (USC) and the Singapore Management University (SMU), and it indicated that TESLA’s assumptions exist in
practice. This paper also provides an extensive analysis on energy
savings achieved by TESLA. These results and analysis show that,
compared to the current systems, TESLA can substantially reduce
overall energy consumption.
2013_12_teamcore_mass-camera-ready-v2.pdf Manish Jain, Vincent Conitzer, and Milind Tambe. 2013. “
Security Scheduling for Real-world Networks .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
AbstractNetwork based security games, where a defender strategically places security measures on the edges of a graph to protect against an adversary, who chooses a path through a graph is an important research problem with potential for real-world impact. For example, police forces face the problem of placing checkpoints on roads to inspect vehicular traffic in their day-to-day operations, a security measure the Mumbai police have performed since the terrorist attacks in 2008. Algorithms for solving such network-based security problems have been proposed in the literature, but none of them scale up to solving problems of the size of real-world networks. In this paper, we present SNARES, a novel algorithm that computes optimal solutions for both the defender and the attacker in such network security problems. Based on a double-oracle framework, SNARES makes novel use of two approaches: warm starts and greedy responses. It makes the following contributions: (1) It defines and uses mincut-fanout, a novel method for efficient warm-starting of the computation; (2) It exploits the submodularity property of the defender optimization in a greedy heuristic, which is used to generate “better-responses"; SNARES also uses a better-response computation for the attacker. Furthermore, we evaluate the performance of SNARES in real-world networks illustrating a significant advance: whereas state-of-the-art algorithms could handle just the southern tip of Mumbai, SNARES can compute optimal strategy for the entire urban road network of Mumbai.
2013_7_teamcore_fp066-jain.pdf 2012
Yevgeniy Vorobeychik, Bo An, and Milind Tambe. 2012. “
Adversarial Patrolling Games .” In AAAI Spring Symposium on Security, Sustainability and Health.
AbstractDefender-Attacker Stackelberg games are the foundations of
tools deployed for computing optimal patrolling strategies in
adversarial domains such as the United states Federal Air
Marshals Service and the United States Coast Guard, among
others. In Stackelberg game models of these systems the attacker knows only the probability that each target is covered
by the defender, but is oblivious to the detailed timing of the
coverage schedule. In many real-world situations, however,
the attacker can observe the current location of the defender
and can exploit this knowledge to reason about the defender’s
future moves. We study Stackelberg security games in which
the defender sequentially moves between targets, with moves
constrained by an exogenously specified graph, while the attacker can observe the defender’s current location and his
(stochastic) policy concerning future moves. We offer five
contributions: (1) We model this adversarial patrolling game
(APG) as a stochastic game with special structure and present
several alternative formulations that leverage the general nonlinear programming (NLP) approach for computing equilibria
in zero-sum stochastic games. We show that our formulations
yield significantly better solutions than previous approaches.
(2) We extend the NLP formulation for APG allow for attacks
that may take multiple time steps to unfold. (3) We provide
an approximate MILP formulation that uses discrete defender
move probabilities. (4) We experimentally demonstrate the
efficacy of an NLP-based approach, and systematically study
the impact of network topology on the results. (5) We extend
our model to allow the defender to construct the graph constraining his moves, at some cost, and offer novel algorithms
for this setting, finding that a MILP approximation is much
more effective than the exact NLP in this setting.
2012_3_teamcore_patrolsymp.pdf Yevgeniy Vorobeychik, Bo An, and Milind Tambe. 2012. “
Adversarial Patrolling Games: Extended Abstract .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) (Short paper).
AbstractDefender-Attacker Stackelberg games are the foundations of tools
deployed for computing optimal patrolling strategies in adversarial domains such as the United states Federal Air Marshals Service
and the United States Coast Guard, among others. In Stackelberg
game models of these systems the attacker knows only the probability that each target is covered by the defender, but is oblivious to
the detailed timing of the coverage schedule. In many real-world
situations, however, the attacker can observe the current location of
the defender and can exploit this knowledge to reason about the
defender’s future moves. We study Stackelberg security games
in which the defender sequentially moves between targets, with
moves constrained by an exogenously specified graph, while the attacker can observe the defender’s current location and his (stochastic) policy concerning future moves.
2012_12_teamcore_patrol_short.pdf Michal Jakob, Zbynek Moler, Antonín Komenday, Zhengyu Yin, Albert Xin Jiang, Matthew P. Johnson, Michal Pechoucek, and Milind Tambe. 2012. “
AgentPolis: Towards a Platform for Fully Agent-based Modeling of Multi-Modal Transportation .” In International Conference on Autonomous Agents and Multiagent Systems (AAMAS) Demonstration Track.
AbstractAgentPolis is a fully agent-based platform for modeling
multi-modal transportation systems. It comprises a highperformance discrete-event simulation core, a cohesive set of
high-level abstractions for building extensible agent-based
models and a library of predefined components frequently
used in transportation models. Together with a suite of supporting tools, AgentPolis enables rapid prototyping and
execution of data-driven simulations of a wide range of mobility and transportation phenomena. We illustrate the capabilities of the platform on a model of fare inspection in
public transportation networks.
2012_22_teamcore_agpolis-aamas-cr-rc2.pdf Jason Tsai, Nicholas Weller, and Milind Tambe. 2012. “
Analysis of Heuristic Techniques for Controlling Contagion .” In AAAI Fall Symposium.
AbstractMany 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.
AbstractIllegal 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).
AbstractTo 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.
AbstractThere 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.
AbstractNations 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.pdfManish Jain, Kevin Leyton-Brown, and Milind Tambe. 2012. “
The Deployment-to-Saturation Ratio in Security Games .” In Conference on Artificial Intelligence (AAAI).
AbstractStackelberg 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) .
AbstractIn 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 .
AbstractIllegal 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