Handling a Kullback-Leibler divergence random walk for scheduling effective patrol strategies in Stackelberg security games

César U. S. Solis; Julio B. Clempner; Alexander S. Poznyak

Kybernetika (2019)

  • Volume: 55, Issue: 4, page 618-640
  • ISSN: 0023-5954

Abstract

top
This paper presents a new model for computing optimal randomized security policies in non-cooperative Stackelberg Security Games (SSGs) for multiple players. Our framework rests upon the extraproximal method and its extension to Markov chains, within which we explicitly compute the unique Stackelberg/Nash equilibrium of the game by employing the Lagrange method and introducing the Tikhonov regularization method. We also consider a game-theory realization of the problem that involves defenders and attackers performing a discrete-time random walk over a finite state space. Following the Kullback-Leibler divergence the players' actions are fixed and, then the next-state distribution is computed. The player's goal at each time step is to specify the probability distribution for the next state. We present an explicit construction of a computationally efficient strategy under mild defenders and attackers conditions and demonstrate the performance of the proposed method on a simulated target tracking problem.

How to cite

top

Solis, César U. S., Clempner, Julio B., and Poznyak, Alexander S.. "Handling a Kullback-Leibler divergence random walk for scheduling effective patrol strategies in Stackelberg security games." Kybernetika 55.4 (2019): 618-640. <http://eudml.org/doc/295077>.

@article{Solis2019,
abstract = {This paper presents a new model for computing optimal randomized security policies in non-cooperative Stackelberg Security Games (SSGs) for multiple players. Our framework rests upon the extraproximal method and its extension to Markov chains, within which we explicitly compute the unique Stackelberg/Nash equilibrium of the game by employing the Lagrange method and introducing the Tikhonov regularization method. We also consider a game-theory realization of the problem that involves defenders and attackers performing a discrete-time random walk over a finite state space. Following the Kullback-Leibler divergence the players' actions are fixed and, then the next-state distribution is computed. The player's goal at each time step is to specify the probability distribution for the next state. We present an explicit construction of a computationally efficient strategy under mild defenders and attackers conditions and demonstrate the performance of the proposed method on a simulated target tracking problem.},
author = {Solis, César U. S., Clempner, Julio B., Poznyak, Alexander S.},
journal = {Kybernetika},
keywords = {Stackelberg games; security; patrolling; Markov chains},
language = {eng},
number = {4},
pages = {618-640},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Handling a Kullback-Leibler divergence random walk for scheduling effective patrol strategies in Stackelberg security games},
url = {http://eudml.org/doc/295077},
volume = {55},
year = {2019},
}

TY - JOUR
AU - Solis, César U. S.
AU - Clempner, Julio B.
AU - Poznyak, Alexander S.
TI - Handling a Kullback-Leibler divergence random walk for scheduling effective patrol strategies in Stackelberg security games
JO - Kybernetika
PY - 2019
PB - Institute of Information Theory and Automation AS CR
VL - 55
IS - 4
SP - 618
EP - 640
AB - This paper presents a new model for computing optimal randomized security policies in non-cooperative Stackelberg Security Games (SSGs) for multiple players. Our framework rests upon the extraproximal method and its extension to Markov chains, within which we explicitly compute the unique Stackelberg/Nash equilibrium of the game by employing the Lagrange method and introducing the Tikhonov regularization method. We also consider a game-theory realization of the problem that involves defenders and attackers performing a discrete-time random walk over a finite state space. Following the Kullback-Leibler divergence the players' actions are fixed and, then the next-state distribution is computed. The player's goal at each time step is to specify the probability distribution for the next state. We present an explicit construction of a computationally efficient strategy under mild defenders and attackers conditions and demonstrate the performance of the proposed method on a simulated target tracking problem.
LA - eng
KW - Stackelberg games; security; patrolling; Markov chains
UR - http://eudml.org/doc/295077
ER -

References

top
  1. Agmon, N., Kaminka, G. A., Kraus, S., Multi-robot adversarial patrolling: facing a full-knowledge opponent., J. Artif. Intell. Res. 42 (2011), 1, 887-916. MR2874818
  2. Albarran, S., Clempner, J. B., 10.1016/j.engappai.2019.03.010, Engrg. Appl. Artif. Intell. 81 (2019), 408-419. DOI10.1016/j.engappai.2019.03.010
  3. Antipin, A. S., An extraproximal method for solving equilibrium programming problems and games., Comput. Mathematics and Math. Phys. 45 (2005), 11, 1893-1914. MR2203222
  4. Blum, A., Haghtalab, N and;, Procaccia, A. D., Lazy defenders are almost optimal against diligent attackers., In: Proc. 28th AAAI Conference on Artificial Intelligence, Québec 2014, pp. 573-579. 
  5. Clempner, J. B., 10.1080/00207179.2017.1371853, Int. J. Control 91 (2018), 2494-2510. MR3866732DOI10.1080/00207179.2017.1371853
  6. Clempner, J. B., Poznyak, A. S., 10.1007/s11518-014-5260-y, J. Systems Sci. Systems Engrg. 23 (2014), 4, 439-459. DOI10.1007/s11518-014-5260-y
  7. Clempner, J. B., Poznyak, A. S., 10.1016/j.eswa.2014.12.034, Expert Syst. Appl. 42 (2015), 8, 3967-3979. DOI10.1016/j.eswa.2014.12.034
  8. Clempner, J. B., Poznyak, A. S., Analyzing an optimistic attitude for the leader firm in duopoly models: A strong Stackelberg equilibrium based on a lyapunov game theory approach., Econ. Comput. Econ. Cybern. Stud. Res. 4 (2016), 50, 41-60. 
  9. Clempner, J. B., Poznyak, A. S., 10.1016/j.asoc.2016.05.037, Appl. Soft Comput. 47 (2016), 1-11. DOI10.1016/j.asoc.2016.05.037
  10. Clempner, J. B., Poznyak, A. S., 10.1016/j.asoc.2016.05.037, Appl. Soft Comput. 47 (2016), 1-11. DOI10.1016/j.asoc.2016.05.037
  11. Clempner, J. B., Poznyak, A. S., 10.1016/j.eswa.2015.11.006, Expert Systems Appl. 46 (2016), 474-484. DOI10.1016/j.eswa.2015.11.006
  12. Clempner, J. B., Poznyak, A. S., 10.1016/j.matcom.2016.12.010, Math. Comput. Simul. 138 (2017), 14-30. MR3638268DOI10.1016/j.matcom.2016.12.010
  13. Clempner, J. B., Poznyak, A. S., 10.1080/0305215x.2017.1418866, Engrg. Optim. 50 (2018), 11, 1996-2012. MR3851177DOI10.1080/0305215x.2017.1418866
  14. Clempner, J. B., Poznyak, A. S., 10.1016/j.cam.2017.07.032, J. Comput. Appl. Math. 328 (2018), 267-286. MR3697102DOI10.1016/j.cam.2017.07.032
  15. Conitzer, V., Sandholm, T., Computing the optimal strategy to commit to., In: Seventh ACM Conference on Electronic Commerce, Ann Arbor 2006, pp. 82-90. 
  16. Guerrero, D., Carsteanu, A. A., Huerta, R., Clempner, J. B., 10.1109/iceee.2017.8108857, In: 14th International Conference on Electrical Engineering, Computing Science and Automatic Control, Mexico City 2017, pp. 1-6. DOI10.1109/iceee.2017.8108857
  17. Guerrero, D., Carsteanu, A. A., Huerta, R., Clempner, J. B., 10.1016/j.cose.2018.01.005, Computers Security 74 (2018), 240-257. DOI10.1016/j.cose.2018.01.005
  18. Jain, M., Kardes, E., Kiekintveld, C., Ordoñez, F., Tambe, M., 10.1016/j.cose.2018.01.005, In: Proc. National Conference on Artificial Intelligence (AAAI), Atlanta 2010. DOI10.1016/j.cose.2018.01.005
  19. Kiekintveld, C., Jain, M., Tsai, J., Pita, J., Ordñez, F., Tambe, M., 10.1017/cbo9780511973031.008, In: Proc. Eighth International Conference on Autonomous Agents and Multiagent Systems, volume 1, Budapest 2009, pp. 689-696. DOI10.1017/cbo9780511973031.008
  20. Korzhyk, D., Yin, Z., Kiekintveld, C., Conitzer, V., Tambe, M., 10.1613/jair.3269, J. Artif. Intell. Res. 41 (2011), 297-327. MR2863313DOI10.1613/jair.3269
  21. Letchford, J., MacDermed, L., Conitzer, V., Parr, R., Isbell, C. L., 10.1145/2509002.2509011, In: Proc. Twenty-Sixth AAAI Conference on Artificial Intelligence (AAAI), Toronto 2012, pp. 1380-1386. DOI10.1145/2509002.2509011
  22. Letchford, J., Vorobeychik, Y., Optimal interdiction of attack plans., In: Proc. Twelfth International Conference of Autonomous Agents and Multi-agent Systems (AAMAS) 
  23. Paruchuri, P., Pearce, J. P., Marecki, J., Tambe, M., Ordoñez, F., Kraus, S., Playing games with security: An efficient exact algorithm for bayesian stackelberg games., In: Proc. Seventh International Conference on Autonomous Agents and Multiagent Systems, Estoril 2008, pp. 895-902. 
  24. Poznyak, A. S., 10.1016/b978-008044674-5.50015-8, Elsevier, Amsterdam 2008. MR2374025DOI10.1016/b978-008044674-5.50015-8
  25. Poznyak, A. S., Najim, K., Gomez-Ramirez, E., Self-learning Control of Finite Markov Chains., Marcel Dekker, New York 2000. MR1760540
  26. Salgado, M., Clempner, J. B., 10.1016/j.eswa.2017.12.036, Expert Systems Appl. 97 (2018), 266-275. DOI10.1016/j.eswa.2017.12.036
  27. Shieh, E., An, B., Yang, R., Tambe, M., Baldwin, C., DiRenzo, J., Maule, B., Meyer, G., 10.1609/aimag.v33i4.2401, In: Proc. 11th International Conference on Autonomous Agents and Multiagent Systems, 2012. DOI10.1609/aimag.v33i4.2401
  28. Skerker, M., Binary Bullets: The Ethics of Cyberwarfare, chapter Moral Concerns with Cyberspionage: Automated Keyword Searches and Data Mining, pp. 251-276., Oxford University Press, NY 2016. 
  29. Solis, C., Clempner, J. B., Poznyak, A. S., 10.1080/01969722.2016.1232121, Cybernetics Systems 47 (2016), 8, 650-673. DOI10.1080/01969722.2016.1232121
  30. Trejo, K. K., Clempner, J. B., Poznyak, A. S., 10.1515/amcs-2015-0026, Int. J. Appl. Math. Computer Sci. 25 (2015), 2, 337-351. MR3363520DOI10.1515/amcs-2015-0026
  31. Trejo, K. K., Clempner, J. B., Poznyak, A. S., 10.1016/j.engappai.2014.09.002, Engrg. Appl. Artif. Intell. 37 (2015), 145-153. DOI10.1016/j.engappai.2014.09.002
  32. Trejo, K. K., Clempner, J. B., Poznyak, A. S., 10.1109/cdc.2016.7799111, In: IEEE 55th Conference on Decision and Control (CDC), Las Vegas 2016, pp. 5484-5489. DOI10.1109/cdc.2016.7799111
  33. Trejo, K. K., Clempner, J. B., Poznyak, A. S., 10.14736/kyb-2016-2-0258, Kybernetika 52 (2016), 2, 258-279. MR3501161DOI10.14736/kyb-2016-2-0258
  34. Trejo, K. K., Clempner, J. B., Poznyak, A. S., 10.1016/j.apm.2016.09.001, Appl. Math. Modell. 41 (2017), 399-418. MR3580575DOI10.1016/j.apm.2016.09.001
  35. Trejo, K. K., Clempner, J. B., Poznyak, A. S., 10.1016/j.jcss.2017.12.004, J. Comput. System Sci. 95 (2018), 35-54. MR3787575DOI10.1016/j.jcss.2017.12.004
  36. Yang, R., Kiekintveld, C., Ordonez, F., Tambe, M., John, R., Improving resource allocation strategy against human adversaries in security games., In: Proc. International Joint Conference on Artificial Intelligence (IJCAI), Barcelona 2011, pp. 458-464. MR3024211
  37. Yin, Z., Jain, M., Tambe, M., Ordonez, F., Risk-averse strategies for security games with execution and observational uncertainty., In: Proc. AAAI Conference on Artificial Intelligence (AAAI), San Francisco 2011, pp. 758-763. 
  38. Yin, Z., Tambe, M., A unified method for handling discrete and continuous uncertainty in bayesian stackelberg games., In: Proc. Eleventh International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Valencia 2012, pp. 234-242. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.