M Brown, B An, C Kiekintveld, F Ordonez, and M Tambe
In Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012).
This is the author's version of the work.
It is posted here by permission of IFAAMAS for personal use, not for redistribution.
Download
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.
