A Game-Theoretic Approach to Solving the Roman Domination Problem

Xiuyang Chen; Changbing Tang; Zhao Zhang; Guanrong Chen

doi:10.1109/JAS.2023.123840

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 > In Press, Accepted Manuscript

X. Chen, C. Tang, Z. Zhang, and G. Chen, “A game-theoretic approach to solving the Roman domination problem,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 0, pp. 1–17, Aug. 2023. doi: 10.1109/JAS.2023.123840

Citation:

X. Chen, C. Tang, Z. Zhang, and G. Chen, “A game-theoretic approach to solving the Roman domination problem,” IEEE/CAA J. Autom. Sinica, vol. 10, no. 0, pp. 1–17, Aug. 2023. doi: 10.1109/JAS.2023.123840

Citation:

PDF( 2230 KB)

A Game-Theoretic Approach to Solving the Roman Domination Problem

doi: 10.1109/JAS.2023.123840

Funds: This work was supported in part by the National Natural Science Foundation of China (U20A2068), and Zhejiang Provincial Natural Science Foundation of China ( LD19A010001, LZ24F030009)

More Information

Author Bio:
Xiuyang Chen received the B.S. degree in mathematics and applied mathematics from Zhejiang International Studies University in 2018. He received his M.S. degree in mathematics and applied mathematics with Zhejiang Normal University in 2021. He is currently pursuing the Ph.D. degree in mathematics and applied mathematics with Xinjiang University.His current research interests include game theory, mechanism design, intelligence algorithm, and approximation algorithm

Changbing Tang (Senior Member, IEEE) received the Ph.D. degree from the Department of Electronic Engineering, Fudan University in 2014. He received the B.S. and M.S. degrees in mathematics and applied mathematics from Zhejiang Normal University in 2004 and 2007, respectively.Dr. Tang was the recipient of the Academic New Artist Doctoral Post Graduate from the Ministry of Education of China in 2012 and the recipient of the Academician Pairing Training Program for Young Talents of Zhejiang Province in 2019. He is currently an Associate Professor with the College of Physics and Electronic Information Engineering, Zhejiang Normal University. His research interests include game theory and its applications, networks, and distributed optimization

Zhao Zhang received the B.S. degree in computational mathematics, M.S. degree in basic mathematics and Ph.D. degree in applied mathematics from Xinjiang University in 1996, 1999 and 2003, respectively.From 2003−2014, She was engaged in scientific research at Xinjiang University. She is currently a Distinguished Professor of Zhejiang Normal University. Her current research interests include approximation algorithm, combinatorial optimization, and machine learning

Guanrong Chen (Life Fellow, IEEE) received the MSc degree in computer science from Sun Yat-sen University in 1981 and the Ph.D. degree in applied mathematics from Texas A&M University, College Station, USA in 1987. He was a Tenured Full Professor at the University of Houston, USA before he joined the City University of Hong Kong as a Chair Professor in 2000, where he has been the Founding Director of the Centre for Complexity and Complex Networks, and is now the Hong Kong Shun Hing Education and Charity Fund Chair Professor in Engineering. Professor Chen was awarded the 2011 Euler Gold Medal from Russia, and conferred Honorary Doctor Degrees by the Saint Petersburg State University, Russia in 2011 and by the University of Normandy, France in 2014. He has been a Member of the Academia Europaea since 2014 and a Fellow of the World Academy of Sciences since 2015.Professor Chen’s research interests are in the fields of complex networks, nonlinear dynamics and control systems. He has been a Highly Cited Researcher in engineering continuously for some ten years according to Clarivate Web of Science
Corresponding author: Changbing Tang, e-mail: tangcb@zjnu.edu.cn; Zhao Zhang, e-mail: hxhzz@sina.com
Received Date: 2023-02-16
Revised Date: 2023-05-19
Accepted Date: 2023-08-19

Available Online: 2024-09-20

Abstract

Abstract

The Roman domination problem is an important combinatorial optimization problem that is derived from an old story of defending the Roman Empire and now regains new significance in cyber space security, considering backups in the face of a dynamic network security requirement. In this paper, firstly, we propose a Roman domination game (RDG) and prove that every Nash equilibrium (NE) of the game corresponds to a strong minimal Roman dominating function (S-RDF), as well as a Pareto-optimal solution. Secondly, we show that RDG is an exact potential game, which guarantees the existence of an NE. Thirdly, we design a game-based synchronous algorithm (GSA), which can be implemented distributively and converge to an NE in $ O(n)$ rounds, where n is the number of vertices. In GSA, all players make decisions depending on local information. Furthermore, we enhance GSA to be enhanced GSA (EGSA), which converges to a better NE in $ O(n^2)$ rounds. Finally, we present numerical simulations to demonstrate that EGSA can obtain a better approximate solution in promising computation time compared with state-of-the-art algorithms.
- Distributed algorithm,
- game theory,
- multi-agent system,
- potential game,
- Roman dominating function

FullText(HTML)

References(45)

References

[1]	I. Stewart, “Defend the Roman Empire!” Scientific American, vol. 281, no. 6, pp. 136–138, Dec. 1999.
[2]	E. J. Cockayne, P. A. Dreyer, S. M. Hedetniemi, and S. T. Hedetniemi, “Roman domination in graphs,” Discrete Mathematics, vol. 278, no. 1, pp. 11–22, 2004.
[3]	A. Pagourtzis, P. Penna, K. Schlude, K. Steinhöfel, D. S. Taylor, and P. Widmayer, Server Placements, Roman Domination and Other Dominating Set Variants. Boston, MA: Springer US, 2002, pp. 280–291.
[4]	F. Ghaffari, B. Bahrak, and S. P. Shariatpanahi, “A novel approach to partial coverage in wireless sensor networks via the Roman dominating set,” IET Networks, vol. 11, no. 2, pp. 58–69, 2022. doi: 10.1049/ntw2.12034
[5]	C. S. ReVelle and K. E. Rosing, “Defendens imperium romanum: A classical problem in military strategy,” The American Mathematical Monthly, vol. 107, no. 7, pp. 585–594, 2000. doi: 10.1080/00029890.2000.12005243
[6]	P. A. Dreyer, “Applications and variations of domination in graphs,” 2000.
[7]	W. Shang and X. Hu, “The Roman domination problem in unit disk graphs,” in Computational Science. Springer Berlin Heidelberg, 2007, pp. 305–312.
[8]	L. Wang, Y. Shi, Z. Zhang, Z.-B. Zhang, and X. Zhang, “Approximation algorithm for a generalized Roman domination problem in unit ball graphs,” J. Combinatorial Optimization, vol. 39, no. 1, pp. 138–148, 2020. doi: 10.1007/s10878-019-00459-1
[9]	H. A. Abdollahzadeh, A. M. Henning, V. Samodivkin, and G. I. Yero, “Total Roman domination in graphs,” Applicable Analysis and Discrete Mathematics, vol. 10, pp. 501–517, 2016. doi: 10.2298/AADM160802017A
[10]	A. Ghaffari-Hadigheh, “Roman domination problem with uncertain positioning and deployment costs,” Soft Computing, vol. 24, no. 4, pp. 2637–2645, 2020. doi: 10.1007/s00500-019-03811-z
[11]	M. Hajjari, H. A. Ahangar, R. Khoeilar, Z. Shao, and S. M. Sheikholeslami, “New bounds on the triplE Roman domination number of graphs,” J. Mathematics, vol. 2022, pp. 1–5, 2022.
[12]	X. Chen, G. Hao, and Z. Xie, “A note on Roman domination of digraphs,” Discussiones Mathematicae Graph Theory, vol. 39, no. 1, pp. 13–21, 2019. doi: 10.7151/dmgt.2067
[13]	L. Ouldrabah, M. Blidia, and A. Bouchou, “Roman domination in oriented trees,” Electronic J. Graph Theory and Applications, vol. 9, no. 1, pp. 95–103, 2021. doi: 10.5614/ejgta.2021.9.1.9
[14]	P. Pavlič and J. Žerovnik, “Roman domination number of the cartesian products of paths and cycles,” The Electronic J. Combinatorics, vol. 19, no. 3, pp. 19–56, 2012. doi: 10.37236/2595
[15]	M. Reddappa and D. C. J. S. Reddy, “Total Roman domination in special type interval graph,” Int. J. Engineering Research &Technology, vol. 8, no. 10, pp. 343–348, 2019.
[16]	E. Cockayne, P. Grobler, W. Gründlingh, J. Munganga, and J. Vuuren, “Protection of a graph,” Utilitas Mathematica, vol. 67, pp. 19–32, 2005.
[17]	H. Peters, Game Theory, a Multi-Leveled Approach, 2nd ed. Berlin, Heidelberg: Springer-Verlag, 2008.
[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 Internet and Distributed Computing Systems, Cham, 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]	X. Chen, C. Tang, and Z. Zhang, “A game theoretic approach for minimal secure dominating set,” To appear in IEEE/CAA J. Automatica Sinica.
[22]	Y. Yang and X. Li, “Towards a snowdrift game optimization to vertex cover of networks,” IEEE Trans. Cybernetics, vol. 43, no. 3, pp. 948–956, 2013. doi: 10.1109/TSMCB.2012.2218805
[23]	C. Tang, A. Li, and X. Li, “Asymmetric game: A silver bullet to weighted vertex cover of networks,” IEEE Trans. Cybernetics, vol. 48, no. 10, pp. 2994–3005, 2018. doi: 10.1109/TCYB.2017.2754919
[24]	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. Cybernetics, vol. 49, no. 5, pp. 1968–1978, 2019. doi: 10.1109/TCYB.2018.2817631
[25]	C. Sun, H. Qiu, W. Sun, Q. Chen, L. Su, X. Wang, and Q. Zhou, “Better approximation for distributed weighted vertex cover via game-theoretic learning,” IEEE Trans. Systems,Man,and Cybernetics: Systems, vol. 52, no. 8, pp. 5308–5319, 2022. doi: 10.1109/TSMC.2021.3121695
[26]	C. Sun, X. Wang, H. Qiu, and Q. Chen, “A game theoretic solver for the minimum weighted vertex cover,” in Proc. 2019 IEEE Int. Conf. Systems, Man and Cybernetics, 2019, pp. 1920–1925.
[27]	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, pp. 1–12, 2022.
[28]	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
[29]	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
[30]	Q. Fang and L. Kong, “Core stability of vertex cover games,” in Internet and Network Economics. Springer Berlin Heidelberg, 2007, pp. 482–490.
[31]	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
[32]	H. K. Kim, “On connected dominating set games,” J. the Korean Data and Information Science Society, vol. 22, pp. 1275–1281, 2011.
[33]	X. Ai, V. Srinivasan, and C. Tham, “Optimality and complexity of pure Nash equilibria in the coverage game,” IEEE J. Selected Areas in Communications, vol. 26, no. 7, pp. 1170–1182, 2008. doi: 10.1109/JSAC.2008.080914
[34]	J. F. Nash, “Equilibrium points in n-person games,” Proc. the National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950. doi: 10.1073/pnas.36.1.48
[35]	C. Padamutham and V. S. R. Palagiri, “Algorithmic aspects of Roman domination in graphs,” J. Applied Mathematics and Computing, vol. 64, no. 1, pp. 89–102, 2020.
[36]	D. Monderer and L. Shapley, “Potential games,” Games and Economic Behavior, vol. 14, pp. 124–143, 1996. doi: 10.1006/game.1996.0044
[37]	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
[38]	P. Erdös and A. Rényi, “On random graphs l,” Publicationes Mathematicae Debrecen, vol. 6, pp. 290–297, 1959.
[39]	K. Li, Y. Ran, Z. Zhang, and D.-Z. Du, “Nearly tight approximation algorithm for (connected) Roman dominating set,” Optimization Letters, vol. 16, no. 8, pp. 2261–2276, 2022. doi: 10.1007/s11590-022-01862-0
[40]	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
[41]	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
[42]	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
[43]	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, pp. 1–12, 2022.
[44]	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
[45]	M. J. Osborne and A. Rubinstein, A Course in Game Theory, 1st ed. London, England: MIT Press, 1994.

Supplements(0)

Cited By

Proportional views

Proportional views

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

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

Figures(11) / Tables(5)

Get Citation

PDF

XML

Article Metrics

Article views (28) PDF downloads(7)

A Game-Theoretic Approach to Solving the Roman Domination Problem

doi: 10.1109/JAS.2023.123840

Abstract

References

Proportional views

Catalog

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

Article Metrics

Export File

Citation

Format

Content