Proteggere obiettivi sensibili in un contesto di attacchi sequenziali

In this work we study, to the best of our knowledge, the first \textit{Security Game} in which an attacker can observe the movements of the defender and perform sequential attacks, exploiting multiple resources. The game is played on an arbitrary graph, and it is in extensive-form: moreover, it can be played more times by both the players. The defender is supported by an alarm system which is perfect, anyhow we show that even in this case the problem's treatment is challenging. We show that the problem is $\mathcal{NP}$-hard, and we provide a polynomial time exact algorithm that finds the \textit{equilibrium path}, when the number of resourse available to the attacker is a fixed parameter. Then, we study the event that the defender doesn't know the number of attacks she will receive, and she makes a \textit{guess} on it: we analyze the robusteness of the defender's strategy with two different ratio. We also propose two online algorithms, the former deterministic, the latter randomized, and we analyze their competitive factor. We conclude the work with an experimental evaluation, inspecting some measures of performance on the exact algorithm.

In questo lavoro studiamo, al meglio delle nostre conoscenze, il primo \textit{Security Game} nel quale un attaccante pu\'o osservare il movimento del difensore e attaccarlo, in modo sequenziale, utilizzando risorse multiple. Il gioco viene giocato su di un grafo arbitrario, e si presenta in forma estesa: pu\'o essere inoltre giocato pi\'u volte da entrambi i giocatori. Il difensore \`e supportato da un sistema di allarme perfetto, tuttavia mostriamo come anche in questo caso il problema sia computazionalmente oneroso. Dimostriamo infatti che il problema \`e $\mathcal{NP}$-difficile, per il quale forniamo un algoritmo esatto che in tempo polinomiale trovi l'\textit{equilibrium path}, qualora il numero di attacchi sferrabili sia un parametro di gioco fissato. Studiamo in seguito il caso in cui il difensore non conosca il numero di attacchi che subir\'a e faccia un \textit{guess} su tale numero, analizzando la robustezza della strategia del difensore con due fattori competitivi differenti. Proponiamo anche due algoritmi online, uno deterministico e uno randomizzato, analizzandone i rispettivi fattori competitivi. Concludiamo il lavoro con una valutazione sperimentale nella quale risolviamo alcune istanze di gioco e mostriamo alcune misure di performance dell'algoritmo esatto introdotto.