Stackelberg Security Games: Models, Applications and Computational Aspects

• Autorzy: Wilczyński A. , Jakóbik A. , Kołodziej J.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2016
• Tom: nr 3
• Strony: 70--79
• Opis fizyczny: Bibliogr. 25 poz., tab.

Twórcy

autor

Wilczyński A.

• AGH University of Science and Technology, Mickiewicza av 30, 30-059 Cracow, Poland
• Tadeusz Kościuszko Cracow University of Technolog,y Warszawska st 24, 31-155 Cracow, Poland

autor

Jakóbik A.

• Faculty of Physics, Mathematics and Computer Science, Tadeusz Kościuszko Cracow University of Technology, Warszawska st 24, 31-155 Cracow, Poland

autor

Kołodziej J.

• Faculty of Physics, Mathematics and Computer Science, Tadeusz Kościuszko Cracow University of Technology, Warszawska st 24, 31-155 Cracow, Poland

Bibliografia

• [1] R. B. Myerson, Game Theory: Analysis of Conflict. Harvard University Press, 1991).
• [2] N. Nisan et al., Ed., Algorithmic Game Theory. Cambridge University Press, 2007.
• [3] J. Pita et al., “Using game theory for Los Angeles Airport security”, Artif. Intell., vol. 30, no. 1, pp. 43–57, 2009 (doi: http://dx.doi.org/ 10.1609/aimag.v30i1.2173).
• [4] S. Tadelis, Game Theory: An Introduction. Princeton University Press, 2013.
• [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.
• [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
• [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
• [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.
• [9] M. Tambe, Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned, 1st ed. Cambridge University Press, 2011.
• [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.
• [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).
• [12] J. Pita, M. Jain, M. Tambe, F. Ordõnez, 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.org/10.1016/j.artint.2010.07.002).
• [13] R. Yang, C. Kiekintveld, F. Ordõnez, 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).
• [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).
• [15] J. Tsai, S. Rathi, C. Kiekintveld, F. Ordõnez, 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.
• [16] M. Jain, E. Kardes, C. Kiekintveld, F. Ordõnez, and M. Tambe, “Security games with arbitrary schedules: A Branch and price approach”, in Proc. 24th AAAI Conf. on Artif. Intell. AAAI-10, Atlanta, GE, USA, 2010, pp. 792–797.
• [17] B. An, J. Pita, E. Shieh, M. Tambe, C. Kiekintveld, and J. Marecki, “GUARDS and PROTECT: next generation applications of security games”, SIGecom Exch., vol. 10, no. 1, pp. 31–34, 2011 (doi: 10.1145/1978721.1978729).
• [18] B. An, M. Tambe, F. Ordõnez, 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: www.aaai.org/OCS/index.php/AAAI/ AAAI11/paper/view/3461/3928
• [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.
• [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).
• [21] D. G. Luenberger and Y. Ye, Linear and Nonlinear Programming, 3rd ed. Springer, 2008 (doi: 10.1007/978-0-387-74503-9).
• [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).
• [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).
• [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).
• [25] Z. Han, D. Niyato, W. Saad, T. Başar, and A. Hjørungnes, Game Theory in Wireless and Communication Networks, 1 ed. Cambridge University Press, 2012.