OSG: Opportunistic Security Game

People

Current Team

Gratefully acknowledge support of:








Motivation

Crime in transportation networks is a threat to passengers. Given the structure of these networks, crime diffuses as criminals traveling by public transportation seize opportunities to commit crimes. Criminals opportunistically react to real-time information, which means that crime diffuses dynamically. Recent research in criminology shows that crimes are often crimes of opportunity and how offenders move and mix with their potential targets or victims is a key determinant of the structure of any crime opportunity.

Hence, we introduce Opportunistic Security Game (OSG), a computational framework to recommend deployment strategies for defenders to control opportunistic crimes with three key contributions: (i) A novel model for opportunistic adversaries. (ii) A new exact algorithm EOSG to optimize defender strategies given our opportunistic adversaries. (iii) The development of a fast heuristic algorithm to solve large-scale OSG problems, exploiting a compact representation.




OSG: Opportunistic Security Game

OSG introduces a new model of adversary behavior, more in line with the opportunistic criminals that commit the majority of everyday crimes. This shift away from a highly capable and highly strategic adversary leads to more complexities in the OSG adversary model. In this model, criminals physically move among a collection of potential crime locations. His motion is quite different from a single fixed route or single fixed target that an adversary is assumed to pursue in Stackelberg Security Game, and, as a result, the criminals exhibit a stochastic pattern of movement to search for crime opportunities. In addition, criminals opportunistically react to real-time information as they move amongst targets; the real-time observations criminals make on the locations of defenders affect their movement and the probability of committing a crime. Additionally, the OSG framework incorporates anchoring-bias to model criminals' limited knowledge of defender patrol strategies.

EOSG is a new algorithm to generate randomized defender patrol schedules given the new adversary model. In OSG, the defender must commit to her patrol strategy first, after which the criminals will choose targets to attack given their belief of the defender's deployment; this belief may be based partially on observations and partially on incorrect assumptions (e.g., anchoring-bias). In OSG, criminals react to real-time information and alter their behavior accordingly. At the same time, after any given attempted attack (successful or not), criminals can remain in the system and search for another target to attack. Our objective is to find a randomized patrol strategy for the defender that optimizes their expected utility against this kind of adversary. We formulate the problem faced by the defender in OSG as a nonlinear optimization problem on a Markov chain.



COPS: the Compact OPportunistic Security state algorithm

COPS is a fast algorithm to solve large scale OSG problems. The number of states in the Markov chain for the OSG grows exponentially with the number of potential targets in the system, as well as with the number of defender resources. COPS compactly represents such states, dramatically reducing computation time, with small sacrifice in solution quality.

Publications

Title Author Published At Year Download
Modeling Crime diffusion and crime suppression on transportation networks: An initial report Chao Zhang, Albert Xin Jiang, Martin B. Short, P. Jeffrey Brantingham, Milind Tambe The AAAI Fall Symposium 2013 on Social Networks and Social Contagion (SNSC) 2013 download



Co-authors and Collaborators

2013 The Teamcore Research Group, University of Southern California ♦ Contact webmaster (Jie Zheng)