Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Predictable allocations of security resources such as police officers, canine units, or checkpoints are vulnerable to exploitation by attackers. Recent work has applied game-theoretic methods to find optimal randomized security policies, including a fielded application at the Los Angeles International Airport (LAX). This approach has promising applications in many similar domains, including police patrolling for subway and bus systems, randomized baggage screening, and scheduling for the Federal Air Marshal Service (FAMS) on commercial flights. However, the existing methods scale poorly when the security policy requires coordination of many resources, which is central to many of these potential applications.

We develop new models and algorithms that scale to much more complex instances of security games. The key idea is to use a compact model of security games, which allows exponential improvements in both memory and runtime relative to the best known algorithms for solving general Stackelberg games. We develop even faster algorithms for security games under payoff restrictions that are natural in many security domains. Finally, introduce additional realistic scheduling constraints while retaining comparable performance improvements. The empirical evaluation comprises both random data and realistic instances of the FAMS and LAX problems. Our new methods scale to problems several orders of magnitude larger than the fastest known algorithm.

REFERENCES

• 1: R. Avenhaus, B. von Stengel, and S. Zamir. Inspection games. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory, volume 3, chapter 51, pages 1947--1987. North-Holland, Amsterdam, 2002.
• 2: T. Basar and G. J. Olsder. Dynamic Noncooperative Game Theory. Academic Press, San Diego, CA, 2nd edition, 1995.
• 3: M. Breton , A. Alj , A. Haurie, Sequential Stackelberg equilibria in two-person games, Journal of Optimization Theory and Applications, v.59 n.1, p.71-94, October 1988 [doi>10.1007/BF00939867]
• 4: Vincent Conitzer , Tuomas Sandholm, Computing the optimal strategy to commit to, Proceedings of the 7th ACM conference on Electronic commerce, p.82-90, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134717]
• 5: Nicola Gatti, Game Theoretical Insights in Strategic Patrolling: Model and Algorithm in Normal-Form, Proceeding of the 2008 conference on ECAI 2008: 18th European Conference on Artificial Intelligence, p.403-407, June 27, 2008
• 6: Albert Xin Jiang , Kevin Leyton-Brown, A polynomial-time algorithm for action-graph games, Proceedings of the 21st national conference on Artificial intelligence, p.679-684, July 16-20, 2006, Boston, Massachusetts
• 7: D. Koller and B. Milch. Multi-agent influence diagrams for representing and solving games. Games and Economic Behavior, 45(1):181--221, 2003.
• 8: G. Leitmann. On generalized Stackelberg strategies. Optimization Theory and Applications, 26(4):637--643, 1978.
• 9: R. D. Luce and H. Raiffa. Games and Decisions. John Wiley and Sons, New York, 1957. Dover republication 1989.
• 10: M. J. Osbourne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 11: Praveen Paruchuri , Jonathan P. Pearce , Janusz Marecki , Milind Tambe , Fernando Ordonez , Sarit Kraus, Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems, May 12-16, 2008, Estoril, Portugal
• 12: James Pita , Manish Jain , Janusz Marecki , Fernando Ordóñez , Christopher Portway , Milind Tambe , Craig Western , Praveen Paruchuri , Sarit Kraus, Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport, Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track, May 12-16, 2008, Estoril, Portugal
• 13: Tim Roughgarden, Stackelberg Scheduling Strategies, SIAM Journal on Computing, v.33 n.2, p.332-350, 2004 [doi>10.1137/S0097539701397059]
• 14: Todd Sandler , Daniel G. Arce M., Terrorism & Game Theory, Simulation and Gaming, v.34 n.3, p.319-337, September 2003 [doi>10.1177/1046878103255492]
• 15: V. Srivastava, J. Neel, A. B. MacKenzie, R. Menon, L. A. Dasilva, J. E. Hicks, J. H. Reed, and R. P. Gilles. Using game theory to analyze wireless ad hoc networks. IEEE Communications Surveys and Tutuorials, 7(4), 2005.
• 16: H. von Stackelberg. Marktform und Gleichgewicht. Springer, Vienna, 1934.
• 17: B. von Stengel and S. Zamir. Leadership with commitment to mixed strategies. Technical Report LSE-CDAM-2004-01, CDAM Research Report, 2004.
• 18: K. wei Lye and J. M. Wing. Game strategies in network security. International Journal of Information Security, 4(1--2):71--86, 2005.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Intelligent agents

General Terms:
Algorithms, Experimentation, Performance, Security, Theory

Keywords:
Stackelberg games, algorithms, game theory, patrolling, randomization, risk analysis, security, uncertainty