A journal of IEEE and CAA , publishes high-quality papers in English on original theoretical/experimental research and development in all areas of automation
Advanced Search
Volume 10 Issue 12
Dec.  2023

IEEE/CAA Journal of Automatica Sinica

  • JCR Impact Factor: 15.3, Top 1 (SCI Q1)
    CiteScore: 23.5, Top 2% (Q1)
    Google Scholar h5-index: 77， TOP 5
Turn off MathJax
Article Contents
Article Navigation >  IEEE/CAA Journal of Automatica Sinica  > 2023  >  10(12): 2258-2268
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
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
shu

A Game Theoretic Approach for a Minimal Secure Dominating Set

doi: 10.1109/JAS.2023.123315
Funds:  This work was supported in part by the National Natural Science Foundation of China (U20A2068, 11771013) and Zhejiang Provincial Natural Science Foundation of China (LD19A010001)
More Information
    Abstract

  • 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.

     

    • FullText(HTML)
  • loading
    • References(40)
  • [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/0166-218X(81)90013-5
    [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/s10878-017-0197-y
    [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, “Game-theoretic approach to self-stabilizing distributed formation of minimal multi-dominating 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, “Game-theoretic approach to self-stabilizing 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 polynomial-time 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/s10878-009-9209-x
    [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 n-person 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/S0022-0000(03)00044-8
    [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
    • Related Articles
    • Supplements(0)

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Figures(6)  / Tables(5)

    Get Citation
    PDF
    XML

    Article Metrics

    Article views (383) PDF downloads(49) Cited by()

    Highlights

    • Designed a security domination game in multi-agent systems
    • Proved that the game is an exact potential game and Nash equilibrium (NE) exists
    • Showed that every NE is a minimal secure dominating set and a Pareto-optimal solution
    • Proposed a distributed algorithm to realize the game
    • The algorithm is local: every decision is based on information at most 6 hops away

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return