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.
In such domains, decision makers have multiple competing objectives they must consider
which may take different forms that are not readily comparable including safety, cost, and
public perception. Thus, it can be difficult to know how to weigh the different objectives
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).
Instead of a single optimal solution, MOSGs have a set of Pareto optimal (non-dominated)
solutions referred to as the Pareto frontier, which can be generated by solving a sequence of
constrained single-objective optimization problems (CSOP). The Pareto frontier allows the
decision maker to analyze the tradeoffs that exist between the multiple 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; (iii) heuristics
that achieve speed up by exploiting the structure of security games to further constrain the
MILP; (iv) an approximate approach for solving a CSOP built off those same heuristics, increasing the scalability of our approach with quality guarantees. Additional contributions of
this paper include proofs on the level of approximation, detailed experimental evaluation of
the proposed approaches and heuristics, as well as a discussion on techniques for visualizing
the Pareto frontier.