Algorithms for finding leader-follower equilibrium with multiple followers

The problem of ensuring security in crowded areas as well as areas of economic or political relevance has become a matter of growing interest in the last few years. The limited amount of resources i.e. money, personnel and equipment, makes it prohibitive to provide a complete coverage of the threatened targets at all the time, hence an efficient resource allocation policy is needed. Moreover, any potential attacker would be able to observe the defender’s strategy before choosing a target in order to exploit any potential weakness. A new branch of Game Theory, namely Security Games, has been successfully applied to these multiagent problems in the last decade, as a way to calculate an optimal defense policy. In this work we provide the state of the art of Security Games describing issues and theories at the basis of the algorithms which are the core of most advanced security software. A critical assumption of those algorithms is the hypothesis that only a single attacker could decide to attack a structure at the same time, then, in the second part of the work, we drop this assumption allowing the existence of multiple concurrent attackers. Under this general assumption we analyze different scenarios in which defender and attackers are allowed or not to play mixed strategies by providing an analysis of the difficulty of finding an optimal solution in the different cases.