Book contents
- Frontmatter
- Contents
- Acknowledgments
- 1 Introduction and Overview of Security Games
- PART I SECURITY EXPERTS' PERSPECTIVES
- PART II DEPLOYED APPLICATIONS
- PART III EFFICIENT ALGORITHMS FOR MASSIVE SECURITY GAMES
- 7 Coordinating Randomized Policies for Increasing the Security of Agent Systems
- 8 Computing Optimal Randomized Resource Allocations for Massive Security Games
- 9 Security Games with Arbitrary Schedules: A Branch-and-Price Approach
- PART IV FUTURE RESEARCH
- PART V SHORT BIOS
- References
- Index
- References
9 - Security Games with Arbitrary Schedules: A Branch-and-Price Approach
from PART III - EFFICIENT ALGORITHMS FOR MASSIVE SECURITY GAMES
Published online by Cambridge University Press: 05 January 2012
- Frontmatter
- Contents
- Acknowledgments
- 1 Introduction and Overview of Security Games
- PART I SECURITY EXPERTS' PERSPECTIVES
- PART II DEPLOYED APPLICATIONS
- PART III EFFICIENT ALGORITHMS FOR MASSIVE SECURITY GAMES
- 7 Coordinating Randomized Policies for Increasing the Security of Agent Systems
- 8 Computing Optimal Randomized Resource Allocations for Massive Security Games
- 9 Security Games with Arbitrary Schedules: A Branch-and-Price Approach
- PART IV FUTURE RESEARCH
- PART V SHORT BIOS
- References
- Index
- References
Summary
Introduction
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.
Unfortunately, current state-of-the art algorithms for Stackelberg games are inadequate for many applications. For example, U.S. carriers fly over 27,000 domestic and 2,000 international flights daily, presenting a massive scheduling challenge for FAMS. IRIS addresses an important part of this space – the international sector – but only considers schedules with a single departure and return flight. The ERASER-C algorithm used in this application does not provide correct solutions for longer and more complex tours (which are common in the domestic sector). In fact, recent complexity results show that the problem of finding Stackelberg equibria with general scheduling constraints is NP-hard (Korzhyk, Conitzer, and Parr, 2010) and can be solved in polynomial time only for restricted cases.
- Type
- Chapter
- Information
- Security and Game TheoryAlgorithms, Deployed Systems, Lessons Learned, pp. 177 - 190Publisher: Cambridge University PressPrint publication year: 2011
References
- 11
- Cited by