Saddle Point Search Algorithm for the Problem of Site Protection Level Assignment Based on Search of Simplices

This paper deals with a continuous zero-sum game with constraints on resources between a defender allocating resources for protection of sites and an attacker choosing sites for attack. The problem is formulated so that each player would have to solve its own linear program with a fixed solution of the other player. We show that in this case the saddle point is located on the faces of simplices defining feasible solutions. We propose an algorithm of saddle point search based on search of the simplices' faces on hyperplanes of equal dimension. Each possible face is defined using a boolean vector defining states of variables and problem constraints. The search of faces is reduced to the search of feasible boolean vectors. In order to reduce computational complexity of the search we formulate the rules for removing patently unfeasible faces. Each point of a face belonging to an (m--1)-dimensional hyperplane is defined using m points of the hyperplane. We created an algorithm for generating these points. Two systems of linear equations must be solved in order to find the saddle point if it located on the faces of simplices belonging to hyperplanes of equal dimension. We created a generic algorithm of saddle point search on the faces located on hyperplanes of equal dimension. We present an example of solving a problem and the results of computational experiments

References

[1] Ma C.Y.T., Yau D.K.Y., Rao N.S.V. Scalable solutions of Markov games for smart-grid infrastructure protection. IEEE Trans. Smart Grid, 2013, vol. 4, no. 1, pp. 47--55. DOI: 10.1109/TSG.2012.2223243

[2] Koppel A., Jakubiec F.Y., Ribeiro A. A saddle point algorithm for networked online convex optimization. IEEE Trans. Signal Process., 2015, vol. 63, no. 19, pp. 5149--5164. DOI: 10.1109/TSP.2015.2449255

[3] Paramasivan B., Prakash M., Kaliappan M. Development of a secure routing protocol using game theory model in mobile ad hoc networks. J. Commun. Inf. Netw., 2015, vol. 17, no. 1, pp. 75--83. DOI: 10.1109/JCN.2015.000012

[4] Wang Q., Zhu J. Optimal information security investment analyses with the consideration of the benefits of investment and using evolutionary game theory. 2nd Int. Conf. Information Management (ICIM), 2016, pp. 105--109. DOI: 10.1109/INFOMAN.2016.7477542

[5] Schottle P., Bohme R. Game theory and adaptive steganography. IEEE Trans. Inf. Forensics Security, 2016, vol. 11, no. 4, pp. 760--773. DOI: 10.1109/TIFS.2015.2509941

[6] Lei C., Ma D., Zhang H. Optimal strategy selection for moving target defense based on Markov game. IEEE Access, 2017, vol. 5, pp. 156--169. DOI: 10.1109/ACCESS.2016.2633983

[7] Xiao L., Chen T., Han G., et al. Channel-based authentication game in MIMO systems. IEEE GLOBECOM Conf., 2016, pp. 16. DOI: 10.1109/GLOCOM.2016.7841657

[8] Shah S., Chaitanya A., Sharma V. Resource allocation in fading multiple access wiretap channel via game theoretic learning. ITA Workshop, 2016, pp. 17. DOI: 10.1109/ITA.2016.7888137

[9] Li L., Shamma J. Efficient computation of discounted asymmetric information zero-sum stochastic games. 54th IEEE Conf. CDC, 2015, pp. 4531--4536. DOI: 10.1109/CDC.2015.7402927

[10] Freudiger J., Manshaei M.H., Hubaux J.P., et al. Cooperative location privacy. IEEE Trans. Depend. Sec. Comput., 2013, vol. 10, no. 2, pp. 84--98. DOI: 10.1109/TDSC.2012.85

[11] Gupta A., Langbort C., Basar T. Dynamic games with asymmetric information and resource constrained players with applications to security of cyberphysical systems. IEEE Trans. Control Netw. Syst., 2017, vol. 4, no. 1, pp. 71--81. DOI: 10.1109/TCNS.2016.2584183

[12] Chessa M., Grossklags J., Loiseau P. A game-theoretic study on non-monetary incentives in data analytics projects with privacy implications. IEEE 28th Computer Security Foundations Symp., 2015, pp. 90--104. DOI: 10.1109/CSF.2015.14

[13] Wang Ya., Yu F.R., Tang H., et al. A mean field game theoretic approach for security enhancements in mobile ad hoc networks. IEEE Trans. Wireless Commun., 2014, vol. 13, no. 3, pp. 1616--1627. DOI: 10.1109/TWC.2013.122313.131118

[14] Bykov A.Yu., Shmatova E.S. The algorithms of resource distribution for information security between objects of an information system based on the game model and principle of equal security of objects. Nauka i obrazovanie: nauchnoe izdanie [Science and Education: Scientific Publication], 2015, no. 9 (in Russ.). DOI: 10.7463/0915.0812283

[15] Bykov A.Yu., Krygin I.A., Mullin A.R. Algorithms of the protection system between assets of a mobile device on the basis of zero-sum game and equal security principle. Vestn. Mosk. Gos. Tekh. Univ. im. N.E. Baumana, Priborostr. [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], 2018, no. 2, pp. 48--68 (in Russ.).DOI: 10.18698/0236-3933-2018-2-48-68

[16] Golshteyn E.G. Generalized saddle version of the level method. Comput. Math. Math. Phys., 2001, vol. 41, no. 8, pp. 1083--1091.