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 se...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(Min SDS) 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.展开更多
基金supported in part by the National Natural Science Foundation of China(U20A2068, 11771013)Zhejiang Provincial Natural Science Foundation of China (LD19A010001)。
文摘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(Min SDS) 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.
