Proceedings

Catcher-Evader Games

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 329-336.

© 2016 International Joint Conferences on Artificial Intelligence

Abstract

Algorithms for computing game-theoretic solutions have recently been applied to a number of security domains. However, many of the techniques developed for compact representations of security games do not extend to Bayesian security games, which allow us to model uncertainty about the attacker's type. In this paper, we introduce a general framework of catcher-evader games that can capture Bayesian security games as well as other game families of interest. We show that computing Stackelberg strategies is NP-hard, but give an algorithm for computing a Nash equilibrium that performs well in experiments. We also prove that the Nash equilibria of these games satisfy the interchangeability property, so that equilibrium selection is not an issue.

  1. [An et al., 2012] Bo An, Eric Shieh, Milind Tambe, Rong Yang, Craig Baldwin, Joseph DiRenzo, Ben Maule, and Garrett Meyer. PROTECT -A deployed game theo- retic system for strategic security allocation for the United States Coast Guard. AI Magazine, 33(4):96-110, 2012.
  2. [Birkhoff, 1946] Garrett Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucumn Rev, Ser. A, no. 5, pages 147-151, 1946.
  3. [Borie et al., 2009] Richard B Borie, Craig A Tovey, and Sven Koenig. Algorithms and complexity results for pursuit-evasion problems. In IJCAI, volume 9, pages 59- 66, 2009. IJCAI
  4. [Kiekintveld et al., 2009] Christopher Kiekintveld, Manish Jain, Jason Tsai, James Pita, Fernando Ordóñez, and Milind Tambe. Computing optimal randomized resource allocations for massive security games. In Proceedings of the Eighth International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 689- 696, Budapest, Hungary, 2009.
  5. [Korzhyk et al., 2010] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. Complexity of computing optimal Stack- elberg strategies in security resource allocation games. In Proceedings of the National Conference on Artificial Intel- ligence (AAAI), pages 805-810, Atlanta, GA, USA, 2010.
  6. [Korzhyk et al., 2011a] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. Security games with multiple attacker resources. In Proceedings of the Twenty-Second Interna- tional Joint Conference on Artificial Intelligence (IJCAI), pages 273-279, Barcelona, Catalonia, Spain, 2011. IJCAI
  7. [Korzhyk et al., 2011b] Dmytro Korzhyk, Zhengyu Yin, Christopher Kiekintveld, Vincent Conitzer, and Milind Tambe. Stackelberg vs. Nash in security games: An extended investigation of interchangeability, equivalence, and uniqueness. Journal of Artificial Intelligence Re- search, 41(2):297-327, 2011.
  8. [Li and Conitzer, 2013] Yuqian Li and Vincent Conitzer. Game-theoretic question selection for tests. In Proceed- ings of the Twenty-Third International Joint Conference on Artificial Intelligence (IJCAI), pages 254-262, Beijing, China, 2013. IJCAI
  9. [Parsons, 1978] Torrence D Parsons. Pursuit-evasion in a graph. In Theory and applications of graphs, pages 426- 441. Springer, 1978.
  10. [Paruchuri et al., 2008] Praveen Paruchuri, Jonathan P. Pearce, Janusz Marecki, Milind Tambe, Fernando Ordóñez, and Sarit Kraus. Playing games for security: An efficient exact algorithm for solving Bayesian Stackelberg games. In Proceedings of the Seventh International Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), pages 895-902, Estoril, Portugal, 2008.
  11. [Pita et al., 2009a] James Pita, Manish Jain, Fernando Ordóñez, Christopher Portway, Milind Tambe, and Craig Western. Using game theory for Los Angeles airport secu- rity. AI Magazine, 30(1):43-57, 2009.
  12. [Pita et al., 2009b] James Pita, Manish Jain, Fernando Ordóñez, Christopher Portway, Milind Tambe, Craig Western, Praveen Paruchuri, and Sarit Kraus. Using game theory for Los Angeles airport security. AI Magazine, 30(1):43-57, 2009.
  13. [Tsai et al., 2009] Jason Tsai, Shyamsunder Rathi, Christo- pher Kiekintveld, Fernando Ordóñez, and Milind Tambe. IRIS -A tool for strategic security allocation in trans- portation networks. In Proceedings of the Eighth Interna- tional Joint Conference on Autonomous Agents and Multi- Agent Systems (AAMAS), pages 37-44, Budapest, Hun- gary, 2009.
  14. [Yin et al., 2012] Zhengyu Yin, Albert Xin Jiang, Milind Tambe, Christopher Kiekintveld, Kevin Leyton-Brown, Tuomas Sandholm, and John P. Sullivan. TRUSTS: Scheduling randomized patrols for fare inspection in tran- sit systems using game theory. AI Magazine, 33(4):59-72, 2012.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards