A Game Theoretic Approach for a Minimal Secure Dominating Set

The secure dominating set (SDS), a variant of the dominating set, is an important combinatorial structure used in wireless networks. In this paper, we apply algorithmic game theory to study the minimum secure dominating set (MinSDS) problem in a multi-agent system. We design a game framework for SDS and show that every Nash equilibrium (NE) is a minimal SDS, which is also a Pareto-optimal solution. We prove that the proposed game is an exact potential game, and thus NE exists, and design a polynomial-time distributed local algorithm which converges to an NE in O (n) rounds of interactions. Extensive experiments are done to test the performance of our algorithm, and some interesting phenomena are witnessed.