I earned my Ph.D. in Information Technology, working in the Department of Electronics, Information and Bioengineering at Politecnico di Milano, advised by Prof. Nicola Gatti.
My research interests include Algorithmic Game Theory for Security, Equilibrium Computation and Computational Complexity. I studied, developed and tested novel Security Games.
I am currently working for a consulting company in the Data & Analytics Group.
Ph.D. Student in Computer Science and Engineering
Politecnico di Milano, Italy
Alta Scuola Politecnica Diploma
Politecnico di Milano and Politecnico di Torino, Italy
Master of Science in Computer Science and Engineering
Politecnico di Torino, Italy
Mark: 110/110 with honors
Master of Science in Computer Science and Engineering
Politecnico di Milano, Italy
Mark: 110/110 with honors
Bachelor of Science in Computer Science and Engineering
Politecnico di Milano, Italy
Physical security is one of the most important challenges of our times. Due to the terrible events happened in the last decades all around the world, and especially nowadays in Europe, novel techniques and methods are being developed to face new threats and dangers. But security means also helping people and saving lives, e.g., detecting and rescuing desperate migrants that are moving across the Mediterranean Sea.
Algorithmic Game Theory allows us to scientifically investigate these phenomena, modeling such interactions as mathematical problems and designing suitable algorithms to deal with these threats.
When patrolling large environments or infrastructures, a crucial issue is to guarantee some level of protection to each area without being able to constantly surveil them. A common countermeasure is the usage of cheap but wide-ranged sensors, able to detect malicious events that may occur.
We propose the first Security Game model with the presence of an alarm system able to trigger alarm signals, carrying the information about targets that can be under attack. Specifically, we focus on the exploitation of such information to improve the effectiveness of guards' strategies.
This survey presents the main results achieved for the influence maximization problem in social networks. This problem is well studied in the literature and, thanks to its recent applications, some of which currently deployed on the field, it is receiving more and more attention in the scientific community. The problem can be formulated as follows: given a graph, with each node having a certain probability of influencing its neighbors, select a subset of vertices so that the number of nodes in the network that are influenced is maximized. Starting from this model, we introduce the main theoretical developments and computational results that have been achieved, taking into account different diffusion models describing how the information spreads throughout the network, various ways in which the sources of information could be placed, and how to tackle the problem in the presence of uncertainties affecting the network. Finally, we present one of the main application that has been developed and deployed exploiting tools and techniques previously discussed.
We focus on adversarial patrolling games on an arbitrary graph, in which the Defender can control a mobile resource and the targets are alarmed by an alarm system, while the Attacker can observe the movements of the mobile resource of the Defender, and, exploiting multiple attacking resources, perform different sequential attacks against the targets. This scenario captures, e.g., the terroristic assaults in Paris in 2015. It can be modelled as a zero-sum extensive-form game in which each player can play multiple times. The game tree is exponentially large both in the size of the graph and in the number of resources available to the Attacker. We show that, when the number of the Attacker's resources is free, the problem of computing the equilibrium path is NP-hard even if the Attacker is restricted to play all her resources simultaneously, while, when the number of resources is fixed, the equilibrium path can be computed in polynomial time. In particular, we provide a dynamic-programming algorithm that, given the number of the Attacker's resources, computes the equilibrium path requiring polynomial time in the size of the graph and exponential time in the number of the resources. Furthermore, since in real-world scenarios it is implausible that the Defender perfectly knows the number of resources of the Attacker, we study the robustness of the Defender's strategy when she makes a wrong guess about that number. We show that even the error of just a single resource, either underestimating or overestimating the number of the Attacker's resources, can lead to an arbitrary inefficiency, when the inefficiency is defined, as usual, as the ratio of the Defender's utilities obtained with a wrong guess and a correct guess. We argue that, in this case, a more suitable definition of inefficiency is given by the difference of the Defender's utilities. With this definition, we observe that the higher the error in the estimation, the higher the loss for the Defender. Then, we investigate the performance of online algorithms when no information about the Attacker's resources is available, showing that there are no competitive deterministic algorithms. Finally, we resort to randomized online algorithms showing that we can obtain a competitive factor that is twice better than the one that can be achieved by any deterministic online algorithm.
Leadership games provide a powerful paradigm to model many real-world settings. Most literature focuses on games with a single follower who acts optimistically, breaking ties in favour of the leader. Unfortunately, for real-world applications, this is unlikely. In this paper, we look for efficiently solvable games with multiple followers who play either optimistically or pessimistically, i.e., breaking ties in favour or against the leader. We study the computational complexity of finding or approximating an optimistic or pessimistic leader-follower equilibrium in specific classes of succinct games—polymatrix like—which are equivalent to 2-player Bayesian games with uncertainty over the follower, with interdependent or independent types. Furthermore, we provide an exact algorithm to find a pessimistic equilibrium for those game classes. Finally, we show that in general polymatrix games the computation is harder even when players are forced to play pure strategies.
We study for the first time, a leadership game in which one agent, acting as leader, faces another agent, acting as follower, whose behaviour is not known a priori by the leader, being one among a set of possible behavioural profiles. The main motivation is that in real-world applications the common game-theoretical assumption of perfect rationality is rarely met, and any specific assumption on bounded rationality models, if wrong, could lead to a significant loss for the leader. The question we pose is whether and how the leader can learn the behavioural profile of a follower in leadership games. This is a “natural” online identification problem: in fact, the leader aims at identifying the follower’s behavioural profile to exploit at best the potential non-rationality of the opponent, while minimizing the regret due to the initial lack of information. We propose two algorithms based on different approaches and we provide a regret analysis. Furthermore, we experimentally evaluate the pseudo-regret of the algorithms in concrete leadership games, showing that our algorithms outperform the online learning algorithms available in the state of the art.
A team game is a non–cooperative normal–form game in which some teams of players play against others. Team members share a common goal but, due to some constraints, they cannot act jointly. A real–world example is the protection of environments or complex infrastructures by different security agencies: they all protect the area with valuable targets but they have to act individually since they cannot share their defending strategies (of course, they are aware of the presence of the other agents). Here, we focus on zero–sum team games with n players, where a team of n-1 players plays against one single adversary. In these games, the most appropriate solution concept is the Team–maxmin equilibrium, i.e., the Nash equilibrium that ensures the team the highest payoff. We investigate the Team–maxmin equilibrium, characterizing the utility of the team and showing that it can be irrational. The problem of computing such equilibrium is NP–hard and cannot be approximated within a factor of n-ε . The exact solution can only be found by global optimization. We propose two approximation algorithms: the former is a modified version of an already existing algorithm, the latter is a novel anytime algorithm. We computationally investigate such algorithms, providing bounds on the utility for the team. We experimentally evaluate the algorithms analyzing their performance w.r.t. a global optimization approach and evaluate the loss due to the impossibility of correlating.
When securing complex infrastructures or large environments, constant surveillance of every area is not affordable. To cope with this issue, a common countermeasure is the usage of cheap but wide-ranged sensors, able to detect suspicious events that occur in large areas, supporting patrollers to improve the effectiveness of their strategies. However, such sensors are commonly affected by uncertainty. In the present paper, we focus on spatially uncertain alarm signals. That is, the alarm system is able to detect an attack but it is uncertain on the exact position where the attack is taking place. This is common when the area to be secured is wide, such as in border patrolling and fair site surveillance. We propose, to the best of our knowledge, the first Patrolling Security Game where a Defender is supported by a spatially uncertain alarm system, which non-deterministically generates signals once a target is under attack. We show that finding the optimal strategy is FNP-hard even in tree graphs and APX-hard in arbitrary graphs. We provide two (exponential time) exact algorithms and two (polynomial time) approximation algorithms. Finally, we show that, without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. This strategy is optimal even with non-negligible missed detection rates, which, unfortunately, affect every commercial alarm system. We evaluate our methods in simulation, assessing both quantitative and qualitative aspects.
Alarm systems represent a novel issue in Security Games, requiring new models that explicitly describe the dynamic interaction between the players. Recent works studied their employment, even considering various forms of uncertainty, and showed that disregarding them can lead to arbitrarily poor strategies. One of the key problems is computing the best strategy to respond to alarm signals for each mobile defensive resource. The current literature only solves the basic single–resource version of such problem. In this paper, we provide a solution for the multi–resource case addressing the challenge of designing algorithms to coordinate a scaling–up number of resources. First, we focus on finding the minimum number of resources assuring non–null protection to every target. Then, we deal with the computation of multi–resource strategies with different degrees of coordination among resources resorting to adversarial team game models. For each considered problem, we provide algorithms and their theoretical and empirical analysis.
The Team-maxmin equilibrium prescribes the optimal strategies for a team of rational players sharing the same goal and without the capability of correlating their strategies in strategic games against an adversary. This solution concept can capture situations in which an agent controls multiple resources — corresponding to the team members — that cannot communicate. It is known that such equilibrium always exists and it is unique (unless degeneracy) and these properties make it a credible solution concept to be used in real–world applications, especially in security scenarios. Nevertheless, to the best of our knowledge, the Team–maxmin equilibrium is almost completely unexplored in the literature. In this paper, we investigate bounds of (in)efficiency of the Team– maxmin equilibrium w.r.t. the Nash equilibria and w.r.t. the Maxmin equilibrium when the team members can play correlated strategies. Furthermore, we study a number of algorithms to find and/or approximate an equilibrium, discussing their theoretical guarantees and evaluating their performance by using a standard testbed of game instances.
Motivated by a number of security applications, among which border patrolling, we study, to the best of our knowledge, the first Security Game model in which patrolling strategies need to be combined with responses to signals raised by an alarm system, which is spatially uncertain (i.e., it is uncertain over the exact location the attack is ongoing) and is affected by false negatives (i.e., the missed detection rate of an attack may be positive). Ours is an infinite–horizon patrolling scenario on a graph where a single patroller moves. We study the properties of the game model in terms of computational issues and form of the optimal strategies and we provide an approach to solve it. Finally, we provide an experimental analysis of our techniques.
We propose, to the best of our knowledge, the first Security Game where a Defender is supported by a spatially uncertain alarm system which non–deterministically generates signals once a target is under attack. Spatial uncertainty is common when securing large environments, e.g., for wildlife protection. We show that finding the equilibrium for this game is FNP–hard even in the zero–sum case and we provide both an exact algorithm and a heuristic algorithm to deal with it. Without false positives and missed detections, the best patrolling strategy reduces to stay in a place, wait for a signal, and respond to it at best. This strategy is optimal even with non–negligible missed detection rates.
Da Luglio 2018 non sono più al Poli: se avete dubbi/domande/perplessità/problemi (spero sul corso e non di vita!), scrivete al prof. Gatti.
In bocca al lupo per tutto!
Appunti del corso con esercizi (Thanks to Fabio Panozzo)
I temi d'esame con * non hanno la soluzione.
N.B.: alcuni temi d'esame contengono esercizi su argomenti non trattati quest'anno durante il corso. Tali argomenti non saranno oggetto dell'esame.
|4 Ottobre 2017||13.15-16.15||9.1.2 (ex C.G.3)||Scheduling di processi aperiodici|
|11 Ottobre 2017||13.15-16.15||9.1.2 (ex C.G.3)||Scheduling di processi periodici|
|12 Ottobre 2017||11.15-13.15||9.1.2 (ex C.G.3)||Scheduling di processi periodici|
|19 Ottobre 2017||11.15-13.15||9.1.2 (ex C.G.3)||Scheduling di processi misti|
|20 Ottobre 2017||13.15-15.15||9.0.1 (ex C.G.1)||Scheduling di processi misti|
|25 Ottobre 2017||13.15-14.15||9.1.2 (ex C.G.3)||Scheduling di processi misti|
|27 Ottobre 2017||13.15-15.15||9.0.1 (ex C.G.1)||Gestione dell'overload|
|9 Novembre 2017||11.15-13.15||9.1.2 (ex C.G.3)||Seminario su ROS e OROCOS|
|16 Novembre 2017||11.15-13.15||9.1.2 (ex C.G.3)||Statecharts|
|17 Novembre 2017||13.15-15.15||9.0.1 (ex C.G.1)||Statecharts|
|22 Novembre 2017||13.15-16.15||9.1.2 (ex C.G.3)||Statecharts|
|23 Novembre 2017||11.15-13.15||9.1.2 (ex C.G.3)||Statecharts|
|6 Dicembre 2017||13.15-16.15||9.1.2 (ex C.G.3)||Java|
|13 Dicembre 2017||13.15-16.15||9.1.2 (ex C.G.3)||Java|
|14 Dicembre 2017||11.15-13.15||9.1.2 (ex C.G.3)||Java|
|15 Dicembre 2017||13.15-15.15||9.0.1 (ex C.G.1)||Incontro finale di ripasso|
Architettura del calcolatore. Introduzione alla progettazione di un controllore che opera su di un singolo calcolatore: ingressi, uscite, e attività del processo di controllo. Architettura del calcolatore e funzionamento del calcolatore: architettura di von Neumann ed esecuzione delle istruzioni. Interruzioni e loro gestione. Direct Memory Access (DMA). Tecniche di interfacciamento.
Sistema operativo. Introduzione al sistema operativo. Gestione dei processi: stati dei processi, transizione, tabella dei processi. Problemi legati alla concorrenza: mutua esclusione e sincronizzazione. Introduzione alle deadlock. Uso dei monitor. Comunicazione tra processi. Gestione I/O.
Schedulazione real-time. Introduzione al problema del real-time e alla schedulazione di processi. Algoritmi per la schedulazione di processi aperiodici: Erliest Deadline First (EDF) e dimostrazione di ottimalità, EDF con processi con precedenze (EDF*), Bretley e Spring. Algoritmi per la schedulazione di processi periodici: Rate Monotonic (RM) e dimostrazioni di ottimalità e schedulabilità, Earliest Deadline First (EDF) e dimostrazione di schedulabilità, Deadline Monotonic (DM) e Response Time Analysis (RTA). Algoritmi per la schedulazione di processi misti a priorità statica: Deferrable Server (DS) e dimostrazione di schedulabilità, teorema di Tia-Liu-Shankar. Algoritmi per la shedulazione di processi misti a priorità dinamica: EDF e Total Bandwith Server (TBS). Gestione delle condizioni di overload: problematiche, fattore competitivo, limiti teorici sul fattore competitivo, algoritmo Dover.
Real-time e reti di comunicazione. Introduzione alla problematica del real-time su reti di calcolatori. Elementi aggiuntivi di rete: hub, switch. Ethernet real-time e studio della schedulazione real-time della comunicazione dei pacchetti. Sincronizzazione interna ed esterna dei calcolatori sulla rete.
Statecharts. Introduzione al formalismo degli Statecharts. Formalizzazione di problemi basati su concorrenza e su gerarchia.
Principi di Ingegneria del software. Sviluppo di applicazioni software. Ciclo di vita del software. Paradigmi di programmazione. Linguaggi di specifica semiformali. Programmazione in Java.