An observation on pure strategies in Security Games
Marek Adrian, Gianluigi Greco
Citation: Proceedings of the 17th Conference on Computer Science and Intelligence Systems, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 30, pages 501–504 (2022)
Abstract. Security Games have been used in several different fields to randomise the division of limited resources and thus maximise the possibility of securing a set of targets. For this very practical purpose it is natural to consider primarily on mixed strategies, but such focus omits some theoretical properties of the games discussed. In this paper we discuss the existence and properties of pure Nash equilibria in security games. We give an overview of the basic observations that can be made in this setting. We also recognize an interesting problem in a case with multiple players playing a security game asynchronously, propose an algorithm for finding a strategy for any given player in the mentioned case and prove that the strategy profile resulting from the algorithm is in fact a Nash equilibrium and, even stronger, a subgame perfect equilibrium. We think that these findings are a nice supplement of the practical approach to Security Games and allow to form new research questions.
- J. Nash, “Non-cooperative games,” Annals of mathematics, pp. 286–295, 1951.
- G. Gottlob, G. Greco, and F. Scarcello, “Pure nash equilibria: hard and easy games,” JAIR, vol. 24, pp. 357–406, 2005.
- R. W. Rosenthal, “A class of games possessing pure-strategy nash equilibria,” Int. Journal of Game Theory, vol. 2, no. 1, pp. 65–67, 1973.
- H. Von Stackelberg, Market structure and equilibrium. Springer Science & Business Media, 2010.
- J. Pita, M. Jain, J. Marecki, F. Ordóñez, C. Portway, M. Tambe, C. Western, P. Paruchuri, and S. Kraus, “Deployed armor protection: the application of a game theoretic model for security at the los angeles international airport,” in Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track. International Foundation for Autonomous Agents and Multiagent Systems, 2008, pp. 125–132.
- J. Tsai, S. Rathi, C. Kiekintveld, F. Ordonez, and M. Tambe, “Iris-a tool for strategic security allocation in transportation networks,” AAMAS (Industry Track), pp. 37–44, 2009.
- F. Fang, P. Stone, and M. Tambe, “When security games go green: Designing defender strategies to prevent poaching and illegal fishing.” in IJCAI, 2015, pp. 2589–2595.
- M. Adrian, “Pure strategies in security games,” Ph.D. dissertation, UNICAL Universita della Calabria, 2017.
- K. Leyton-Brown and Y. Shoham, “Essentials of game theory: A concise multidisciplinary introduction,” Synthesis Lectures on Artificial Intelligence and Machine Learning, vol. 2, no. 1, pp. 1–88, 2008.
- S. Tadelis, Game theory: an introduction. Princeton university press, 2013.