Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games

ABSTRACT

In a class of games known as Stackelberg games, one agent (the leader) must commit to a strategy that can be observed by the other agent (the follower or adversary) before the adversary chooses its own strategy. We consider Bayesian Stackelberg games, in which the leader is uncertain about the types of adversary it may face. Such games are important in security domains, where, for example, a security agent (leader) must commit to a strategy of patrolling certain areas, and a robber (follower) has a chance to observe this strategy over time before choosing its own strategy of where to attack. This paper presents an efficient exact algorithm for finding the optimal strategy for the leader to commit to in these games. This algorithm, DOBSS, is based on a novel and compact mixed-integer linear programming formulation. Compared to the most efficient algorithm known previously for this problem, DOBSS is not only faster, but also leads to higher quality solutions, and does not suffer from problems of infeasibility that were faced by this previous algorithm. Note that DOBSS is at the heart of the ARMOR system that is currently being tested for security scheduling at the Los Angeles International Airport.

REFERENCES

• 1: R. W. Beard and T. W. McLain. Multiple UAV cooperative search under collision avoidance and limited range communication constraints. In IEEE CDC, 2003.
• 2: Gerald Brown , Matthew Carlyle , Javier Salmerón , Kevin Wood, Defending Critical Infrastructure, Interfaces, v.36 n.6, p.530-544, November 2006 [doi>10.1287/inte.1060.0252]
• 3: J. Brynielsson and S. Arnborg. Bayesian games for threat prediction and situation analysis. In FUSION, 2004.
• 4: J. Cardinal, M. Labbe, S. Langerman, and B. Palop. Pricing of geometric transportation networks. In 17th Canadian Conference on Computational Geometry, 2005.
• 5: 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]
• 6: D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
• 7: J. C. Harsanyi and R. Selten. A generalized Nash solution for two-person bargaining games with incomplete information. Management Science, 18(5):80--106, 1972.
• 8: Daphne Koller , Nimrod Megiddo , Bernhard von Stengel, Fast algorithms for finding randomized strategies in game trees, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.750-759, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195451]
• 9: Daphne Koller , Avi Pfeffer, Representations and solutions for game-theoretic problems, Artificial Intelligence, v.94 n.1-2, p.167-215, July 1997 [doi>10.1016/S0004-3702(97)00023-4]
• 10: Yannis A. Korilis , Aurel A. Lazar , Ariel Orda, Achieving network optima using Stackelberg routing strategies, IEEE/ACM Transactions on Networking (TON), v.5 n.1, p.161-173, Feb. 1997 [doi>10.1109/90.554730]
• 11: A. Murr. Random checks. In Newsweek National News. http://www.newsweek.com/id/43401, 28 Sept. 2007.
• 12: Praveen Paruchuri , Jonathan P. Pearce , Milind Tambe , Fernando Ordonez , Sarit Kraus, An efficient heuristic approach for security against multiple adversaries, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329344]
• 13: 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
• 14: S. Ruan, C. Meirina, F. Yu, K. R. Pattipati, and R. L. Popp. Patrolling in a stochastic environment. In 10th Intl. Command and Control Research and Tech. Symp., 2005.
• 15: T. Sandholm, A. Gilpin, and V. Conitzer. Mixed-integer programming methods for finding nash equilibria. In AAAI, 2005.
• 16: L. A. Wolsey. Integer Programming. John Wiley, 1998.

INDEX TERMS

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

General Terms:
Design, Security, Theory

Keywords:
Bayesian and Stackelberg games, game theory, security of agent systems