Equilibri di Nash e di tipo leadership con applicazione ai patrolling games

The interest aroused by the so-called Security Games has greatly increased in recent times. These games pattern the situation in which an agent must defend various sites from potential attacks. These models have been used in practical situations, for example to define the security system of the LAX - Los Angeles International Airport. In this paper we study a particular type of these games: the Patrolling Games. Examining th situation, we consider two types of players, the Patroller and the Intruder; the former has, as main target, the role to defend various sites of interest (often modeled by a graph), the latter, on the contrary, try to break into a protected area to perform an attack. It can be assumed that the players act simultaneously, so that there can be no observation by some agents of the moves of the others, or as Leadership Games, in which a Leader commits its strategy and the Follower (or Followers) reacts (react) consequently. In this context, it is assumed that the Leader is the Patroller, which can take "observable" behaviors by those who want to launch an attack. It is therefore interesting to compare their solution concepts in the two situations, that is, Nash and Stackelberg equilibria . In the first part of the work it is considered a theoretical study comparing the two types of equilibria, to show how, from the first player point of view is better to take a leadership role if the players are two. On the other hand it is interesting to observe how the situation changes when the game involves two or more actors. Then the results stated in the first part of a Patrolling Game are applied, to highlight how different approaches of the two types of healthy Patroller can determine the outcome of the game. Finally, we consider the Patrolling Games as simultaneous or Stackelberg games with one or two Followers and define techniques for elimination of dominated strategies that reduce the size of the game and the computational cost needed to find a balance.

L'interesse suscitato dai cosiddetti Security Games è notevolmente aumentato negli ultimi tempi. Tali giochi modellizzano la situazione in cui un agente deve difendere vari siti da potenziali attacchi. Questi modelli sono stati utilizzati in situazioni concrete, per esempio per definire il sistema di sicurezza del LAX - Los Angeles International Airport. In questo lavoro si studia un particolare tipo di questi giochi: i Patrolling Games. In questo contesto si considerano due tipi di giocatori, i Patroller e gli Intruder; i primi hanno come obiettivo principale quello di difendere diversi siti di interesse (spesso modellizzati mediante un grafo), i secondi, al contrario, devono cercare di introdursi nello spazio protetto per compiere un attacco. Si può supporre che i giocatori agiscano simultaneamente, quindi che non può esserci osservazione, da parte di alcuni agenti, delle mosse degli altri, o come Leadership Games, in cui un Leader annuncia la propria strategia e il Follower (o i Follower) risponde (rispondono) di conseguenza. In questo contesto si presuppone che il Leader sia il Patroller, che può assumere dei comportamenti “osservabili” da chi voglia sferrare un attacco. Diventa quindi interessante comparare i rispettivi concetti di soluzione nelle due situazioni, cioè gli equilibri di Nash e di Stackelberg. Nella prima parte del lavoro si considera uno studio teorico che pone a confronto i due tipi di equilibrio, per mostrare come, dal punto di vista del giocatore che può assumere il ruolo del Leader, sia più conveniente questo contesto, se l'attaccante è uno solo. D'altra parte è interessante osservare come cambia la situazione quando il gioco coinvolge due o più attori. Successivamente si applicano i risultati enunciati nella prima parte a un Patrolling Game, per mettere in evidenza come due tipi di approcci diversi del Patroller possano determinare l'esito del gioco. Infine, si considerano i Patrolling Games come giochi simultanei e di Stackelberg a uno o due Follower e si definiscono tecniche di eliminazione di strategie dominate che permettono di ridurre le dimensioni del gioco e il costo computazionale necessario per trovare un equilibrio.