Provable space discretization based evolutionary search for scalable multi-objective security games

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 targets and heterogeneous attackers may exceed the capability of most existing state-of-the-art (SOTA) methods, i.e., MOSGs are limited by the issue of scalability. In fact, there is still a lack of algorithms to improve scalability while ensuring accuracy. To this end, this paper proposes a general framework named Space Discretization based Evolutionary Search (SDES) based on many/multi-objective evolutionary algorithms (MOEAs) 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 EAs bypass the high-dimensional step function and simplify the solution of large-scale MOSGs. Then, MOEAs are 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 can solve up to 20 attackers and 100 targets MOSG problems, while SOTA methods can only solve up to 8 attackers and 25 targets. An ablation study verifies the necessity of all components in SDES.