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

• DOI: 10.5555/1402298.1402348
• Publication Date: 2008-05-12
• Authors: Praveen Paruchuri; Jonathan P. Pearce; Janusz Marecki; Milind Tambe; Fernando Ordóñez; Sarit Kraus
• Keywords: Stackelberg competition; Commit; Adversary model; Bayesian game

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