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.