Stackelberg Security Games: Models, Applications and Computational Aspects

Authors

DOI:

https://doi.org/10.26636/jtit.2016.3.749

Keywords:

Bayesian games, game theory, leadership, Nash equilibrium, normal form games, security games, Stackelberg equilibrium, Stackelberg games

Abstract

Stackelberg games are non-symmetric games where one player or specified group of players have the privilege position and make decision before the other players. Such games are used in telecommunication and computational systems for supporting administrative decisions. Recently Stackleberg games became useful also in the systems where security issues are the crucial decision criteria. In this paper authors briefly survey the most popular Stackelberg security game models and provide the analysis of the model properties illustrated in the realistic use cases.

Downloads

Download data is not yet available.

References

[1] R. B. Myerson, Game Theory: Analysis of Conflict. Harvard University Press, 1991.
View in Google Scholar

[2] N. Nisan et al., Eds., Algorithmic Game Theory. Cambridge University Press, 2007.
View in Google Scholar

[3] J. Pita et al., “Using game theory for Los Angeles Airport security”, AI Mag., vol. 30, no. 1, pp. 43–57, 2009 (doi: 10.1609/aimag.v30i1.2173).
View in Google Scholar

[4] S. Tadelis, Game Theory: An Introduction. Princeton University Press, 2013.
View in Google Scholar

[5] J. F. Nash, “Equilibrium points in n-person games”, Proc. of the National Academy of Sciences of the United States of America, vol. 36, no. 1, pp. 48–49, 1950.
View in Google Scholar

[6] B. von Stengel and S. Zamir, “Leadership with commitment to mixed strategies”, Tech. Rep. LSE-CDAM-2004-01, CDAM Research Report, 2004 [Online]. Available: http://www.cdam.lse.ac.uk/Reports/Files/cdam-2004-01.pdf
View in Google Scholar

[7] J. Gan and B. An, “Minimum support size of the defender’s strong Stackelberg equilibrium strategies in security games”, in Proc. AAAI Spring Symp. on Appl. Computat. Game Theory, Stanford, CA, USA, 2014 [Online]. Available: http://www.ntu.edu.sg/home/boan/papers/AAAISS14b.pdf
View in Google Scholar

[8] P. Paruchuri et al., “Efficient algorithms to solve Bayesian Stackelberg games for security applications”, in Proc. 23rd Nat. Conf. on Artificial Intelligence AAAI’08, Chicago, IL, USA, 2008, vol. 3, pp. 1559–1562.
View in Google Scholar

[9] M. Tambe, Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned, 1st ed. Cambridge University Press, 2011.
View in Google Scholar

[10] D. Korzhyk, Z. Yin, C. Kiekintveld, V. Conitzer, and M. Tambe, “Stackelberg vs. Nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness”, J. Artif. Intell. Res., vol. 41, no. 2, pp. 297–327, 2011.
View in Google Scholar

[11] M. Jain et al., “Bayesian Stackelberg games and their application for security at Los Angeles International Airport”, ACM SIGecom Exchan., vol. 7, no. 2, article no. 10, 2008 (doi: 10.1145/1399589.1399599).
View in Google Scholar

[12] J. Pita, M. Jain, M. Tambe, F. Ordoñez, and S. Kraus, “Robust solutions to Stackelberg games: Addressing bounded rationality and limited observations in human cognition”, Artif. Intell., vol. 174, no. 15, pp. 1142–1171, 2010 (doi: 10.1016/j.artint.2010.07.002).
View in Google Scholar

[13] R. Yang, C. Kiekintveld, F. Ordoñez, M. Tambe, and R. John, “Improving resource allocation strategies against human adversaries in security games: An extended study”, Artif. Intell., vol. 195, pp. 440–469, 2013 (doi: 10.1016/j.artint.2012.11.004).
View in Google Scholar

[14] A. Tambe and T. Nguyen, “Robust resource allocation in security games and ensemble modeling of adversary behavior”, in Proc. 30th Ann. ACM Symp. Appl. Comput. SAC’15, Salamanca, Spain, 2015, pp. 277–282 (doi: 10.1145/2695664.2695686).
View in Google Scholar

[15] J. Tsai, S. Rathi, C. Kiekintveld, F. Ordoñez, and M. Tambe, “IRIS – A tool for strategic security allocation in transportation networks”, in Proc. 8th International Conference on Autonomous Agents and Multiagent Systems AAMAS 2009, Budapest, Hungary, 2009, vol. 2, pp. 1327–1334.
View in Google Scholar

[16] M. Jain, E. Kardes, C. Kiekintveld, F. Ordoñez, and M. Tambe, “Security games with arbitrary schedules: A branch and price approach”, in Proc. 24th AAAI Conf. on Artif. Intell. AAAI-10, Atlanta, GA, USA, 2010, pp. 792–797.
View in Google Scholar

[17] B. An et al., “GUARDS and PROTECT: next generation applications of security games”, SIGecom Exch., vol. 10, no. 1, pp. 31–34, 2011 (doi: 10.1145/1978721.1978729).
View in Google Scholar

[18] B. An, M. Tambe, F. Ordoñez, E. A. Shieh, and C. Kiekintveld, “Refinement of strong Stackelberg equilibria in security games”, in Proc. 25th AAAI Conf. on Artif. Intell., San Francisco, CA, USA, 2011 [Online]. Available: http://www.aaai.org/OCS/index.php/AAAI/AAAI11/paper/view/3461/3928
View in Google Scholar

[19] J. Letchford and Y. Vorobeychik, “Computing optimal security strategies in networked domains: a cost-benefit approach”, in Proc. 11th Int. Conf. on Autonom. Agents and Multiagent Syst. AAMAS’12, Valencia, Spain, 2012, vol. 3, pp. 1303–1304.
View in Google Scholar

[20] J. B. Clempner and A. S. Poznyak, “Stackelberg security games: Computing the shortest-path equilibrium”, Expert Syst. with Applications, vol. 42, no. 8, pp. 3967–3979, 2015 (doi: 10.1016/j.eswa.2014.12.034).
View in Google Scholar

[21] D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd ed. Springer, 2008 (doi: 10.1007/978-0-387-74503-9).
View in Google Scholar

[22] M. Held, R. M. Karp, and P. Wolfe, “Large-scale optimization and the relaxation method”, in Proc. of the ACM Annual Conference ACM’72, Boston, MA, USA, 1972, vol. 1, pp. 507–509 (doi: 10.1145/800193.569964).
View in Google Scholar

[23] J. Rios, “Algorithm 928: A general, parallel implementation of Dantzig-Wolfe decomposition”, ACM Trans. Mathem. Softw., vol. 39, no. 3, article no. 21, 2013 (doi: 10.1145/2450153.2450159).
View in Google Scholar

[24] J. K. Ho and R. P. Sundarraj, “Distributed nested decomposition of staircase linear programs”, ACM Trans. Mathem. Softw., vol. 23, no. 2, pp. 148–173, 1997 (doi: 10.1145/264029.264031).
View in Google Scholar

[25] Z. Han, D. Niyato, W. Saad, T. Başar, and A. Hjørungnes, Game Theory in Wireless and Communication Networks, 1st ed. Cambridge University Press, 2012.
View in Google Scholar

Downloads

Published

2016-09-30

Issue

Section

RESEARCH ARTICLES

How to Cite

[1]
A. Wilczyński, A. Jakóbik (Krok), and J. Kołodziej, “Stackelberg Security Games: Models, Applications and Computational Aspects”, JTIT, vol. 65, no. 3, pp. 70–79, Sep. 2016, doi: 10.26636/jtit.2016.3.749.

Most read articles by the same author(s)

1 2 > >>