The border patrol game
Creators: name: Darlington, Matthew
Publisher: name: Lancaster University
Year: 2024

description: The issue of how best to patrol a border can be found in many settings.
 Important examples include protecting important infrastructure such as
 airports, preventing the smuggling of illicit items, or defending
 computers in a network. This thesis contributes to the existing literature
 by developing two unique models for border patrol. 
 
 We begin by introducing a model where a group of smugglers play a game
 against a single patroller. We investigate how communication and
 cooperation between the smugglers affect the equilibria in the game.
 Smugglers are located at different locations along a border and, for each
 smuggler, a decision is made about whether they will attack.
 Simultaneously, the patroller chooses one of the locations to defend.
 Smugglers obtain rewards for making successful attacks, but incur penalty
 costs if they are caught by the patroller. The reward to an individual
 smuggler for making a successful attack decreases with the total number of
 successful attacks made, so that the smugglers obtain diminishing marginal
 returns as they smuggle larger quantities of items. We define equilibria
 in three different cases: selfish smugglers without communication, selfish
 smugglers with communication, and cooperative smugglers. We study the
 equilibria in each case and establish properties of the associated
 smuggler and patroller strategies. We show that communication and
 cooperation both tend to improve the smugglers’ expected returns, while
 (perhaps counter-intuitively) the smugglers attack less often when they
 are cooperating than when they are communicating but acting selfishly. 
 
 Our second model considers a similar problem to the first, but we make
 some important changes to the game. We simplify the payoff structure of
 the model, however, we are then able to study a repeated game with
 inter-temporal dependence. The application of the model is examining a
 group of cooperating smugglers who make 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. 
 
 Furthermore, we introduce a multiple patroller extension to the second
 model. The addition of multiple patrollers increases the complexity of the
 game, and exactly finding Nash equilibria becomes an even more complex
 task. We describe how we model the multiple patroller extension, and
 detail why previous methods for the single patroller game no longer apply.
 Three different techniques to study the game are then discussed. Firstly,
 we look at a method using subgradient descent to try to find the exact
 Nash equilibrium in the game. Secondly, we look at two different
 heuristics for the patroller’s strategy. We first consider the myopic
 strategy for the patrollers, and then introduce a method of partitioning
 the border into multiple segments each defended by one patroller. The
 performance of the heuristics is numerically investigated and used to
 evaluate the convergence of the subgradient method. Finally, we discuss
 how reinforcement learning can be applied to our model. We consider two
 different reinforcement learning approaches, fictitious play and
 Q-learning, and then provide a numerical analysis of the resulting player
 behaviours. We conclude with several directions of further work for the
 multiple patroller problem.