IEEE/CAA Journal of Automatica Sinica
Citation:  X. Y. Chen, C. B. Tang, and Z. Zhang, “A game theoretic approach for a minimal secure dominating set,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 12, pp. 2258–2268, Dec. 2023. doi: 10.1109/JAS.2023.123315 
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 multiagent system. We design a game framework for SDS and show that every Nash equilibrium (NE) is a minimal SDS, which is also a Paretooptimal solution. We prove that the proposed game is an exact potential game, and thus NE exists, and design a polynomialtime 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.
[1] 
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Fundamentals of Domination in Graphs. Boca Raton, USA: CRC Press, Jan. 1998.

[2] 
T. W. Haynes, S. T. Hedetniemi, and P. J. Slater, Domination in Graphs. New York, USA: Routledge, Oct. 1998, vol. 2.

[3] 
T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, Topics in Domination in Graphs. Geneva, Switzerland: Springer, Cham, Jan. 2020, vol. 64.

[4] 
A. Burger, A. de Villiers, and J. van Vuuren, “A linear algorithm for secure domination in trees,” Discrete Applied Math., vol. 171, pp. 15–27, 2014. doi: 10.1016/j.dam.2014.02.001

[5] 
E. Cockayne, P. Grobler, W. Gründlingh, J. Munganga, and J. Vuuren, “Protection of a graph,” Utilitas Mathematica, vol. 67, pp. 19–32, 2005.

[6] 
A. Burger, A. de Villiers, and J. Vuuren, “Two algorithms for secure graph domination,” J. Combinatorial Math. and Combinatorial Computing, vol. 85, pp. 321–339, 2013.

[7] 
H. Boumediene Merouane and M. Chellali, “On secure domination in graphs,” Infor. Proc. Lett., vol. 115, no. 10, pp. 786–790, 2015. doi: 10.1016/j.ipl.2015.05.006

[8] 
T. Araki and H. Miyazaki, “Secure domination in proper interval graphs,” Discrete Applied Math., vol. 247, pp. 70–76, 2018. doi: 10.1016/j.dam.2018.03.040

[9] 
T. Araki and R. Yamanaka, “Secure domination in cographs,” Discrete Applied Math., vol. 262, pp. 179–184, 2019. doi: 10.1016/j.dam.2019.02.043

[10] 
T. Araki and I. Yumoto, “On the secure domination numbers of maximal outerplanar graphs,” Discrete Applied Math., vol. 236, pp. 23–29, 2018. doi: 10.1016/j.dam.2017.10.020

[11] 
A. P. Burger, M. A. Henning, and J. H. van Vuuren, “Vertex covers and secure domination in graphs,” Quaestiones Math., vol. 31, no. 2, pp. 163–171, 2008. doi: 10.2989/QM.2008.31.2.5.477

[12] 
A. Burger, A. de Villiers, and J. van Vuuren, “On minimum secure dominating sets of graphs,” Quaestiones Math., vol. 39, no. 2, pp. 189–202, 2016. doi: 10.2989/16073606.2015.1068238

[13] 
E. Castillano, R. Ugbinada, and S. Canoy Jr, “Secure domination in the joins of graphs,” Applied Math. Sciences, vol. 8, pp. 5203–5211, 2014. doi: 10.12988/ams.2014.47519

[14] 
D. Corneil, H. Lerchs, and L. Burlingham, “Complement reducible graphs,” Discrete Applied Math., vol. 3, no. 3, pp. 163–174, 1981. doi: 10.1016/0166218X(81)900135

[15] 
D. Pradhan and A. Jha, “On computing a minimum secure dominating set in block graphs,” J. Combinatorial Optimization, vol. 35, pp. 613–631, 2018. doi: 10.1007/s108780170197y

[16] 
Z. Han, D. Niyato, W. Saad, T. Başar, and A. Hjørungnes, Game Theory in WIReless and Communication Networks: Theory, Models, and Applications. Cambridge, UK: Cambridge University Press, Jan. 2011.

[17] 
D.Z. Du and P.J. Wan, Connected Dominating Set: Theory and Applications. New York, USA: Springer 2013, vol. 77.

[18] 
L.H. Yen and Z.L. Chen, “Gametheoretic approach to selfstabilizing distributed formation of minimal multidominating sets,” IEEE Trans. Parallel and Distributed Systems, vol. 25, no. 12, pp. 3201–3210, 2014. doi: 10.1109/TPDS.2013.2297100

[19] 
L.H. Yen and G.H. Sun, “Gametheoretic approach to selfstabilizing minimal independent dominating sets,” in Proc. Internet and Distributed Computing Syst., 2018, pp. 173–184.

[20] 
X. Chen and Z. Zhang, “A game theoretic approach for minimal connected dominating set,” Theoretical Computer Science, vol. 836, pp. 29–36, 2020. doi: 10.1016/j.tcs.2020.05.020

[21] 
Y. Yang and X. Li, “Towards a snowdrift game optimization to vertex cover of networks,” IEEE Trans. Cyber., vol. 43, no. 3, pp. 948–956, 2013. doi: 10.1109/TSMCB.2012.2218805

[22] 
C. Tang, A. Li, and X. Li, “Asymmetric game: A silver bullet to weighted vertex cover of networks,” IEEE Trans. Cyber., vol. 48, no. 10, pp. 2994–3005, 2018. doi: 10.1109/TCYB.2017.2754919

[23] 
C. Sun, W. Sun, X. Wang, and Q. Zhou, “Potential game theoretic learning for the minimal weighted vertex cover in distributed networking systems,” IEEE Trans. Cyber., vol. 49, no. 5, pp. 1968–1978, 2019. doi: 10.1109/TCYB.2018.2817631

[24] 
C. Sun, X. Wang, H. Qiu, and Q. Chen, “A game theoretic solver for the minimum weighted vertex cover,” in Proc. IEEE Int. Conf. Syst., Man and Cyber., 2019, pp. 1920–1925.

[25] 
J. Chen, K. Luo, C. Tang, Z. Zhang, and X. Li, “Optimizing polynomialtime solutions to a network weighted vertex cover game,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 2, pp. 512–523, 2023. doi: 10.1109/JAS.2022.105521

[26] 
X.Y. Li, Z. Sun, W. Wang, X. Chu, S. Tang, and P. Xu, “Mechanism design for set cover games with selfish element agents,” Theoretical Computer Science, vol. 411, no. 1, pp. 174–187, 2010. doi: 10.1016/j.tcs.2009.09.024

[27] 
X.Y. Li, Z. Sun, W. Wang, and W. Lou, “Cost sharing and strategyproof mechanisms for set cover games,” J. Comb. Optim., vol. 20, pp. 259–284, 2010. doi: 10.1007/s108780099209x

[28] 
Q. Fang and L. Kong, “Core stability of vertex cover games,” in Internet and Network Economics. Berlin Heidelberg, Germang: Springer, 2007, pp. 482–490.

[29] 
B. van Velzen, “Dominating set games,” Operations Research Letters, vol. 32, no. 6, pp. 565–573, 2004. doi: 10.1016/j.orl.2004.02.004

[30] 
H. K. Kim, “On connected dominating set games,” J. Korean Data and Information Science Society, vol. 22, pp. 1275–1281, 2011.

[31] 
X. Ai, V. Srinivasan, and C. Tham, “Optimality and complexity of pure nash equilibria in the coverage game,” IEEE J. Selected Areas in Commun., vol. 26, no. 7, pp. 1170–1182, 2008. doi: 10.1109/JSAC.2008.080914

[32] 
J. F. Nash, “Equilibrium points in nperson games,” Proc. National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950. doi: 10.1073/pnas.36.1.48

[33] 
D. Monderer and L. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, pp. 124–143, 1996. doi: 10.1006/game.1996.0044

[34] 
A.L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. doi: 10.1126/science.286.5439.509

[35] 
P. Erdös and A. Rényi, “On random graphs l,” Publicationes Mathematicae Debrecen, vol. 6, pp. 290–297, 1959.

[36] 
T. Roughgarden, “The price of anarchy is independent of the network topology,” J. Computer and System Sciences, vol. 67, no. 2, pp. 341–364, 2003. doi: 10.1016/S00220000(03)000448

[37] 
Y. Li and A. S. Morse, “The power allocation game on a network: A paradox,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 771–776, 2018. doi: 10.1109/JAS.2018.7511129

[38] 
G. Zhao, Y. Wang, and H. Li, “A matrix approach to the modeling and analysis of networked evolutionary games with time delays,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 4, pp. 818–826, 2018. doi: 10.1109/JAS.2016.7510259

[39] 
M. Ye, D. Li, Q.L. Han, and L. Ding, “Distributed Nash equilibrium seeking for general networked games with bounded disturbances,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 2, pp. 376–387, 2023. doi: 10.1109/JAS.2022.105428

[40] 
D. Cheng, T. Xu, F. He, and H. Qi, “On dynamics and Nash equilibriums of networked games,” IEEE/CAA J. Autom. Sinica, vol. 1, no. 1, pp. 10–18, 2014. doi: 10.1109/JAS.2014.7004614
