Counterfactual Regret Minimization in Sequential Security Games

Game theory has become a common tool to model many real-world security problems, such as protecting airports or airplanes from terrorist attacks, preventing fare evaders form misusing public transport, preventing attacks in... [ view full abstract ]

Game theory has become a common tool to model many real-world security problems, such as protecting airports or airplanes from terrorist attacks, preventing fare evaders form misusing public transport, preventing attacks in computer networks, or protecting wildlife from poachers. Recent game theory research has yielded significant progress in solving massive imperfect information extensive-form games. In particular, counterfactual regret minimization (CFR) has emerged from the computer poker research community as a standard technique for solving massive poker games. However, there has not been any transfer of these results to research on real-world security problems. We examine an abstract class of sequential games, called normal-form games with sequential strategies (NFGSS), that can model many sequential security games, such as games taking place in physical space that can be discretized as a graph. We prove that all games from this class can be modelled can be solved by counterfactual regret minimization. We then show how to adapt the CFR+ algorithm directly to NFGSS and empirically validate our approach on two security-inspired domains. We show that with a negligible loss in precision, CFR+ can compute a Nash equilibrium with five times less computation than methods traditionally used in research on security games.