Education

  • Ph.D. 2018

    Ph.D. Student in Computer Science and Engineering

    Politecnico di Milano, Italy

  • ASP Diploma 2015

    Alta Scuola Politecnica Diploma

    Politecnico di Milano and Politecnico di Torino, Italy

  • M.Sc.2015

    Master of Science in Computer Science and Engineering

    Politecnico di Torino, Italy

    Mark: 110/110 with honors

  • M.Sc.2014

    Master of Science in Computer Science and Engineering

    Politecnico di Milano, Italy

    Mark: 110/110 with honors

  • B.Sc.2012

    Bachelor of Science in Computer Science and Engineering

    Politecnico di Milano, Italy

    Mark: 110/110

Visiting Period

  • 2016
    University of Southern California
    image
    From June to September, I have been at USC, developing research with the Teamcore, under the supervision of Prof. Milind Tambe.

Awards and Grants

  • 2015
    Leonardo Lesmo Award
    image
    2015 AIxIA (Italian Association for the Artificial Intelligence) award for the best Italian MSc thesis on Artificial Intelligence
    2014
    National Doctoral Scholarship
    image
    Three-years doctoral scholarship sponsored by the Ministry of Education, Universities and Research.

Research Group

Alberto Marchesi

Ph.D. Student

Webpage

Alessandro Nuara

Ph.D. Student

Nicola Gatti

Associate Professor

Webpage

Marcello Restelli

Assistant Professor

Webpage

Nicola Basilico

Assistant Professor

Webpage

Francesco Trovò

Postdoc

Webpage

Stefano Paladino

Ph.D. Student

Webpage

Andrea Celli

Ph.D. Student

Webpage

Filter by type:

Sort by year:

How to Maximize the Spread of Social Influence: A Survey

Giuseppe De Nittis and Nicola Gatti
Tech Report arXiv Technical Report

Abstract

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.

Facing Multiple Attacks in Adversarial Patrolling Games with Alarmed Targets

Giuseppe De Nittis and Nicola Gatti
Tech Report arXiv Technical Report

Abstract

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.

Computing the Strategy to Commit to in Polymatrix Games

Giuseppe De Nittis, Alberto Marchesi and Nicola Gatti
Conference Conference on Artificial Intellgence (AAAI 2018)

Abstract

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.

Regret Minimization Algorithms for the Follower’s Behaviour Identification in Leadership Games

Lorenzo Bisi, Giuseppe De Nittis, Francesco Trovò, Marcello Restelli and Nicola Gatti
Conference Conference on Uncertainty in Artificial Intelligence (UAI 2017)

Abstract

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.

Computing the Team–maxmin Equilibrium in Single–Team Single–Adversary Team Games

Nicola Basilico, Andrea Celli, Giuseppe De Nittis and Nicola Gatti
JournalIntelligenza Artificiale

Abstract

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.

Adversarial Patrolling with Spatially Uncertain Alarm Signals

Nicola Basilico, Giuseppe De Nittis and Nicola Gatti
JournalArtificial Intelligence (AIJ)

Abstract

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.

Coordinating Multiple Defensive Resources in Patrolling Games with Alarm Systems

Nicola Basilico, Andrea Celli, Giuseppe De Nittis and Nicola Gatti
Conference International Conference on Antonomous Agents and Multiagent Sytems (AAMAS 2017)

Abstract

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.

Team–maxmin Equilibrium: Efficiency Bounds and Algorithms

Nicola Basilico, Andrea Celli, Giuseppe De Nittis and Nicola Gatti
Conference Conference on Artificial Intelligence (AAAI 2017)

Abstract

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.

A Security Game Combining Patrolling and Alarm–Triggered Responses under Spatial and Detection Uncertainties

Nicola Basilico, Giuseppe De Nittis and Nicola Gatti
Conference Conference on Artificial Intelligence (AAAI 2016)

Abstract

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.

A Security Game Model for Environment Protection in the Presence of an Alarm System

Nicola Basilico, Giuseppe De Nittis and Nicola Gatti
Conference Conference on Decision and Game Theory for Security (GameSec 2015)

Abstract

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.

Current Teaching

    • 2014 2018

    Sistemi Informatici

    Teaching Assistant