A continuous-time Markov Stackelberg security game approach for reasoning about real patrol strategies

References

• Agmon, N. , Kaminka, G. A. , & Kraus, S. (2011). Multi-robot adversarial patrolling: Facing a full-knowledge opponent. Journal of Artificial Intelligence Research, 42 (1), 887–916.
   Google Scholar
• An, B. , Kempe, D. , Kiekintveld, C. , Shieh, E. , Singh, S. , & Tambe, M. (2012). Security games with limited surveillance. In Proceedings of the Twenty-Sixth AAAI conference on artificial intelligence (AAAI) (pp. 1241–1247). Toronto.
   Google Scholar
• An, B. , Pita, J. , Shieh, E. , Tambe, M. , Kiekintveld, C. , & Marecki, J. (2011). GUARDS and PROTECT: Next generation applications of security games. SIGECOM, 10 , 31–34.
   Google Scholar
• An, B. , Tambe, M. , Ordonez, F. , Shieh, E. , & Kiekintveld, C. (2011). Refinement of strong Stackelberg equilibria in security games. In Proceedings of the twenty-fifth conference for the advancement of artificial intelligence (AAAI) (pp. 587–593). San Francisco, CA.
   Google Scholar
• Antipin, A. S. (2005). An extraproximal method for solving equilibrium programming problems and games. Computational Mathematics and Mathematical Physics, 45 (11), 1893–1914.
   Google Scholar
• Basilico, N. , Gatti, N. , & Villa, F. (2010). Asynchronous multi-robot patrolling against intrusions in arbitrary topologies. In Proceeding of the conference for the advancement of artificial intelligence (AAAI) (pp. 345–350). Atlanta, GA.
   Google Scholar
• Clempner, J. B. , & Poznyak, A. S. (2014). Simple computing of the customer lifetime value: A fixed local-optimal policy approach. Journal of Systems Science and Systems Engineering, 23 (4), 439–459.
   Web of Science ®Google Scholar
• Clempner, J. B. , & Poznyak, A. S. (2015). Stackelberg security games: Computing the shortest-path equilibrium. Expert Systems with Applications, 42 (8), 3967–3979.
   Web of Science ®Google Scholar
• Dickerson, J. P. , Simari, G. I. , Subrahmanian, V. S. , & Kraus, S. (2010). A graph-theoretic approach to protect static and moving targets from adversaries. In Proceedings of the ninth international joint conference on autonomous agents and multiagent systems (pp. 299–306). Toronto.
   Google Scholar
• Fang, F. , Jiang, A. , & Tambe, M. (2013). Protecting moving targets with multiple mobile resources. Journal of Artificial Intelligence Research, 48 , 583–634.
   Web of Science ®Google Scholar
• Fave, F. M. D. , Jiang, A. X. , Yin, Z. , Zhang, C. , Tambe, M. , Kraus, S. , & Sullivan, J. (2014). Game-theoretic security patrolling with dynamic execution uncertainty and a case study on a real transit system. Journal of Artificial Intelligence Research, 50 , 321–367.
   Web of Science ®Google Scholar
• Garcia, C. B. , & Zangwill, W. I. (1981). Pathways to solutions, fixed points and equilibria . Englewood Cliffs, NJ: Prentice-Hall.
   Google Scholar
• Guo, X. , & Hernandez-Lerma, O. (2009). Continuous-time Markov decision processes . Berlin: Springer-Verlag.
   Google Scholar
• Haskell, W. B. , Kar, D. , Fang, F. , Tambe, M. , Cheung, S. , & Denicola, L. E. (2014). Robust protection of fisheries with compass. In The twenty-sixth annual conference on innovative applications of artificial intelligence . Quebec.
   Google Scholar
• Hernández, E. , Barrientos, A. , & Del Cerro, J. (2014). Selective smooth fictitious play: An approach based on game theory for patrolling infrastructures with a multi-robot system. Expert Systems with Applications, 41 (6), 2897–2913.
   Web of Science ®Google Scholar
• Jain, M. , Kardes, E. , Kiekintveld, C. , Ordoñez, F. , & Tambe, M. (2010). Security games with arbitrary schedules: A branch and price approach. In Proceedings of the national conference on artificial intelligence (AAAI) . Atlanta, GA.
   Google Scholar
• Jain, M. , Kiekintveld, C. , & Tambe, M. (2011). Quality-bounded solutions for finite Bayesian Stackelberg games: Scaling up. In Proceedings of the tenth international joint conference on autonomous agents and multi-agent systems (AAMAS) (pp. 997–1004). Taipei.
   Google Scholar
• Jiang, A. X. , Yin, Z. , Zhang, C. , Tambe, M. , & Kraus, S. (2013). Game-theoretic randomization for security patrolling with dynamic execution uncertainty. In Proceedings of the international conference on autonomous agents and multi-agent systems (AAMAS) (pp. 207–214). Saint Paul, MN.
   Google Scholar
• Korzhyk, D. , Conitzer, V. , & Parr, R. (2011a). Security games with multiple attacker resources. In Proceedings of the twenty-second international joint conference on artificial intelligence (IJCAI) (pp. 273–279). Barcelona.
   Google Scholar
• Korzhyk, D. , Conitzer, V. , & Parr, R. (2011b). Solving Stackelberg games with uncertain observability. In Proceedings of the tenth international conference on agents and multi-agent systems (AAMAS) (pp. 1013–1020). Taipei.
   Google Scholar
• Korzhyk, D. , Yin, Z. , Kiekintveld, C. , Conitzer, V. , & Tambe, M. (2011). Stackelberg vs. Nash in security games: An extended investigation of interchangeability equivalence, and uniqueness. Journal of Artificial Intelligence Research, 41 , 297–327.
   Web of Science ®Google Scholar
• Letchford, J. , & Conitzer, V. (2013). Solving security games on graphs via marginal probabilities. In Proceedings of the AAAI conference on artificial intelligence (AAAI) (pp. 591–597). Bellevue, WA.
   Google Scholar
• Letchford, J. , MacDermed, L. , Conitzer, V. , Parr, R. , & Isbell, C. (2012). Computing optimal strategies to commit to in stochastic games. In Proceedings of the national conference on artificial intelligence (AAAI) (pp. 1380–1386). Toronto.
   Google Scholar
• Letchford, J. , & Vorobeychik, Y. (2013). Optimal interdiction of attack plans. In Proceedings of the twelfth international conference of autonomous agents and multi-agent systems (AAMAS) (pp. 199–206). Saint Paul, MN.
   Google Scholar
• Nguyen, T. H. , Yang, R. , Azaria, A. , Kraus, S. , & Tambe, M. (2013). Analyzing the effectiveness of adversary modeling in security games. In Proceedings of the AAAI conference on artificial intelligence (AAAI) (pp. 718–724). Bellevue, WA.
   Google Scholar
• Pita, J. , Jain, M. , Ordoñez, F. , Portwa, C. , Tambe, M. , & Western, C. (2009). Using game theory for Los Angeles airport security. AI Magazine, 30 (1), 43–57.
   Web of Science ®Google Scholar
• Pita, J. , Tambe, M. , Kiekintveld, C. , Cullen, S. , & Steigerwald, E. (2011). Guards-game theoretic security allocation on a national scale. In Proceedings of the 10th international conference on autonomous agents and multiagent systems (AAMAS) .
   Google Scholar
• Poznyak, A. S. (2008). Advanced mathematical tools for automatic control engineers: Deterministic technique (Vol. 1). Amsterdam: Elsevier.
   Google Scholar
• Poznyak, A. S. , Najim, K. , & Gomez-Ramirez, E. (2000). Self-learning control of finite Markov chains . New York, NY: Marcel Dekker.
   Google Scholar
• Shieh, E. , An, B. , Yang, R. , Tambe, M. , Baldwin, C. , DiRenzo, J. , Meyer, G. (2012). Protect: A deployed game theoretic system to protect the ports of the united states. In Proceedings of the 11th international conference on autonomous agents and multiagent systems .
   Google Scholar
• Tambe, M. (2011). Security and game theory: Algorithms, deployed systems, lessons learned . New York, NY: Cambridge University Press.
   Google Scholar
• Tanaka, K. (1989). The closest solution to the shadow minimum of a cooperative dynamic game. Computers & Mathematics with Applications, 18 (1–3), 181–188.
   Web of Science ®Google Scholar
• Tanaka, K. , & Yokoyama, K. (1991). On ε-equilibrium point in a noncooperative n-person game. Journal of Mathematical Analysis and Applications , 160 , 413–423.
   Web of Science ®Google Scholar
• Trejo, K. K. , Clempner, J. B. , & Poznyak, A. S. (2015a). Computing the Stackelberg/Nash equilibria using the extraproximal method: Convergence analysis and implementation details for Markov chains games. International Journal of Applied Mathematics and Computer Science, 25 (2), 337–351.
   Web of Science ®Google Scholar
• Trejo, K. K. , Clempner, J. B. , & Poznyak, A. S. (2015b). A Stackelberg security game with random strategies based on the extraproximal theoretic approach. Engineering Applications of Artificial Intelligence, 37 , 145–153.
   Web of Science ®Google Scholar
• Trejo, K. K. , Clempner, J. B. , & Poznyak, A. S. (2016). An optimal strong equilibirum solution for cooperative multi-leader–follower Stackelberg Markov chains games. Kibernetika, 52 (2), 258–279.
   Web of Science ®Google Scholar
• Tsai, J. , Rathi, S. , Kiekintveld, C. , Ordoñez, F. , & Tambe, M. (2009). Iris – A tool for strategic security allocation in transportation networks. In Eighth international conference on autonomous agents and multiagent systems – industry track (pp. 37–44).
   Google Scholar
• Varakantham, P. , Lau, H. C. , & Yuan, Z. (2013). Scalable randomized patrolling for securing rapid transit networks. In Proceedings of the conference for innovative applications for artificial intelligence (IAAI) (pp. 1563–1568). Bellevue, WA.
   Google Scholar
• Yang, R. , Ford, B. , Tambe, M. , & Lemieux, A. (2014). Adaptive resource allocation for wildlife protection against illegal poachers. In International conference on autonomous agents and multiagent systems . Paris.
   Google Scholar
• Yang, R. , Kiekintveld, C. , Ordonez, F. , Tambe, M. , & John, R. (2011). Improving resource allocation strategy against human adversaries in security games. In Proceedings of the international joint conference on artificial intelligence (IJCAI) (pp. 458–464). Barcelona.
   Google Scholar
• Yin, Z. , Jain, M. , Tambe, M. , & Ordonez, F. (2011). Risk-averse strategies for security games with execution and observational uncertainty. In Proceedings of the AAAI conference on artificial intelligence (AAAI) (pp. 758–763). San Francisco, CA.
   Google Scholar
• Yin, Z. , Jiang, A. , Johnson, M. , Tambe, M. , Kiekintveld, C. , Leyton-Brown, K. , Sullivan, J. (2012). Trusts: Scheduling randomized patrols for fare inspection in transit systems. In The twenty-fourth annual conference on innovative applications for artificial intelligence . Toronto.
   Google Scholar
• Yin, Z. , & Tambe, M. (2012). A unified method for handling discrete and continuous uncertainty in Bayesian Stackelberg games. In Proceedings of the eleventh international conference on autonomous agents and multiagent systems (AAMAS) (pp. 234–242). Valencia.
   Google Scholar
• Yuan, Y. , Sun, F. , & Liu, H. (2016). Resilient control of cyber-physical systems against intelligent attacker: A hierarchal Stackelberg game approach. International Journal of Systems Science , 47(9), 2067–2077.
   Web of Science ®Google Scholar
• Zangwill, W. I. (1969). Nonlinear programming: A unified approach . Englewood Cliffs, NJ: Prentice-Hall.
   Google Scholar