In recent years, Game Theory has assumed an important role in many fields, specifically in Security Games. These models are very used for analyzing the behaviour of two players, an Attacker and a Defender. The goal of the Attacker is to attack important places, called targets, while the Defender should protect potential targets as best as he can do or the ones that are under attack. A lot of studies and applications have been done so far in several fields, for example in airports, patrolling on flights and other contests. In this research, the behaviour of the two players in case of multiple attacks has been examined. Specifically, the Defender always has a single resource, while the Attacker has k resources and he can use them in different ways. In the first case, the presence of alarm systems with spatial uncertainty has been supposed and another hypothesis is the fact that the Attacker must use all his resources at the same time. The game can be modeled by a constant sum game and a Leader-Follower model. The idea of the Leader-Follower is that the Defender (Leader) announces the strategy that he will adopt during the game and the Attacker will play according to the Defender strategy. In the present case it is shown that using marginal strategies for the Attacker is equivalent to using correlated strategies. Marginal strategies denote the probability to attack a single target, while correlated strategies specify the probability to attack a ktuple of targets. In the second case, the situation in which the Attacker decides to attack in a sequential way has been analyzed. Differently from the previous model, now the alarm systems are not with spatial uncertainty; moreover it has been supposed that the Attacker has only 2 resources. In this contest, first of all the general model is described and from this one a restrictedmodel has been deduced, allowing finding the best strategy for the Defender. Finally, an algorithm that suggests the best strategy for the Defender has been provided. Specifically, it has been proved that the shortest path is not always the best strategy.

Negli ultimi anni, la Teoria dei Giochi ha assunto un ruolo sempre più importante in molteplici discipline, in particolare nei Security Games. Questi ultimi modellizzano e analizzano il comportamento di due giocatori che rispettivamente ricoprono il ruolo di Attaccante e Difensore. L’obiettivo dell’Attaccante è di attaccare siti di rilevante importanza, detti targets, mentre il Difensore deve cercare di proteggere al meglio i potenziali luoghi attaccabili oppure quelli sotto attacco. Questi studi hanno portato anche ad applicazioni in contesti concreti, come la protezione di aeroporti, il dislocamento del personale di sicurezza sugli aerei, il controllo dei porti. In tale tesi, si è approfondito il comportamento dei due giocatori nel caso di molteplici attacchi. Nello specifico, il Difensore è dotato sempre di una singola risorsa mentre l’Attaccante ha a disposizione k risorse e può utilizzarle in modi differenti. In un primo caso, si è supposta la presenza del segnale d’allarme con incertezza spaziale e l’obbligo da parte dell’Attaccante di servirsi delle risorse in maniera contemporanea. Si tratta di un gioco a somma costante e il comportamento del Difensore prima degli attacchi si modellizza attraverso un modello Leader-Follower. In questa situazione, si è dimostrato che per l’Attaccante le strategie marginali, ovvero le probabilità di attaccare un singolo target, sono equivalenti alle strategie correlate, cioè le probabilità di attaccare una k-tupla di targets. Il secondo caso riguarda invece l’impiego sequenziale delle risorse da parte dell’Attaccante. In particolare, si è ipotizzata la presenza di un sistema di allarme puntuale, ovvero privo di incertezza spaziale; inoltre l’Attaccante non è dotato di k risorse, bensì di solo due. Per questo contesto, è stato studiato il modello generale e si è poi passati ad un modello ridotto che permette di trovare la strategia migliore per il Difensore. A seguito di queste analisi, è stato esaminato e suggerito un algoritmo per trovare la strategia migliore per il Difensore. In particolare, si è visto che lo shortest-path non sempre è il percorso migliore.

Security games : models for multiple attacks

VERGA, ROBERTA
2015/2016

Abstract

In recent years, Game Theory has assumed an important role in many fields, specifically in Security Games. These models are very used for analyzing the behaviour of two players, an Attacker and a Defender. The goal of the Attacker is to attack important places, called targets, while the Defender should protect potential targets as best as he can do or the ones that are under attack. A lot of studies and applications have been done so far in several fields, for example in airports, patrolling on flights and other contests. In this research, the behaviour of the two players in case of multiple attacks has been examined. Specifically, the Defender always has a single resource, while the Attacker has k resources and he can use them in different ways. In the first case, the presence of alarm systems with spatial uncertainty has been supposed and another hypothesis is the fact that the Attacker must use all his resources at the same time. The game can be modeled by a constant sum game and a Leader-Follower model. The idea of the Leader-Follower is that the Defender (Leader) announces the strategy that he will adopt during the game and the Attacker will play according to the Defender strategy. In the present case it is shown that using marginal strategies for the Attacker is equivalent to using correlated strategies. Marginal strategies denote the probability to attack a single target, while correlated strategies specify the probability to attack a ktuple of targets. In the second case, the situation in which the Attacker decides to attack in a sequential way has been analyzed. Differently from the previous model, now the alarm systems are not with spatial uncertainty; moreover it has been supposed that the Attacker has only 2 resources. In this contest, first of all the general model is described and from this one a restrictedmodel has been deduced, allowing finding the best strategy for the Defender. Finally, an algorithm that suggests the best strategy for the Defender has been provided. Specifically, it has been proved that the shortest path is not always the best strategy.
ING - Scuola di Ingegneria Industriale e dell'Informazione
21-dic-2016
2015/2016
Negli ultimi anni, la Teoria dei Giochi ha assunto un ruolo sempre più importante in molteplici discipline, in particolare nei Security Games. Questi ultimi modellizzano e analizzano il comportamento di due giocatori che rispettivamente ricoprono il ruolo di Attaccante e Difensore. L’obiettivo dell’Attaccante è di attaccare siti di rilevante importanza, detti targets, mentre il Difensore deve cercare di proteggere al meglio i potenziali luoghi attaccabili oppure quelli sotto attacco. Questi studi hanno portato anche ad applicazioni in contesti concreti, come la protezione di aeroporti, il dislocamento del personale di sicurezza sugli aerei, il controllo dei porti. In tale tesi, si è approfondito il comportamento dei due giocatori nel caso di molteplici attacchi. Nello specifico, il Difensore è dotato sempre di una singola risorsa mentre l’Attaccante ha a disposizione k risorse e può utilizzarle in modi differenti. In un primo caso, si è supposta la presenza del segnale d’allarme con incertezza spaziale e l’obbligo da parte dell’Attaccante di servirsi delle risorse in maniera contemporanea. Si tratta di un gioco a somma costante e il comportamento del Difensore prima degli attacchi si modellizza attraverso un modello Leader-Follower. In questa situazione, si è dimostrato che per l’Attaccante le strategie marginali, ovvero le probabilità di attaccare un singolo target, sono equivalenti alle strategie correlate, cioè le probabilità di attaccare una k-tupla di targets. Il secondo caso riguarda invece l’impiego sequenziale delle risorse da parte dell’Attaccante. In particolare, si è ipotizzata la presenza di un sistema di allarme puntuale, ovvero privo di incertezza spaziale; inoltre l’Attaccante non è dotato di k risorse, bensì di solo due. Per questo contesto, è stato studiato il modello generale e si è poi passati ad un modello ridotto che permette di trovare la strategia migliore per il Difensore. A seguito di queste analisi, è stato esaminato e suggerito un algoritmo per trovare la strategia migliore per il Difensore. In particolare, si è visto che lo shortest-path non sempre è il percorso migliore.
Tesi di laurea Magistrale
File allegati
File Dimensione Formato  
2016_12_Verga.pdf

accessibile in internet solo dagli utenti autorizzati

Descrizione: Testo della tesi
Dimensione 385.76 kB
Formato Adobe PDF
385.76 kB Adobe PDF   Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/131886