312
Views
10
CrossRef citations to date
0
Altmetric
Original Articles

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

ORCID Icon
Pages 2494-2510 | Received 29 Mar 2016, Accepted 21 Aug 2017, Published online: 06 Sep 2017

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.
  • 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.
  • 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.
  • 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.
  • Antipin, A. S. (2005). An extraproximal method for solving equilibrium programming problems and games. Computational Mathematics and Mathematical Physics, 45 (11), 1893–1914.
  • 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.
  • 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.
  • Clempner, J. B. , & Poznyak, A. S. (2015). Stackelberg security games: Computing the shortest-path equilibrium. Expert Systems with Applications, 42 (8), 3967–3979.
  • 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.
  • Fang, F. , Jiang, A. , & Tambe, M. (2013). Protecting moving targets with multiple mobile resources. Journal of Artificial Intelligence Research, 48 , 583–634.
  • 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.
  • Garcia, C. B. , & Zangwill, W. I. (1981). Pathways to solutions, fixed points and equilibria . Englewood Cliffs, NJ: Prentice-Hall.
  • Guo, X. , & Hernandez-Lerma, O. (2009). Continuous-time Markov decision processes . Berlin: Springer-Verlag.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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) .
  • Poznyak, A. S. (2008). Advanced mathematical tools for automatic control engineers: Deterministic technique (Vol. 1). Amsterdam: Elsevier.
  • Poznyak, A. S. , Najim, K. , & Gomez-Ramirez, E. (2000). Self-learning control of finite Markov chains . New York, NY: Marcel Dekker.
  • 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 .
  • Tambe, M. (2011). Security and game theory: Algorithms, deployed systems, lessons learned . New York, NY: Cambridge University Press.
  • Tanaka, K. (1989). The closest solution to the shadow minimum of a cooperative dynamic game. Computers & Mathematics with Applications, 18 (1–3), 181–188.
  • Tanaka, K. , & Yokoyama, K. (1991). On ε-equilibrium point in a noncooperative n-person game. Journal of Mathematical Analysis and Applications , 160 , 413–423.
  • 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.
  • 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.
  • 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.
  • 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).
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • Zangwill, W. I. (1969). Nonlinear programming: A unified approach . Englewood Cliffs, NJ: Prentice-Hall.

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.