Proceedings

Defender (Mis)coordination in Security Games

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 220-225.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

We study security games with multiple defenders. To achieve maximum security, defenders must perfectly synchronize their randomized allocations of resources. However, in real-life scenarios (such as protection of the port of Boston) this is not the case. Our goal is to quantify the loss incurred by miscoordination between defenders, both theoretically and empirically. We introduce two notions that capture this loss under different assumptions: the price of miscoordination, and the price of sequential commitment. Generally speaking, our theoretical bounds indicate that the loss may be extremely high in the worst case, while our simulations establish a smaller yet significant loss in practice.

  1. [Agmon et al., 2009] Noa Agmon, Sarit Kraus, Gal A Kaminka, and Vladimir Sadov. Adversarial uncertainty in multi-robot patrol. In IJCAI, pages 1811-1817, 2009. IJCAI
  2. [Agmon, 2010] Noa Agmon. On events in multi-robot patrol in adversarial environments. In AAMAS, pages 591-598, 2010.
  3. [Ashlagi et al., 2008] I. Ashlagi, D. Monderer, and M. Ten- nenholtz. On the value of correlation. Journal of Artificial Intelligence Research, 33(1):575-613, 2008.
  4. [Basilico et al., 2009] N. Basilico, N. Gatti, and F. Amigoni. Leader-follower strategies for robotic patrolling in envi- ronments with arbitrary topologies. In AAMAS, 2009.
  5. [Bradonjic et al., 2009] M. Bradonjic, G. Ercal-Ozkaya, A. Meyerson, and A. Roytman. On the price of media- tion. In EC, pages 315-324, 2009.
  6. [Jain et al., 2010] M. Jain, E. Kardes, C. Kiekintveld, F. Or- donez, and M. Tambe. Security games with arbitrary schedules: A branch and price approac. In AAAI, 2010.
  7. [Korzhyk et al., 2010] D. Korzhyk, V. Conitzer, and R. Parr. Complexity of computing optimal Stackelberg strategies in security resource allocation games. In Proc. of The 24th AAAI Conference on Artificial Intelligence, pages 805- 810, 2010.
  8. [Korzhyk et al., 2011a] D. Korzhyk, V. Conitzer, and R. Parr. Solving stackelberg games with uncertain observability. In AAMAS, 2011.
  9. [Korzhyk et al., 2011b] Dmytro Korzhyk, Vincent Conitzer, and Ronald Parr. Security games with multiple attacker resources. In IJCAI, 2011. IJCAI
  10. [Koutsoupias and Papadimitriou, 1999] E. Koutsoupias and C. Papadimitriou. Worst-case equilibria. In STACS, pages 404-413, 1999.
  11. [Lofberg, 2004] J. Lofberg. Yalmip: A toolbox for modeling and optimization in matlab. In CACSD, pages 284-289. IEEE, 2004.
  12. [Panel, 2011] Los Angeles Mayor's Blue Ribbon Panel. Re- port of the Mayor's Blue Ribbon Panel on airport security, 2011.
  13. [Paruchuri et al., 2008] P. Paruchuri, J. P. Pearce, J. Marecki, M. Tambe, F. Ordonez, and S. Kraus. Playing games for security: An efficient exact algorithm for solving bayesian stackelberg games. In AAMAS, 2008.
  14. [Powell, 2007] R. Powell. Defending against terrorist attacks with limited resources. American Political Science Re- view, 101(3):527-541, 2007.
  15. [Roughgarden and Tardos, 2002] T. Roughgarden and É. Tardos. How bad is selfish routing? Journal of the ACM, 49(2):236-259, 2002.
  16. [Shieh et al., 2012] E. Shieh, B. An, R. Yang, M. Tambe, C. Baldwin, J. DiRenzo, B. Maule, and G. Meyer. Protect: A deployed game theoretic system to protect the ports of the united states. In AAMAS, 2012.
  17. [Tambe, 2011] M. Tambe. Security and Game Theory: Algo- rithms, Deployed Systems, Lessons Learned. Cambridge University Press, New York, NY, 2011.
  18. [Yin et al., 2010] Z. Yin, D. Korzhyk, C. Kiekintveld, V. Conitzer, and M. Tambe. Stackelberg vs. nash in secu- rity games: Interchangeability, equivalence, and unique- ness. In AAMAS, 2010.

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

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