  In the field of security, multi-objective security games (MOSGs) allow
defenders to simultaneously protect targets from multiple heterogeneous
attackers. MOSGs aim to simultaneously maximize all the heterogeneous payoffs,
e.g., life, money, and crime rate, without merging heterogeneous attackers. In
real-world scenarios, the number of heterogeneous attackers and targets to be
protected may exceed the capability of most existing state-of-the-art methods,
i.e., MOSGs are limited by the issue of scalability. To this end, this paper
proposes a general framework called SDES based on many-objective evolutionary
search to scale up MOSGs to large-scale targets and heterogeneous attackers.
SDES consists of four consecutive key components, i.e., discretization,
optimization, evaluation, and refinement. Specifically, SDES first discretizes
the originally high-dimensional continuous solution space to the
low-dimensional discrete one by the maximal indifference property in game
theory. This property helps evolutionary algorithms (EAs) bypass the
high-dimensional step function and ensure a well-convergent Pareto front. Then,
a many-objective EA is used for optimization in the low-dimensional discrete
solution space to obtain a well-spaced Pareto front. To evaluate solutions,
SDES restores solutions back to the original space via greedily optimizing a
novel divergence measurement. Finally, the refinement in SDES boosts the
optimization performance with acceptable cost. Theoretically, we prove the
optimization consistency and convergence of SDES. Experiment results show that
SDES is the first linear-time MOSG algorithm for both large-scale attackers and
targets. SDES is able to solve up to 20 attackers and 100 targets MOSG
problems, while the state-of-the-art (SOTA) methods can only solve up to 8
attackers and 25 targets ones. Ablation study verifies the necessity of all
components in SDES.
