Scheduling Bodyguards

ABSTRACT Security agencies around the world use bodyguards to protect government officials and public figures. In this paper, we consider a two‐person zero‐sum game between a defender who allocates such bodyguards to protect several targets and an attacker who chooses one target to attack. Because the number of feasible bodyguard allocations grows quickly as either the number of targets or the number of bodyguards increases, solving the game by brute force with a linear program becomes computationally intractable for problems of practical size. By assuming that the marginal benefit of each additional bodyguard assigned to a target is nonincreasing, we show that we can solve the game with a different linear program whose size is linear in the number of targets and the number of bodyguards, respectively. Next, we extend the allocation game to a scheduling game, which allows a bodyguard to report to multiple targets if their schedules allow. We develop an algorithm to compute a bound on the value of this bodyguard scheduling game and present a mixed strategy that achieves this bound in all numerical experiments. Through a case study, we demonstrate how our bodyguard games can be deployed in the Netherlands.