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

Manish Jain · Erim Kardeş · Christopher D. Kiekintveld · Milind Tambe · Fernando Ordóñez

124 citations0/0 files storedCambridge University Press eBooks

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Game Theory and Applications Information and Cyber Security Military Defense Systems Analysis

Abstract

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 124 citations exist upstream.

References

2006Computing the optimal strategy to commit to 2008Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games 1978On generalized Stackelberg strategies 2021Responsibility Research for Trustworthy Autonomous Systems (Blue Sky Ideas Track)1988Sequential Stackelberg equilibria in two-person games 2010Complexity of Computing Optimal Stackelberg Strategies in Security Resource Allocation Games 2004Leadership with commitment to mixed strategies

Cited by

2011GUARDS and PROTECT 2011Solving Stackelberg games with uncertain observability 2011Quality-bounded solutions for finite Bayesian Stackelberg games: scaling up 2011Refinement of Strong Stackelberg Equilibria in Security Games 2016One Size Does Not Fit All: A Game-Theoretic Approach for Dynamically and Effectively Screening for Threats 2013Security games with interval uncertainty 2014A Stackelberg security game with random strategies based on the extraproximal theoretic approach

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.