Security Games with Arbitrary Schedules: A Branch-and-Price Approach

Manish Jain, Erim Kardeş, Christopher Kiekintveld, Milind Tambe, Fernando OrdóñezCambridge 2011 · DOI · OpenAlex

Abstract

Algorithms for attacker-defender Stackelberg games, resulting in randomized schedules for deploying limited security resources at airports, subways, ports, and other critical infrastructure have garnered significant research interest (Parachuri et al. 2008; Kiekintveld et al. 2009). Indeed, two important deployed security applications are using such algorithms: ARMOR and IRIS. ARMOR has been in use for over two years by Los Angeles International Airport police to generate canine-patrol and vehicle-checkpoint schedules (Pita et al., 2009). IRIS was recently deployed by the Federal Air Marshals Service (FAMS) to create flight schedules for air marshals (Tsai et al., 2009). These applications use efficient algorithms that solve large-scale games (Parachuri et al., 2008; Conitzer and Sandholm, 2006; Basilico, Gatti, and Amigoni, 2009), the latest being ERASER-C, the algorithm used in IRIS.
BibTeX
@inproceedings{jain2011security,
  author = {Manish Jain and Erim Kardeş and Christopher Kiekintveld and Milind Tambe and Fernando Ordóñez},
  title = {{Security Games with Arbitrary Schedules: A Branch-and-Price Approach}},
  booktitle = {Cambridge},
  year = {2011},
  doi = {10.1017/cbo9780511973031.009},
}

Loading related content...

Figure