A Deployed Quantal Response-Based Patrol Planning System for the U.S. Coast Guard

Abstract

In this paper, we describe the model, theory developed, and deployment of PROTECT, a game-theoretic system that the United States Coast Guard (USCG) uses to schedule patrols in the Port of Boston. The USCG evaluated PROTECT’s deployment in the Port of Boston as a success and is currently evaluating the system in the Port of New York, with the potential for nationwide deployment. PROTECT is premised on an attacker-defender Stackelberg game model; however, its development and implementation required both theoretical contributions and detailed evaluations. We describe the work required in the deployment, which we group into five key innovations. First, we propose a compact representation of the defender’s strategy space by exploiting equivalence and dominance, to make PROTECT efficient enough to solve real-world sized problems. Second, this system does not assume that adversaries are perfectly rational, a typical assumption in previous game-theoretic models for security. Instead, PROTECT relies on a quantal response (QR) model of the adversary’s behavior. We believe this is the first real-world deployment of a QR model. Third, we develop specialized solution algorithms that can solve this problem for real-world instances and give theoretical guarantees. Fourth, our experimental results illustrate that PROTECT’s QR model handles real-world uncertainties more robustly than a perfect-rationality model. Finally, we present (1) a comparison of human-generated and PROTECT security schedules, and (2) results of an evaluation of PROTECT from an analysis by human mock attackers.