Methods for finding leader-follower equilibria with multiple followers

Recently, the problem of securing particularly crowded places or politically, economically, and culturally relevant targets is becoming paramount. In fact, the risk that these places are attacked by either organized terrorist groups or dangerous and unpredictable people is steadily increasing. Protecting such sensible targets ensuring the maximum security level requires huge financial investments. Unfortunately, in most cases the interested entities cannot afford these costs entirely, so that the resources available for security are not sufficient to guarantee a complete protection. This raises a new problem, the one of efficiently allocating available resources to ensure the highest possible level of protection. However, this is a difficult problem to solve, because it requires the analysis of many variables and possibilities, thus it is not suited to be solved manually. This led to the birth of a new branch of Artificial Intelligence, whose aim is to develop IT systems able to autonomously compute optimal defence strategies, reducing human intervention to a minimum. This new area of research finds its foundations in Game Theory, introducing new game models, usually known as Security Games, and developing algorithms to solve them. In this field, a particular solution concept has been established, called Leader-Follower equilibrium, in which the leader takes the role of defender, while the follower plays as attacker, under the assumption that the latter can observe the defender’s strategy beforehand. The Leader-Follower equilibrium in its simplest form, which considers only one leader and one follower, has already been largely studied. The purpose of this thesis is to extend such study, considering the case with multiple followers who play a Nash equilibrium. We prove that the problem, in the most general form, is computationally hard, being NP-Hard and not in Poly-APX. For this reason, we identify several special cases, for instance narrowing the strategy space or considering games with a particular structure, in an attempt to identify situations in which the problem is easier. For each considered case, we propose specific algorithms which are, then, experimentally evaluated.

Negli ultimi tempi il problema di mettere in sicurezza luoghi particolarmente affollati o rilevanti da un punto di vista politico, economico e culturale sta diventando di primaria importanza. Infatti, il rischio che questi luoghi siano colpiti da attacchi organizzati da gruppi terroristici o portati a termine da persone pericolose e imprevedibili sta costantemente aumentando. Proteggere tali obbiettivi sensibili garantendo il massimo livello di sicurezza richiede grossi investimenti economici. Sfortunatamente, nella maggior parte dei casi questi costi risultano impossibili da sostenere per le entità interessante, quindi le risorse a disposizione per la sicurezza non sono sufficienti a garantire una protezione completa. Si pone dunque un nuovo problema, quello di allocare in modo efficiente le risorse a disposizione in modo da assicurare il massimo livello di protezione possibile. Tuttavia questo è un problema difficile da risolvere, poiché richiede l’analisi di diverse variabili e possibilità; quindi non si presta ad essere risolto manualmente. Questo ha portato alla nascita di un nuovo ramo dell’Intelligenza Artificiale, il cui scopo è quello di sviluppare sistemi in grado di calcolare autonomamente una strategia di difesa ottima, riducendo al minimo l’intervento umano. Questa nuova branca di ricerca trae le sue basi dalla Teoria dei Giochi, introducendo nuovi modelli di gioco, solitamente detti Security Games, e sviluppando algoritmi per risolverli (cioè, calcolarne gli equilibri). In questo ambito si è ormai affermato un particolare concetto di soluzione, detto equilibrio Leader-Follower, in cui il leader svolge il ruolo di difensore, mentre il follower quello di attaccante, e si assume che quest’ultimo possa osservare la strategia del difensore a priori. L’equilibrio Leader-Follower nella sua forma più semplice, che considera un solo leader ed un solo follower, è già stato largamente studiato. Lo scopo di questa tesi è estenderne lo studio, considerando il caso in cui vi sono molteplici followers, i quali giocano un equilibrio di Nash. Si dimostra che il problema, nella forma più generale, è computazionalmente difficile, essendo NP-difficile e non in Poly-APX. Per questo motivo sono stati individuati alcuni casi particolari, ad esempio restringendo lo spazio delle strategie o considerando giochi con una particolare struttura, nel tentativo di individuare situazioni in cui il problema è più semplice da risolvere. Per ogni caso considerato vengono proposti e valutati sperimentalmente algoritmi specifici.