Cost-Aware Coalition Formation in Multi-Defender Network Security Games: Mathematical Modeling and Optimization

Abstract

Distributed network security requires multiple defenders to make coupled resource allocation and coordination decisions under limited budgets, connectivity-dependent risks, and non-negligible coordination costs. We develop a mathematical framework for jointly optimizing defensive resource allocation and coalition formation in a multi-defender network security game. Nodes have heterogeneous values and protection thresholds, attacks propagate through vulnerable connected components, and defenders retain individual budgets while forming coalitions for joint decision-making. For each defender partition, the induced allocation game is evaluated by its worst pure-Nash-equilibrium loss together with a supermodular coordination cost. We prove that optimal protection is NP-hard even in a restricted setting, that every fixed partition induces an exact potential game with finite best-response convergence, and that decentralized equilibria can have an unbounded price of anarchy. We further characterize merge and split thresholds, the piecewise-constant dependence of optimal partitions on the coordination weight, the monotonicity of the selected coordination cost, and conditions for diminishing net merge benefits. Based on these properties, we propose Cost-Aware Coalition Search (CACS), which combines a tractable allocation oracle with multi-start local search over merge, split, and move operations. Experiments on synthetic and real networks show that selective coalitions provide a scalable tradeoff between residual attack loss and coordination cost across different resource levels, coordination weights, and defender populations. The framework provides a mathematical basis for organizing distributed defenders in networked security environments.