A stochastic game framework for patrolling a border

DOI10.1016/J.EJOR.2023.06.011MaRDI QIDQ6096639zbMATH OpenOpenAlexFDO

Authors Matthew Darlington, Kevin D. Glazebrook, D. S. Leslie, Rob Shone, Roberto Szechtman

Publication date 15 September 2023

Published in European Journal of Operational Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2205.10017

zbMATH Keywords

game theoryOR in defencepatrol problems

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: In this paper we consider a stochastic game for modelling the interactions between smugglers and a patroller along a border. The problem we examine involves a group of cooperating smugglers making regular attempts to bring small amounts of illicit goods across a border. A single patroller has the goal of preventing the smugglers from doing so, but must pay a cost to travel from one location to another. We model the problem as a two-player stochastic game and look to find the Nash equilibrium to gain insight to real world problems. Our framework extends the literature by assuming that the smugglers choose a continuous quantity of contraband, complicating the analysis of the game. We discuss a number of properties of Nash equilibria, including the aggregation of smugglers, the discount factors of the players, and the equivalence to a zero-sum game. Additionally, we present algorithms to find Nash equilibria that are more computationally efficient than existing methods. We also consider certain assumptions on the parameters of the model that give interesting equilibrium strategies for the players.

Recommendations

• Solving partially observable agent-intruder games with an application to border security problems
• Dynamical and Game-Theoretical Approaches to an Optimal Patrol Problem
• On dynamic patrolling security games
• A continuous-time Markov Stackelberg security game approach for reasoning about real patrol strategies
• Handling a Kullback--Leibler divergence random walk for scheduling effective patrol strategies in Stackelberg security games
• Securing gates of a protected area: a hybrid game and queueing theory modeling approach
• Patrolling security games: definition and algorithms for solving large instances with single patroller and single intruder
• Border-collision bifurcations in a dynamic management game
• A Class of Stochastic Games and Moving Free Boundary Problems

Cites work

• A generalized inspection game
• A graph patrol problem with random attack times
• A remark on the customs and smuggler game
• Adaptive policies for perimeter surveillance problems
• Adversarial patrolling in a uniform
• Discrete Optimization Via Marginal Analysis
• Equilibrium points in n -person games
• Evolutionary Games and Population Dynamics
• scientific article; zbMATH DE number 2067965 (Why is no real title available?)
• scientific article; zbMATH DE number 1391661 (Why is no real title available?)
• scientific article; zbMATH DE number 3247810 (Why is no real title available?)
• Lower and Upper Bounds for the Allocation Problem and Other Nonlinear Optimization Problems
• On stochastic games
• Optimal patrol to uncover threats in time when detection is imperfect
• Optimizing periodic patrols against short attacks on the line and other networks
• Patrolling a border
• Patrolling games
• Player aggregation in the traveling inspector model
• Stochastic Games
• Technical note -- Optimal patrol of a perimeter
• The traveling inspector model

Cited in

(2)

• Handling a Kullback--Leibler divergence random walk for scheduling effective patrol strategies in Stackelberg security games
• A direct reduction from stochastic parity games to simple stochastic games

This page was built for publication: A stochastic game framework for patrolling a border

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6096639)